Chapter Notes Minimum Spanning Trees
This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.
Learning objectives
- Explain the main ideas and vocabulary in Chapter Notes Minimum Spanning Trees.
- Work through the source examples for Chapter Notes Minimum Spanning Trees without depending on raw chunk order.
- Use Chapter Notes Minimum Spanning Trees as selective reference when learner modules point back to The Algorithm Design Manual.
Prerequisites
- None curated yet.
Module targets
module-03-graph-algorithms
AI companion modes
- Explain simply
- Socratic tutor
- Quiz me
- Challenge my understanding
- Diagnose my confusion
- Generate extra practice
- Revision mode
- Connect forward / backward
Source-of-truth note
This unit is anchored to The Algorithm Design Manual and the source chapter "Chapter Notes Minimum Spanning Trees". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.
External enrichment
No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.
Source provenance
- Primary source:
The Algorithm Design Manual - Source chapter: Chapter Notes Minimum Spanning Trees
- Raw source file:
088-chapter-notes-minimum-spanning-trees.md
Merged source
Chapter Notes Minimum Spanning Trees
Chapter Notes Minimum Spanning Trees
Chapter Notes Minimum Spanning Trees
6-2. [3] Is the path between two vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample.
6-3. [3] Assume that all edges in the graph have distinct edge weights (i.e. , no pair of edges have the same weight). Is the path between a pair of vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph?
Give a proof or a counterexample.
6-4. [3] Can Prim's and Kruskal's algorithm yield different minimum spanning trees?
Explain why or why not.
6-5. [3] Does either Prim's and Kruskal's algorithm work if there are negative edge weights? Explain why or why not.
6-6. [5] Suppose we aregiventhe minimum spanning treeTof a given graphG(withn
vertices andmedges) and a new edgee= (u, v) of weightwthat we will add toG.
Give an efficient algorithm to find the minimum spanning tree of the graphG+e.
Your algorithm should run inO(n) time to receive full credit.
6-7. [5] (a) LetTbe a minimum spanning tree of a weighted graphG. Construct a new graph G′ by adding a weight of k to every edge of G. Do the edges of T form a minimum spanning tree ofG′? Prove the statement or give a counterexample.
(b) Let P={s, . . . , t}describe a shortest weighted path between vertices sandt
of a weighted graphG. Construct a new graphG′ by adding a weight ofkto every edge ofG. DoesPdescribe a shortest path fromstot inG′? Prove the statement or give a counterexample.
6-8. [5] Devise and analyze an algorithm that takes a weighted graph Gand finds the smallest change in the cost to a non-MST edge that would cause a change in the minimum spanning tree ofG. Your algorithm must be correct and run in polynomial time.
6-9. [4] Consider the problem of finding a minimum weight connected subsetTof edges from a weighted connected graph G. The weight of T is the sum of all the edge weights inT.
(a) Why is this problem not just the minimum spanning tree problem? Hint: think negative weight edges.
(b) Give an efficient algorithm to compute the minimum weight connected subset
T.
6-10. [4] Let G= (V, E) be an undirected graph. A set F ⊆Eof edges is called a
feedback-edge setif every cycle of Ghas at least one edge inF.
(a) Suppose that G is unweighted. Design an efficient algorithm to find a minimum-size feedback-edge set.
(b) Suppose that Gis a weighted undirected graph with positive edge weights.
Design an efficient algorithm to find a minimum-weight feedback-edge set.
6-11. [5] Modify Prim's algorithm so that it runs in timeO(nlogk) on a graph that has onlykdifferent edges costs.
Union-Find 6-12. [5] Devise an efficient data structure to handle the following operations on a weighted directed graph:
(a) Merge two given components.
(b) Locate which component contains a given vertexv.
(c) Retrieve a minimum edge from a given component.
6-13. [5] Design a data structure that can perform a sequence of, munion and find operations on a universal set of nelements, consisting of a sequence of all unions followed by a sequence of allfinds, in time O(m+n).
Shortest Paths 6-14. [3] Thesingle-destination shortest path problem for a directed graph seeks the shortest pathfromevery vertex to a specified vertexv. Give an efficient algorithm to solve the single-destination shortest paths problem.
6-15. [3] LetG= (V, E) be an undirected weighted graph, and letTbe the shortest-path
spanning tree rooted at a vertexv. Suppose now that all the edge weights inGare increased by a constant numberk. Is T still the shortest-path spanning tree from v?
6-16. [3] Answer all of the following:
(a) Give an example of a weighted connected graph G= (V, E) and a vertex v,
such that the minimum spanning tree ofGis the same as the shortest-path spanning tree rooted atv.
(b) Give an example of a weighted connected directed graph G= (V, E) and a
vertexv, such that the minimum-cost spanning tree ofGis very different from the shortest-path spanning tree rooted atv.
(c) Can the two trees be completely disjointed?
6-17. [3] Either prove the following or give a counterexample:
(a) Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?
(b) Suppose that the minimum spanning tree of the graph is unique. Is the path between a pair of vertices in a minimum spanning tree of an undirected graph necessarily the shortest (minimum weight) path?
6-18. [5] In certain graph problems, vertices have can have weights instead of or in addition to the weights of edges. Let Cv be the cost of vertex v, andC(x,y) the cost of the edge (x, y). This problem is concerned with finding the cheapest path between vertices aandb in a graph G. The cost of a path is the sum of the costs of the edges and vertices encountered on the path.
(a) Suppose that each edge in the graph has a weight of zero (while non-edges
have a cost of ∞). Assume that Cv = 1 for all vertices 1 ≤v ≤n(i.e. , all
vertices have the same cost). Give anefficientalgorithm to find the cheapest path fromatoband its time complexity.
(b) Now suppose that the vertex costs are not constant (but are all positive) and the edge costs remain as above. Give an efficient algorithm to find the cheapest path fromatoband its time complexity.
(c) Now suppose that both the edge and vertex costs are not constant (but are all positive). Give an efficient algorithm to find the cheapest path fromato band its time complexity.
6-19. [5]LetGbe a weighteddirectedgraph withnvertices andmedges, where all edges have positive weight. A directed cycle is a directed path that starts and ends at the same vertex and contains at least one edge. Give an O(n3) algorithm to find a directed cycle in Gof minimum total weight. Partial credit will be given for an
O(n2m) algorithm.
6-20. [5]Can we modify Dijkstra's algorithm to solve the single-sourcelongestpath problem by changingminimumtomaximum? If so, then prove your algorithm correct.
If not, then provide a counterexample.
6-21. [5]LetG= (V, E) be a weighted acyclic directed graph with possibly negative edge
weights. Design a linear-time algorithm to solve the single-source shortest-path
problem from a given sourcev.
6-22. [5] Let G= (V, E) be a directed weighted graph such that all the weights are
positive. Let v andwbe two vertices in Gandk≤|V| be an integer. Design an
algorithm to find the shortest path fromvtowthat contains exactlykedges. Note
that the path need not be simple.
6-23. [5] Arbitrageis the use of discrepancies in currency-exchange rates to make a profit.
For example, there may be a small window of time during which 1 U.S. dollar buys 0.75 British pounds, 1 British pound buys 2 Australian dollars, and 1 Australian dollar buys 0.70 U.S. dollars. At such a time, a smart trader can trade one U.S.
dollar and end up with 0.75×2×0.7 = 1.05 U.S. dollars--a profit of 5%. Suppose that there are ncurrencies c1, ..., cn and ann×ntable Rof exchange rates, such that one unit of currency ci buysR[i, j] units of currency cj. Devise and analyze an algorithm to determine the maximum value of
R[c1, ci1] · R[ci1, ci2]· · ·R[cik−1, cik] · R[cik, c1]
Hint: think all-pairs shortest path.
Network Flow and Matching 6-24. [3] A matching in a graph is a set of disjoint edges--i.e., edges that do not share any vertices in common. Give a linear-time algorithm to find a maximum matching in a tree.
6-25. [5] Anedge coverof an undirected graphG= (V, E) is a set of edges such that each
vertex in the graph is incident to at least one edge from the set. Give an efficient