The maximum capacity spanning tree problem is as follows for a given graph G = (V, E) withcapacities c(uv) on the edges. The capacity of a tree T is defined as the minimum capacity of anedge in T. The maximum capacity spanning tree problem is to determine the maximum capacity ofa spanning tree.(i) Describe how to modify the input graph to find a maximum weight spanning tree making use ofa minimum weight spanning tree algorithm.(ii) Show that a maximum (weight) spanning tree is also a maximum capacity spanning tree.(iii) Is the converse of part (ii) true? That is, is it true that a maximum capacity spanning tree is alsoa maximum spanning tree? Either give counterexamples (of all sizes) or a proof.(iv) Prove the following max-min result. The maximum capacity of a spanning tree is equal to theminimum bottleneck value of a cut. For a subset U ⊆ V , the cut [U, V − U] is the set of edgesbetween U and V − U. The bottleneck value of a cut [U, V − U] is the largest capacity among theedges of the cut
The maximum capacity spanning tree problem is as follows for a given graph G = (V, E) with
capacities c(uv) on the edges. The capacity of a tree T is defined as the minimum capacity of an
edge in T. The maximum capacity spanning tree problem is to determine the maximum capacity of
a spanning tree.
(i) Describe how to modify the input graph to find a maximum weight spanning tree making use of
a minimum weight spanning tree algorithm.
(ii) Show that a maximum (weight) spanning tree is also a maximum capacity spanning tree.
(iii) Is the converse of part (ii) true? That is, is it true that a maximum capacity spanning tree is also
a maximum spanning tree? Either give counterexamples (of all sizes) or a proof.
(iv) Prove the following max-min result. The maximum capacity of a spanning tree is equal to the
minimum bottleneck value of a cut. For a subset U ⊆ V , the cut [U, V − U] is the set of edges
between U and V − U. The bottleneck value of a cut [U, V − U] is the largest capacity among the
edges of the cut
Step by step
Solved in 2 steps with 9 images
