Let G(V, E) be a weighted undirected graph. Let the value of a spanning tree be the minimum weight of the edges. Let the cap from a cut [S, V - S] (i.e, the set of undirected edges that connect a node in S to a node in the remaining set V -S) be the maximum weight of its edges. Prove that the maximum value of a spanning tree of G equals the minimum cap of a cut in G ?
How to model his problem to a network flow problem, any hints thanks in advance!! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
