Consider the Minimum Spanning Tree Problem on an undirected graph G = (V, E) wit

Question

Consider the Minimum Spanning Tree Problem on an undirected graph G = (V, E) with a cost Ce 0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in general be many distinct minimum-cost solutions. Suppose we are given a spanning tree T E with the property that for every e T, e belongs to some minimum-cast spanning tree in G. Can we conclude that T itself must be a minimum-cost spanning tree in G? Give a proof or a counterexample with explanation.

Explanation / Answer

Please rate with 5 stars :)

here is a counterexample:

a) The two 1-edges in the triangle form a spanning tree.
b) Each 1-edge is part of a minimal spanning tree when paired with the 0-edge.
c) However, despite this, the two 1-edges don't form a minimal spanning tree when paired together.
d) So therefore we conclude that it doesn't suffice to know that each edge is part of some minimal spanning tree when trying to determine whether a spanning tree is minimal itself

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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