Graph vocabulary: vertex, edge, weight, degree, walk, trail, path, cycle, connected, subgraph, tree, spanning tree, simple graph, digraph

Complete graphs Kₙ, 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

1. 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; Kₙ has ½n(n − 1) edges.

2. 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.

3. Kruskal: list the arcs in increasing order of weight; add each one unless it would make a cycle; stop at n − 1 arcs.

4. 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.

5. 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.

6. 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.

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.

WORKED EXAMPLE · QUESTION

(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.

SOLUTION

(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.

A complete graph Kₙ 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.

WORKED EXAMPLE · QUESTION

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.

SOLUTION

(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.

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.

WORKED EXAMPLE · QUESTION

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.

SOLUTION

(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.

Kruskal's algorithm is greedy: at every step it takes the cheapest arc still available, as long as it does not form a cycle.

1. Sort the arcs into ascending order of weight.

2. Add the arc of least weight to the tree.

3. Take the next arc: add it if it does not form a cycle with the arcs already chosen, otherwise reject it.

4. 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.

WORKED EXAMPLE · QUESTION

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.

SOLUTION

(a) Work through the sorted arcs until there are 8 − 1 = 7:

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.

1. Choose any vertex to start the tree.

2. Select the arc of least weight joining a vertex in the tree to a vertex not yet in the tree, and add it.

3. 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.

WORKED EXAMPLE · QUESTION

Use Prim's algorithm, starting at A, on the network of worked example 4. List the arcs in the order selected.

SOLUTION

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.

1. Choose a starting vertex: label its column 1 and delete its row.

2. Look down all labelled columns and circle the smallest entry not in a deleted row.

3. That entry's row gives the new vertex: label its column with the next number and delete its row.

4. Repeat until every row is deleted.

The circled entries are the arcs of the tree.

WORKED EXAMPLE · QUESTION

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.

SOLUTION

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.

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.

1. Give the start vertex final value 0 and order label 1.

2. 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.

3. Of all vertices without final values, give the one with the smallest working value its final value and the next order label.

4. Repeat 2 and 3 until the destination has a final value.

5. Trace back from the destination: arc XY is on the route when final(Y) − final(X) = weight of XY.

WORKED EXAMPLE · QUESTION

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.

SOLUTION

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).

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.

WORKED EXAMPLE · QUESTION

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).

SOLUTION

(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).

(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.

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.

1. How many edges does K₁₀ have, and how many arcs are in a spanning tree of K₁₀?

2. A connected graph has exactly four odd vertices. Is it Eulerian, semi-Eulerian or neither?

3. A simple graph has four vertices, each of degree 3. Name it and state its number of edges.

4. A minimum spanning tree is found for K₆ with distinct weights. How many arcs of K₆ 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.

1. ½ × 10 × 9 = 45 edges; a spanning tree has 10 − 1 = 9 arcs.

2. Neither: Eulerian needs no odd vertices and semi-Eulerian exactly two. At least two edges would have to be repeated.

3. K₄ (each vertex joins all three others), with (3 × 4) ÷ 2 = 6 edges.

4. K₆ has 15 arcs and the tree uses 5, so 10 are not used.

5. S 0; A 4; B min(9, 4 + 3) = 7; T min(4 + 11, 7 + 6) = 13. Route S–A–B–T, length 13.