D1.2 Graphs, minimum spanning trees and Dijkstra
⤓ Presentation⤓ PowerPointPresentation: opens offline in any browser, simulations live. PowerPoint: editable.
Decision Mathematics 1 (AS), specification sections 2.1–2.4. Route inspection and the travelling salesperson are on D1.3; sorting and bin packing on D1.1.
What this page covers
7 points
- Graph vocabulary: vertex, edge, weight, degree, walk, trail, path, cycle, connected, subgraph, tree, spanning tree, simple graph, digraph
- Complete graphs Kn, planar graphs and isomorphic graphs
- Eulerian and semi-Eulerian graphs and the degree test
- Adjacency matrices and distance (weight) matrices
- Minimum spanning trees by Kruskal's algorithm
- Prim's algorithm on a drawn network and on a distance matrix
- Dijkstra's algorithm: labelling boxes, working values, and tracing back the route
In one minute
6 points
- The degrees of all the vertices of a graph add up to twice the number of edges, so the number of odd vertices is always even; Kn has ½n(n − 1) edges.
- A tree is connected with no cycles; a tree on n vertices has n − 1 edges. A minimum spanning tree (MST) is a spanning tree of least total weight.
- Kruskal: list the arcs in increasing order of weight; add each one unless it would make a cycle; stop at n − 1 arcs.
- Prim: start at any vertex; repeatedly add the cheapest arc joining a vertex in the tree to one outside it. On a matrix: cross out rows, look down the labelled columns.
- Dijkstra: give the start 0; from the newest permanent vertex update working values; make the smallest working value permanent; repeat. Trace back using final(Y) − final(X) = weight of XY.
- Eulerian: connected with every degree even. Semi-Eulerian: connected with exactly two odd vertices, and a trail through every edge starts at one and ends at the other.
Contents
12 sections
- What are graphs and networks, and what do the words mean?
- What are complete, planar and isomorphic graphs?
- When is a graph Eulerian, and how are graphs stored as matrices?
- What is a minimum spanning tree, and how does Kruskal's algorithm find one?
- How does Prim's algorithm work, on a network and on a matrix?
- How does Dijkstra's algorithm find a shortest route?
- Exam tips for D1.2
- Common misconceptions
- How this topic connects
- Key formulae
- Check your understanding
- Specification checklist
What are graphs and networks, and what do the words mean?
D1 graph questions reward exact vocabulary and visible working: why a graph is or is not simple, connected, a tree, planar or Eulerian; the order in which Kruskal or Prim adds arcs; and every Dijkstra working value with a trace-back.
| Word | Meaning |
|---|---|
| Degree (valency) | the number of edge-ends at a vertex; a loop adds 2. A vertex is odd or even according to its degree |
| Walk | a sequence of edges, each starting where the last one ended |
| Trail | a walk in which no edge is used twice |
| Path | a walk in which no vertex is visited twice (so no edge is repeated either) |
| Cycle | a closed path: it ends where it started, with no other vertex repeated |
| Connected | there is a path between every pair of vertices |
| Subgraph | a graph made from some of the vertices and edges of another graph |
| Simple graph | no loops and at most one edge between any pair of vertices |
| Tree | a connected graph with no cycles |
| Spanning tree | a subgraph that is a tree and includes every vertex of the original graph |
| Digraph | a graph whose edges have directions (one-way arcs), shown with arrows |
(a) Find the number of edges in K₇ and the degree of each vertex. (b) A graph has six vertices with degrees 4, 4, 3, 3, 2 and 2. Find the number of edges. (c) Explain why no graph has degrees 5, 4, 3, 3, 2, 2. (d) Explain why no simple graph on 5 vertices can have a vertex of degree 5. (e) State the number of edges in a spanning tree of a connected graph with 9 vertices.
(a) Each vertex joins the other 6, and every edge is counted from both ends: degree 6; edges = ½ × 7 × 6 = 21.
(b) 4 + 4 + 3 + 3 + 2 + 2 = 18 = 2 × edges, so 9 edges.
(c) 5 + 4 + 3 + 3 + 2 + 2 = 19 is odd, so it cannot equal twice a whole number of edges (equivalently, there would be three odd vertices).
(d) In a simple graph a vertex joins each other vertex at most once; there are only 4 others, so the maximum degree is 4.
(e) A tree on n vertices has n − 1 edges: 8 edges.
What are complete, planar and isomorphic graphs?
- A complete graph Kn has n vertices, each joined to every other by exactly one edge: each degree is n − 1 and there are ½n(n − 1) edges (K₄: 6, K₅: 10, K₆: 15).
- A graph is planar if it can be drawn in a plane with no edges crossing. A drawing with crossings does not prove a graph is non-planar: try redrawing it. K₄ is planar; K₅ is not.
- Two graphs are isomorphic if they are the same graph drawn differently: there is a one-to-one matching of vertices so that two vertices are joined in one graph exactly when the matching vertices are joined in the other.
Testing for isomorphism. Quick checks can rule it out: same number of vertices, same number of edges, same list of degrees; if any differ, the graphs are not isomorphic. Equal degree lists do not prove it: look for a structural difference such as a triangle in one but not the other, or how the odd vertices are joined. To show two graphs are isomorphic, write down the matching and check every edge.
G has vertices 1–6 and edges 12, 23, 34, 45, 56, 61, 14. H has vertices P–U and edges PQ, QR, ST, TU, PS, QT, RU. J has vertices 1–6 and edges 12, 23, 34, 45, 56, 61, 13. (a) Show that G and H are isomorphic. (b) Explain why G and J are not isomorphic, even though they have the same degrees.
(a) Both have 6 vertices, 7 edges and degrees 3, 3, 2, 2, 2, 2; the degree-3 vertices are 1, 4 in G and Q, T in H, and in both they are joined. Matching 1→Q, 2→P, 3→S, 4→T, 5→U, 6→R: 12→QP, 23→PS, 34→ST, 45→TU, 56→UR, 61→RQ, 14→QT, all edges of H, so G and H are isomorphic.
(b) J contains the triangle 1–2–3; G has no cycle of length 3 (its shortest cycles, 1–2–3–4 and 1–4–5–6, have length 4), so they are not isomorphic.
When is a graph Eulerian, and how are graphs stored as matrices?
An Eulerian graph has a closed trail using every edge exactly once (drawn without lifting your pen, finishing where you started). A semi-Eulerian graph has such a trail that starts and finishes at different vertices. Each time a trail passes through a vertex it uses two edge-ends there, so only the start and finish can be odd.
An adjacency matrix has a row and column for each vertex; the entry in row X, column Y is the number of edges joining X to Y. For an undirected graph it is symmetric about the leading diagonal; a loop at X goes on the diagonal (usually as 2, as it adds 2 to the degree, or as 1 by some conventions: say which you use). With no loops, the row sum for X is the degree of X. A distance (weight) matrix holds the weight of each arc, with a dash for no direct arc; Prim's algorithm runs on it directly. For a digraph, row X, column Y refers to the arc from X to Y, so the matrix need not be symmetric.
A graph has this adjacency matrix. (a) Explain how it shows that the graph is not simple. (b) Find the degree of each vertex and the number of edges. (c) Determine whether the graph is Eulerian, semi-Eulerian or neither, and write down a trail that uses every edge exactly once.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 2 | 1 | 0 |
| C | 1 | 2 | 0 | 1 | 1 |
| D | 0 | 1 | 1 | 0 | 1 |
| E | 0 | 0 | 1 | 1 | 0 |
(a) The entry 2 in row B, column C means two edges join B and C.
(b) Row sums: A 2, B 4, C 5, D 3, E 2; 16 ÷ 2 = 8 edges.
(c) The graph is connected and only C and D are odd, so it is semi-Eulerian, with a trail from C to D, e.g. C – B – C – A – B – D – E – C – D. Check: 8 edges, using each of the two B–C edges once.
What is a minimum spanning tree, and how does Kruskal's algorithm find one?
Kruskal's algorithm is greedy: at every step it takes the cheapest arc still available, as long as it does not form a cycle.
- Sort the arcs into ascending order of weight.
- Add the arc of least weight to the tree.
- Take the next arc: add it if it does not form a cycle with the arcs already chosen, otherwise reject it.
- Repeat step 3 until n − 1 arcs have been added.
The tree may be in separate pieces until the end. Arcs of equal weight may be taken in either order; say which you chose.
The network has vertices A–H and arcs AB 7, AC 5, BC 9, BD 4, CD 6, BE 10, DE 5, DF 8, CF 11, EF 7, EG 6, FG 9, GH 3, EH 12, FH 10. (a) Use Kruskal's algorithm to find a minimum spanning tree, listing the arcs in the order considered and stating which are rejected. (b) State the weight of the tree.
(a) Work through the sorted arcs until there are 8 − 1 = 7:
| Step | Arc | Weight | Decision |
|---|---|---|---|
| 1 | GH | 3 | add |
| 2 | BD | 4 | add |
| 3 | AC | 5 | add |
| 4 | DE | 5 | add |
| 5 | CD | 6 | add |
| 6 | EG | 6 | add |
| 7 | AB | 7 | reject (cycle) |
| 8 | EF | 7 | add |
Seven arcs are added, so DF 8, BC 9, FG 9, … need not be considered. (b) MST GH, BD, AC, DE, CD, EG, EF; weight 3 + 4 + 5 + 5 + 6 + 6 + 7 = 36.
The tied pairs (AC, DE at 5 and CD, EG at 6) are both accepted, so their order does not matter. AB and EF tie at 7: taking EF first would complete the tree and AB would never be considered. The tree is the same either way.
Rejecting an arc because one of its ends is "already in the tree". Reject only if both ends are already connected through chosen arcs: that is what makes a cycle. EF is accepted although E is in the tree, because F is not.
How does Prim's algorithm work, on a network and on a matrix?
- Choose any vertex to start the tree.
- Select the arc of least weight joining a vertex in the tree to a vertex not yet in the tree, and add it.
- Repeat step 2 until every vertex is in the tree.
Prim never needs a cycle check, because each new arc reaches a new vertex, and the tree is connected at every stage.
Use Prim's algorithm, starting at A, on the network of worked example 4. List the arcs in the order selected.
From A alone the cheapest arc out is AC 5; from A, C it is CD 6 (not AB 7). From A, C, D: DB 4; then DE 5; then EG 6; then GH 3; finally F joins by EF 7 (cheaper than DF 8, FG 9, FH 10, CF 11). Order AC, CD, DB, DE, EG, GH, EF; weight 36.
GH 3 is the lightest arc but Prim takes it sixth: it cannot be chosen until G is in the tree. That is the key difference from Kruskal.
On a distance matrix, "arcs from the tree" are the entries in the columns of vertices already chosen. Label each column in the order its vertex joins and cross out its row, so you never select an arc back into the tree.
- Choose a starting vertex: label its column 1 and delete its row.
- Look down all labelled columns and circle the smallest entry not in a deleted row.
- That entry's row gives the new vertex: label its column with the next number and delete its row.
- Repeat until every row is deleted. The circled entries are the arcs of the tree.
The table gives lengths, in km, of possible water pipes between villages P–U. Use Prim's algorithm, starting at P, to find a minimum spanning tree. State the order in which vertices are added and the total length.
| P (1) | Q (2) | R (3) | S (5) | T (4) | U (6) | |
|---|---|---|---|---|---|---|
| P | — | 14 | 21 | 17 | 30 | 25 |
| Q | (14) | — | 12 | 19 | 24 | 28 |
| R | 21 | (12) | — | 16 | 13 | 22 |
| S | 17 | 19 | (16) | — | 18 | 11 |
| T | 30 | 24 | (13) | 18 | — | 20 |
| U | 25 | 28 | 22 | (11) | 20 | — |
Column P labelled 1, row P deleted: smallest in column P is 14, row Q. Columns P, Q: 12 (column Q, row R) → R. Columns P, Q, R: 13 (column R, row T) → T. Columns P, Q, R, T: 16 (column R, row S), not 17 (P to S) or 18 (T to S) → S. Finally 11 (column S, row U) → U.
Order P, Q, R, T, S, U; arcs PQ 14, QR 12, RT 13, RS 16, SU 11: total 66 km. The bracketed numbers in the header are the order labels; the bold entries are the circled arcs.
"The order in which the arcs are selected" needs arcs (PQ, QR, …), not vertices; "the order of vertices" needs vertices. On a matrix, show the column labels and deleted rows: the final tree alone does not show you used Prim.
How does Dijkstra's algorithm find a shortest route?
Dijkstra's algorithm finds the shortest route from a start vertex to every other vertex, in networks and digraphs whose weights are not negative. Each vertex gets a box: vertex, order of labelling and final value on top, working values underneath. A working value is the shortest distance found so far; a final value is the shortest distance, fixed for good.
- Give the start vertex final value 0 and order label 1.
- For every vertex Y joined directly to the vertex X just made final (and Y not yet final): working value = final(X) + weight XY. Write it in Y's box only if it is smaller than Y's current working value.
- Of all vertices without final values, give the one with the smallest working value its final value and the next order label.
- Repeat 2 and 3 until the destination has a final value.
- Trace back from the destination: arc XY is on the route when final(Y) − final(X) = weight of XY.
A network has arcs SA 9, SB 5, SC 12, AB 3, AD 7, BC 6, BD 11, BE 15, CE 9, DE 4, DT 16, EF 5, ET 13, FT 6. Use Dijkstra's algorithm to find the shortest route from S to T and its length.
S final (0): A 9, B 5, C 12; smallest B. B final (5): A 5 + 3 = 8 < 9 (write 8), C 11 < 12 (write 11), D 16, E 20; smallest A. A final (8): D 8 + 7 = 15 < 16. C final (11): E 11 + 9 = 20, not smaller, so nothing is written. D final (15): E 19 < 20, T 31. E final (19): F 24, T 32 (not smaller). F final (24): T 30 < 31. T final (30).
| Order | Vertex | Final value | Working values |
|---|---|---|---|
| 1 | S | 0 | — |
| 2 | B | 5 | 5 |
| 3 | A | 8 | 9, 8 |
| 4 | C | 11 | 12, 11 |
| 5 | D | 15 | 16, 15 |
| 6 | E | 19 | 20, 19 |
| 7 | F | 24 | 24 |
| 8 | T | 30 | 31, 30 |
Trace back: 30 − 24 = 6 = FT; 24 − 19 = 5 = EF; 19 − 15 = 4 = DE; 15 − 8 = 7 = AD; 8 − 5 = 3 = BA; 5 − 0 = 5 = SB. Shortest route S–B–A–D–E–F–T, length 30. E is not the vertex before T: 30 − 19 = 11, but ET is 13.
Crossing out or overwriting working values, or writing a new value larger than the existing one. List every improving value in order, and only those: the boxes are your evidence.
Farm water pipes join junctions A–G; lengths in tens of metres are AB 12, AC 8, AD 15, BC 6, BE 10, CD 9, CE 15, CF 11, DF 7, EF 5, EG 13, FG 9, DG 18. (a) Use Kruskal's algorithm to find a minimum spanning tree, stating the order of arcs and its weight. (b) Use Dijkstra's algorithm to find the shortest route from A to G. (c) Water must now pass through B on its way from A to G. Find the shortest such route. (d) Explain why the route from A to G within your tree is not the answer to (b).
(a) In order: EF 5, BC 6, DF 7, AC 8, CD 9, FG 9; none of the first six makes a cycle. EF, BC, DF, AC, CD, FG; weight 44 (6 arcs for 7 vertices; CD and FG tie at 9).
| Order | Vertex | Final value | Working values |
|---|---|---|---|
| 1 | A | 0 | — |
| 2 | C | 8 | 8 |
| 3 | B | 12 | 12 |
| 4 | D | 15 | 15 |
| 5 | F | 19 | 19 |
| 6 | E | 22 | 23, 22 |
| 7 | G | 28 | 33, 28 |
(b) D keeps 15 (AD): via C it would be 17. Trace back: 28 − 19 = 9 = FG; 19 − 8 = 11 = CF; 8 − 0 = 8 = AC. A–C–F–G, length 28 (280 m).
(c) A to B: AB = 12 (A–C–B is 14). B to G: B–E–G = 23 (B–E–F–G is 24, B–C–F–G is 26). A–B–E–G, length 35 (350 m).
(d) In the tree, A to G is A–C–D–F–G = 33, longer than 28. An MST minimises the total length connecting every vertex, not the distance between a particular pair.
Exam tips for D1.2
For Kruskal, list every arc you consider in order, with "reject" beside rejected ones. For Prim, list arcs in the order selected. A correct tree with no order shown does not demonstrate the algorithm.
In Dijkstra, fill in order of labelling, final value and all working values for every vertex you reach, including the destination, then show the trace-back subtraction for each arc of the route.
Count the vertices first. A spanning tree on n vertices has exactly n − 1 arcs: stop Kruskal as soon as you have them, and check your Prim list has that many.
"Explain why this is a tree" needs connected and no cycles. "Explain why it is semi-Eulerian" needs "connected and exactly two vertices of odd degree", naming them.
With equal weights either arc may come first; say which you took. If asked whether the MST is unique, check whether a tied arc you rejected could have replaced one you accepted.
Common misconceptions
| Misconception | Why it is wrong | Correct idea |
|---|---|---|
| Prim always starts with the lightest arc in the network. | Prim starts from a chosen vertex and only looks at arcs leaving the current tree. | The lightest arc is Kruskal's first step; in Prim it joins only when one end is in the tree. |
| Kruskal rejects an arc if one end is already in the tree. | That is how the tree grows. | Reject only if both ends are already connected, so the arc would close a cycle. |
| The MST contains the shortest route between any two vertices. | It minimises total weight, not each pairwise distance. | Use Dijkstra (worked example 8: 33 in the tree, 28 by Dijkstra). |
| In Dijkstra, a working value is final as soon as it is written. | A later vertex may give a shorter route (A: 9 then 8). | Only the smallest working value among non-final vertices is made final each step. |
| A drawing with crossing edges shows the graph is not planar. | Planar means it can be redrawn without crossings. | Try to redraw it; K₄ as a square with diagonals is planar. |
| Graphs with the same degrees are isomorphic. | Matching degrees is necessary, not sufficient. | Find an explicit matching, or a structural difference such as a triangle. |
How this topic connects
D1.3 Route inspection and the travelling salesperson
The degree test decides which arcs must be repeated in route inspection, Dijkstra finds the shortest repeats, and minimum spanning trees give upper and lower bounds for the travelling salesperson problem.
D1.1 Algorithms and critical path analysis
Kruskal's first step is a sort, and all three graph algorithms are greedy algorithms whose work grows with the network. Activity networks are digraphs; the forward pass works like Dijkstra but takes the largest value at each event.
P1 Coordinate geometry
When vertices are grid points, arc weights are often straight-line distances found with Pythagoras' theorem before an algorithm is run.
Key formulae
| Formula | Use | In the formulae list? |
|---|---|---|
| sum of degrees = 2 × number of edges | counting edges from degrees; showing a degree list is impossible | No — learn it |
| number of odd vertices is even | consequence of the line above | No — derive it |
| Kn: ½n(n − 1) edges, each degree n − 1 | complete graphs; maximum edges in a simple graph on n vertices | No — derive it |
| spanning tree on n vertices: n − 1 arcs | knowing when Kruskal or Prim is finished | No — learn it |
| Eulerian ⇔ connected, all degrees even; semi-Eulerian ⇔ connected, exactly two odd | whether every edge can be traced exactly once | No — learn it |
| working value of Y = final(X) + weight XY | updating boxes in Dijkstra | No — learn it |
| final(Y) − final(X) = weight XY | tracing back a Dijkstra route | No — learn it |
Check your understanding
1. How many edges does K₁₀ have, and how many arcs are in a spanning tree of K₁₀?
½ × 10 × 9 = 45 edges; a spanning tree has 10 − 1 = 9 arcs.
2. A connected graph has exactly four odd vertices. Is it Eulerian, semi-Eulerian or neither?
Neither: Eulerian needs no odd vertices and semi-Eulerian exactly two. At least two edges would have to be repeated.
3. A simple graph has four vertices, each of degree 3. Name it and state its number of edges.
K₄ (each vertex joins all three others), with (3 × 4) ÷ 2 = 6 edges.
4. A minimum spanning tree is found for K₆ with distinct weights. How many arcs of K₆ are not used?
K₆ has 15 arcs and the tree uses 5, so 10 are not used.
5. A network has arcs SA 4, SB 9, AB 3, AT 11, BT 6. Find the shortest route from S to T.
S 0; A 4; B min(9, 4 + 3) = 7; T min(4 + 11, 7 + 6) = 13. Route S–A–B–T, length 13.
Specification checklist
- (D1 2.1) I can use and define vertex, edge, weight, degree, walk, trail, path, cycle, connected, subgraph, simple graph, tree, spanning tree and digraph.
- (D1 2.1) I can use the fact that the degrees add up to twice the number of edges, and state the number of edges of Kn.
- (D1 2.1) I can recognise complete and planar graphs, and decide whether two graphs are isomorphic by matching vertices or finding a difference.
- (D1 2.1) I can decide whether a graph is Eulerian or semi-Eulerian from its degrees, and say where a trail must start and finish.
- (D1 2.1) I can write down and read adjacency matrices and distance matrices.
- (D1 2.2) I can find a minimum spanning tree with Kruskal's algorithm, showing the order of arcs and those rejected.
- (D1 2.2) I can find a minimum spanning tree with Prim's algorithm on a network, listing arcs in order, and explain how Prim and Kruskal differ.
- (D1 2.3) I can apply Prim's algorithm to a distance matrix, labelling columns and deleting rows.
- (D1 2.4) I can apply Dijkstra's algorithm with full boxes (order, final value, working values), trace back the shortest route, and state its length.