The electric grid connection problem
An electricity supplier wants to connect a power plant and a set of customers by installing wires. A wire can connect two locations directly, and customers may receive power through other customers. The supplier wants the cheapest set of wires that still connects everyone.
The natural model is an undirected graph G=(V,E). Nodes represent the power plant and customers. Edges represent possible wires. Since a wire has no direction, an edge between nodes a and b is written {a,b}, and {a,b}={b,a}.
Each edge has a nonnegative cost c(i,j). The goal is to choose a subset of edges T ⊆ E that connects all nodes and minimizes ∑{i,j}∈T c(i,j).
Minimum spanning tree problem
Input.
- Undirected graph G=(V,E).
- Nonnegative edge cost c(i,j) for every edge {i,j}∈E.
Output.
- A subset T⊆E connecting every pair of nodes.
Objective.
Minimize ∑{i,j}∈T c(i,j).
Playing around with the chapter example
The graph below is the chapter’s six-node example. A feasible solution is any set of edges that connects every node to every other node. If a feasible solution contains a cycle, at least one edge on that cycle can be removed without disconnecting the graph. Since costs are nonnegative, an optimal solution never needs such a redundant cycle.
Input graph
Edges are undirected; the number on each edge is the installation cost.
Minimum spanning tree
One optimal tree has total cost 18.
A connected graph on n nodes needs at least n−1 edges. A tree is a connected graph with exactly n−1 edges and no cycle. For the six-node example, any spanning tree has five edges.
Two greedy algorithms
Kruskal’s algorithm
- Start with T=∅.
- Sort edges in increasing cost.
- Consider the next cheapest edge {i,j}.
- Add it to T if doing so does not create a cycle.
- Stop once all nodes are connected, or once every edge has been considered.
Equivalent test: add an edge exactly when its endpoints are currently in different connected components.
Prim’s algorithm
- Choose a start node s.
- Let S={s} and T=∅.
- Among all edges with one endpoint in S and one endpoint outside S, choose the cheapest.
- Add that edge to T, and add the new endpoint to S.
- Repeat until every node is in S.
The algorithm grows one connected tree outward from the start node.
Interactive minimum spanning tree lab
Edit the graph, then step through either algorithm. The page treats edges as undirected and uses nonnegative costs. Double-click blank space to add a node, drag nodes to reposition them, and use Add edge mode to connect two nodes.
Algorithm controls
Selection
Current components
Kruskal edge order
Solution summary
Verifying an MST with a lower bound
The chapter also explains a geometric certificate for Euclidean instances: draw non-overlapping discs around points, then grow equal-width moats around the connected components as they merge. Each layer contributes a mandatory amount of length to any spanning tree. When this lower bound equals the cost of a displayed tree, the tree is certified optimal.
Moat ledger
| Initial discs | 5·2r = 10r | 10.00 |
| First moats | 2·2s = 4s | 1.40 |
| Final moat | 1·2t = 2t | 0.80 |
| Total lower bound | 10r+4s+2t | 12.20 |
|---|
The drawing is a teaching visualization of the certificate described in the chapter; the sliders show how the ledger changes.
The reason this certificate matches Kruskal’s algorithm is that components merge exactly when the cheapest edge between them becomes tight. The accumulated moat lengths budget precisely for the edges Kruskal adds.
Implementation notes
Graph editor
The editor supports undirected edges, nonnegative costs, node dragging, edge insertion, deletion, and automatic complete-graph construction from node positions.
Algorithm behavior
If the graph is disconnected, the algorithms display a minimum spanning forest and warn that no spanning tree exists for the full graph.
Source material
The default six-node example and edge costs are taken from the attached TeX chapter. The referenced header image was not included with the upload, so it is omitted.
