The Gateway to Computer Science Excellence
0 votes
57 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 by Boss (13.8k points) | 57 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 ?
+1

" 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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,596 answers
195,824 comments
102,083 users