Show that the minimum spanning tree of a weighted, undirected graph is equivalen

Question

Show that the minimum spanning tree of a weighted, undirected graph is equivalent to a bottleneck shortest path tree of the graph, viz. a tree that has the property that for every pair of vertices u; v, the longest edge on the tree path connecting u and v is as short as possible (here, short and long refer to weights). Show that the minimum spanning tree of a weighted, undirected graph is equivalent to a bottleneck shortest path tree of the graph, viz. a tree that has the property that for every pair of vertices u; v, the longest edge on the tree path connecting u and v is as short as possible (here, short and long refer to weights).

Explanation / Answer

Let G = (N,E,w) be a weighted undirected graph. For every spanning tree T =
(N,E?) of G, define a bottleneck edge of T as an edge which has the maximum
weight over all edges in E?. A minimum weight bottleneck spanning tree is
a spanning tree such that the weight of its bottleneck edge is the minimum over all
spanning trees.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.