Let G = (V,E) be an undirected graph that is connected and has acost associated
ID: 3610161 • Letter: L
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
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.