Consider the following graph G with solid and dotted edges: 3 6 The solid edges

Question

Consider the following graph G with solid and dotted edges: 3 6 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, (2,5), (3,6), (6,8), (7,8) and (6,9), such that: » Each of the edge weights is a positive INTEGER; » Tree T is a SHORTEST PATH tree of G with root vi and NO other tree is a SHORTEST PATH tree of G with root vi; » Each of the edge weights of the dotted edges is as small as possible. For instance, the distance from vi to v5 in T is 6. If you assign the edge weight 2 to edge (v2, v5), then replacing edge (v4, vs) in T with edge (v2, v5) will give a spanning tree whose distance from v1 to vs is 5. Thus edge (v2, v5) must have a weight greater than 2. If you assign the edge weight 3 to edge (v2, v5) then replacing edge (v4, v5) in T with edge (v2, v5) will give a spanning tree whose distance from vi to v5 is 6. This new tree would also be a shortest path tree of G. Thus edge (v2, v;) must have weight greater than 3

Explanation / Answer

Here we have minimum weight from source vertex so,

*
As weight to travel from node 7 to 8 is 6 (3+2+1) via edges (7,4) and (4,5) and (5,8),
so our path weight should be greater than 6
hence weight for edge should be minimum (7,8)-->7
*
similarly weight to travel from node 2 to 5 is 9 (3+4+2) via nodes 2 to 1 to 4 to 5,
so our path weight should be greater than 9
hence weight for edge should be minimum
(2,5)-->10
*
similarly weight to travel from node 3 to 6 is 12 (5+7) via nodes 3 to 2 to 6,
so our path should be greater than 12
hence weight for edge should be minimum
(3,6)-->13
*
similarly weight to travel from node 6 to 8 is 15 (5+3+4+2+1) via nodes 6 to 2 to 1 to 4 to 5 to 8,
so our path should be greater than 15
hence weight for edge should be minimum
(6,8)-->16
*
similarly weight to travel from node 6 to 9 is 17 (5+3+4+2+1+2) via nodes 6 to 2 to 1 to 4 to 5 to 8 to 9,
so our path should be greater than 17
hence weight for edge should be minimum
(6,9)-->18

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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