01:640:103 Chap.10 Trees, Networks and Kruskal's Algorithm
Trees, Networks and Kruskal's Algorithm
From round trips to networks
The second graph-theory question is about building a network, such as rail links between cities, so that every city can reach every other, perhaps through intermediate stops, at the least total cost. A graph is connected if a path joins every pair of vertices, and a tree is a connected graph with no circuits.
If a network contains a circuit, one of its links can be removed without disconnecting anything, so the cheapest connected network is always a tree.
Spanning trees and redundancy
A spanning tree of a connected graph uses every vertex and only edges of the graph, and a minimum spanning tree is a spanning tree of least total weight. Every tree with V vertices has exactly V minus 1 edges.
The redundancy of a connected graph, the largest number of edges it can lose and stay connected, equals E + 1 − V, one more than the edge count less the vertex count; a tree has redundancy 0.
Kruskal's Algorithm
Kruskal's Algorithm starts from the vertices alone and adds edges in increasing order of weight, skipping only an edge that would close a circuit, until it has V minus 1 edges.
Unlike the Cheapest Link Algorithm for circuits, it allows three or more edges at one vertex. It is both efficient and guaranteed to find a minimum spanning tree, a combination the Traveling Salesman heuristics could not achieve.
Why a tree is the cheapest connected network
Suppose a network connects every city and contains a circuit.
Removing any one edge of that circuit leaves every city still reachable, because the rest of the circuit provides another route, and the network becomes cheaper. Repeating this until no circuit remains gives a tree. So a network of least cost that keeps everything connected must be a tree, and the only question is which tree.
A tree has no spare links, which is also its weakness: losing any one link disconnects it, while a network with redundancy can survive some failures.
Redundancy puts a number on that trade-off. A graph with 6 vertices and 15 edges, every pair of cities linked, has redundancy 15 + 1 − 6 = 10: ten links could fail and the network might stay connected.
Its minimum spanning tree keeps only 5 edges and has redundancy 0. Cost and resilience pull in opposite directions, and the course asks you to compute both.
What this chapter covers
- 01
Connected graphs and circuits
- 02
Trees and spanning trees
- 03
Counting edges and redundancy
- 04
Kruskal's Algorithm
- 05
Why Kruskal is both optimal and efficient
Worked example · free
Kruskal on five towns
- 2Take B–C 7, D–E 8 and A–C 9; none closes a circuit.
- 2Take C–D 10, which joins the two groups; the tree now has 4 = 5 − 1 edges.
- 2Stop: B–E 11 and every dearer edge would close a circuit. Total = 7 + 8 + 9 + 10 = 34.
Key terms
- Tree
- A tree is a connected graph that contains no circuits.
- Spanning tree
- A spanning tree is a tree using every vertex of a graph and only that graph's edges.
- Minimum spanning tree
- A minimum spanning tree is a spanning tree whose total edge weight is as small as possible.
- Redundancy
- Redundancy is the number of edges a connected graph can lose while staying connected, E + 1 − V.
- Connected graph
- A connected graph has a path between every pair of its vertices.
Trees, Networks and Kruskal's Algorithm FAQ
How is Kruskal's Algorithm different from Cheapest Link?
Both add edges from cheapest upward. Cheapest Link builds a circuit, so it also rejects a third edge at any vertex; Kruskal builds a tree, so it rejects only an edge that closes a circuit and allows several edges at one vertex.
How many edges does a spanning tree of a 12-vertex graph have?
Eleven. Every tree has one fewer edge than vertices, whichever spanning tree is chosen and whatever the edge weights are. Picture it as a family tree: every vertex except the first hangs from exactly one edge.
Does Kruskal's Algorithm ever need to backtrack?
No. It considers each edge once, in increasing order of weight, and either keeps it or skips it because it would close a circuit. The resulting spanning tree is guaranteed to have the least possible total weight.
Exam move
Sort all edges by weight before starting, cross them off as you take or skip them, and state the reason for each skip in one word: circuit.
Working through Trees, Networks and Kruskal's Algorithm in 01:640:103? Sia is AskSia’s AI Mathematics tutor — ask any 01:640:103 Trees, Networks and Kruskal's Algorithm question and get a clear, step-by-step explanation grounded in how 01:640:103 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
