Let G = (V,E) be an undirected graph that is connected and has acost associated

Question

Let G = (V,E) be an undirected graph that is connected and has acost associated with
every one of its edges. Let T denote a minimum-cost spanning treeof G
(as computed by, for example, Kruskal’s algorithm).

Suppose that the cost of a path in G is defined to be the cost ofthe most expensive edge on
that path (i.e., it is the max rather than the sum of the edgecosts on the path).

• Prove that, for any pair of vertices x and y, the path fromx to y that uses only edges
of T is as cheap as any other path in G from x to y.
Let G = (V,E) be an undirected graph that is connected and has acost associated with
every one of its edges. Let T denote a minimum-cost spanning treeof G
(as computed by, for example, Kruskal’s algorithm).

Suppose that the cost of a path in G is defined to be the cost ofthe most expensive edge on
that path (i.e., it is the max rather than the sum of the edgecosts on the path).

• Prove that, for any pair of vertices x and y, the path fromx to y that uses only edges
of T is as cheap as any other path in G from x to y.

Explanation / Answer

Kruskal’s algorithm sorts the edges and then puts them inone at a time so long as they don’t form a cycle. So, firstthe AD and BE edges will be added, then the DE edge, and then theEF edge. The AB edge will be skipped over because it forms a cycle,and finally the CF edge will be added (at that point you can eithernotice that you have included n 1 edges and therefore aredone, or else keep going, skipping over all the remaining edges oneat a time).

Let G be the given graph, and let F be the forest we haveconstructed so far (initially, F consists of n trees of 1 nodeeach, and at each step two trees get merged until finally F is justa single tree at the end). Assume by induction that there exists anMST M of G that is consistent with F, i.e., all edges in F are alsoin M; this is clearly true at the start when F has no edges. Let ebe the next edge added by the algorithm. Our goal is to show thatthere exists an MST M’ of G consistent with F U{e}.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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