Log In
1 vote

how is statement iv always true??

in Algorithms 122 views
Yes 4 is not always true consider a triangle. all edges form cyclem
and i think statement 3 is true as all the edges will be distinct when the first best MST is formed second best MST is formed by removing a edge with the next highest edge so the second best also will be unique

correct me if i'm wrong!!
yes @pavan,i also think the same,dts y i marked that answr
@Akriti, even i marked same(C). but see option (4) it says edges that do not lie in any cycle must be in MST, it doesn't say what if they lie in cycle. So (4) is true.

And for (3) who knows maybe someone can draw a graph. But not sure. maybe it depends on how weights are distributed (1+4) = (3+2)
3rd sttement says that MST will include all edges not in cycle,it also means that we can include any edge not in ycle even if it is the maximum size edge,but thats not true..right??

anmd since,weights are unique,so second best will just not contain the minimum weight edge,rest all same.can u give nay counter example for 3rd??

no even if a max weight edge is not in cycle it is to be included, consider graph::

AC = 100,DC = 101,CB = CE = BE = 1

So, (4) is definitely true. And According to me (3) is also true, but i mean to say maybe there exists a counter example for option (iii) statement.
alright..thanks @mcjoshi..:)

Please log in or register to answer this question.

Related questions

5 votes
1 answer
Which of the following statements are false ? $1.$ A depth-first search of a directed graph always produces the same number of tree edges (i.e., independent of the order in which the vertices are provided and independent of the order of the adjacency list). ... path between any two vertices will not change. $4.$ Dijkstra's algorithm may not terminate if the graph contains negative weight edges.
asked Jan 23, 2017 in Algorithms Akriti sood 547 views
1 vote
0 answers
Which of the following statements are correct? S1: Binary search on array take less time than binary search on linked list. S2: Merge sort on array has more space complexity than merge sort on linked list. Only S1 Only S2 Both S1 and S2 Neither S1 nor S2 ** Here my doubt is, In S1 should i assume here that array is sorted. Answer given as Both S1 and S2.
asked Dec 27, 2015 in DS Sandeep Singh 150 views
0 votes
0 answers
A packet has arrived in which the offset value of second frame is 450, the header length is 20 and the value of total length field is 1000. What is the number of the first byte in the first frame and the last byte in the last frame if the size of IP packet is 3500 B. ... value of second frame is $450$ then 1st frame consisted of $450 \times 8 = 3600B$. that's more than the data we want to send.
asked Sep 10, 2018 in Computer Networks Mk Utkarsh 98 views
0 votes
0 answers
28 views asked Aug 27, 2018 in Operating System Avik Chowdhury 28 views