Here is some intuition: The min weight edge E of a max val spanning tree naturally cuts V into two sets S and V-S. You should be able to add a source and sink with infinite capacity edges from source to S and V-S to sink and reason about flows across the cut to argue that it is also a min cap cut with max edge E. The proof is an immediate consequence of this.
On Nov 14, 10:13 pm, Sundi <[email protected]> wrote: > 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.
