2. Consider the following graph C with solid and dotted edges: The solid edges f

Question

2. Consider the following graph C with solid and dotted edges: The solid edges form a spanning tree T of graph G. Each of the solid edges has a weight. Assign weights to the dotted edges, (1,2), (2,3), (4,5), (3,6) and (4,7), such that: Each of the edge weights is a positive INTEGER; Tree T is a MINIMUM spanning tree of G and NO other tree is a MINIMUM spanning tree of G; Each of the edge weights of the dotted edges is as small as possible. For instance, if you assign the edge weight 1 to edge (2,3), then replacing edge (3,5) in T with edge (2,3) will give a spanning tree with less weight than T. Thus edge (2,3) must have a weight greater than 1. if you assign the edge weight 3 to edge (2,3), then replacing edge (3,5) in T with edge (2,3) will give a different spanning tree with weight equal to T. This new tree would also be a minimum spanning tree. Thus edge (2,3) must have a weight greater than 3.

Explanation / Answer

https://drive.google.com/file/d/0B3lVit8k3iPqczg2SndtUWp4Zm8/view?usp=sharing

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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