search
Log In
0 votes
92 views
II.  if an edge (u,v) is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph.

III. If (u,v) is a light edge connecting CC(connected component) to some other component in the forest of graph G, then (u, v) is     included in the minimum spanning tree.

 

didn’t understand the part “light edge crossing some cut of the graph”

can someone explain me with the diagram ??
in Algorithms 92 views
0
those two statement are equivalent, right ?
0
yup

but I couldn't  analyze the part  " it is a light edge crossing some cut of the graph."

what's that mean ?
2

" it is a light edge crossing some cut of the graph."

means, it is minimum weight edge among those edges which are in the connecting other component

in e1,e2,e3 we should include one edge in any case which is should having less weight

0

got it !

thanks @Shaik

Please log in or register to answer this question.

Related questions

0 votes
1 answer
1
318 views
How many numbers of spanning tree are possible?
asked Nov 9, 2018 in Algorithms Lakshman Patel RJIT 318 views
0 votes
1 answer
2
73 views
T/F In a graph G=(V,E) suppose that each edge e ∊ E has an integer weight w(e) such that 1<= W(e) <=n Then there is a an o(mlogn) time algorithm to find a minimum spanning tree in G. Also,Does this "weight w(e) such that 1<= W(e) <=n" has significance on time complexity or we consider it as some edges weights and proceed?
asked Oct 4, 2018 in Algorithms meghna 73 views
0 votes
0 answers
3
140 views
Which algorithm will be implemented on the weighted graph in which the edges are uniformly distributed over the half-open interval $[0,1)$ to construct MST so that it runs in linear time? $A)$ Kruskal's algorithm $B)$ Prim's algorithm $C)$ Both $(A)$ and $(B)$ $D)$ None of these
asked Nov 10, 2018 in Algorithms Lakshman Patel RJIT 140 views
1 vote
1 answer
4
255 views
How to count the number of spanning tree?
asked Nov 9, 2018 in Algorithms Lakshman Patel RJIT 255 views
...