3.16 Graph algorithms: trees, cycles and routes
Studying this course? Keep your progress in one place.
Key facts
- A walk repeats freely; a trail repeats no edge; a path repeats no vertex; a circuit and a cycle are closed.
- An Eulerian route uses every edge once: 0 odd vertices give a circuit, 2 give a trail.
- A Hamiltonian cycle visits every vertex once; there is no simple test for one.
- Kruskal and Prim find a minimum spanning tree ( edges, no cycle).
- Chinese postman repeats the least extra distance; travelling salesman is bounded above and below.
Routes in a graph
The names describe which edges and vertices a route may repeat, and whether it returns to its start.
A graph has vertices joined by edges. The degree of a vertex is the number of edges meeting it. A graph is connected if there is a walk between any two vertices.
A walk is any sequence of linked edges. A trail is a walk with no repeated edge. A path has no repeated vertex. A circuit is a closed trail and a cycle is a closed path.
A tree is a connected graph with no cycles; with vertices it has edges. A complete graph has an edge between every pair of vertices.
| Trail | Path | Circuit | Cycle | |
|---|---|---|---|---|
| Repeats an edge | No | No | No | No |
| Repeats a vertex (apart from start = end) | Yes | No | Yes | No |
| Closed | No | No | Yes | Yes |
Trail
- Repeats an edge:
- No
- Repeats a vertex (apart from start = end):
- Yes
- Closed:
- No
Path
- Repeats an edge:
- No
- Repeats a vertex (apart from start = end):
- No
- Closed:
- No
Circuit
- Repeats an edge:
- No
- Repeats a vertex (apart from start = end):
- Yes
- Closed:
- Yes
Cycle
- Repeats an edge:
- No
- Repeats a vertex (apart from start = end):
- No
- Closed:
- Yes
A route repeats a vertex but no edge, and ends where it began. What is it?
Eulerian trails and circuits
Count the odd vertices: none gives an Eulerian circuit, two give an Eulerian trail, more give neither.
An Eulerian trail uses every edge exactly once; an Eulerian circuit also returns to the start. For a connected graph:
- all vertices even: a circuit exists, from any start
- exactly two odd vertices: a trail exists, from one odd vertex to the other, but no circuit
- more than two odd vertices: neither exists
In the graph, degrees are . Only and are odd, so a trail runs from to , for example .
A connected graph has 4 vertices of odd degree. What can you say?
Hamiltonian paths and cycles
A Hamiltonian cycle visits every vertex exactly once and returns to the start; there is no simple test for one.
A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle also returns to the start. It need not use every edge.
You find one by trial, or show none exists by finding a vertex that cannot be reached. A complete graph with vertices always has one.
In the five-vertex graph, is a Hamiltonian cycle. It uses 5 of the 7 edges.
| Eulerian | Hamiltonian | |
|---|---|---|
| Visits | Every edge once | Every vertex once |
| Test | Count odd vertices | Trial and error |
Eulerian
- Visits:
- Every edge once
- Test:
- Count odd vertices
Hamiltonian
- Visits:
- Every vertex once
- Test:
- Trial and error
A Hamiltonian cycle in a 5-vertex graph uses how many edges?
Minimum spanning trees
A minimum spanning tree joins every vertex with the least total weight; Kruskal and Prim both build it.
A minimum spanning tree (MST) of a connected weighted graph contains every vertex and has least total weight.
Kruskal: sort the edges by weight, add the smallest that makes no cycle, and stop at edges.
Prim: start at any vertex and repeatedly add the smallest edge joining the tree to a vertex outside it. In the matrix method, delete row and circle column ; choose the smallest uncrossed entry in the circled columns, delete that new row and circle its column; repeat.
Kruskal suits a list of edges; Prim suits a table.
Worked example (Kruskal)
Find the minimum spanning tree of the graph above.
- 1
Sort: , , , , , .
- 2
Add (3), (4) and (5). None forms a cycle.
- 3
There are edges, so stop. would have made a cycle.
How many edges does an MST of a graph with 7 vertices have?
Chinese postman
Repeat the cheapest set of edges that makes every vertex even, then add the repeat to the total weight.
The Chinese postman problem asks for the shortest closed route that uses every edge at least once. If all vertices are even, the answer is the total weight, an Eulerian circuit.
Otherwise some edges must be repeated. Pair up the odd vertices, find the least distance for each pair (check routes through other vertices) and choose the pairing with the least total. Two odd vertices give one pairing; four give three.
- 1
List the odd vertices
- 2
Find least distances
a table helps if a direct edge is not shortest
- 3
List every pairing
total the least distances
- 4
Choose the least total
and repeat those paths
- 5
Add up
all edge weights plus the repeated distance
Worked example
AB = 9, AC = 4, AD = 6, BC = 3, BD = 8, CD = 5 (all four vertices are odd). Find the shortest route using every road and returning to the start.
- 1
The total of all weights is .
- 2
Pairing and : (least to is ).
- 3
Pairing and : . Pairing and : .
- 4
The least is , so repeat and .
A graph has exactly two odd vertices. How many pairings must you test?
Travelling salesman and choosing
The tour is squeezed between a lower bound from a deleted vertex and an upper bound from nearest neighbour.
The travelling salesman problem asks for the Hamiltonian cycle of least weight in a weighted complete graph. If roads are missing, first complete a table of least distances.
Upper bound, nearest neighbour: go to the nearest unvisited vertex each time, then return. Any valid tour is an upper bound; try several starts.
Lower bound, deleted vertex: delete a vertex, find the MST of the rest and add the two shortest edges at the deleted vertex. Taking the largest over all vertices gives the best bound.
State .
- 1
Complete the graph
table of least distances
- 2
Upper bound
nearest neighbour tour
- 3
Lower bound
delete a vertex, MST, add two shortest edges
- 4
State both
lower bound upper bound
| Spanning tree | Chinese postman | Travelling salesman | |
|---|---|---|---|
| Need | Connect everything cheaply | Use every edge | Visit every vertex |
| Method | Kruskal or Prim | Repeat least distance | Give bounds |
Spanning tree
- Need:
- Connect everything cheaply
- Method:
- Kruskal or Prim
Chinese postman
- Need:
- Use every edge
- Method:
- Repeat least distance
Travelling salesman
- Need:
- Visit every vertex
- Method:
- Give bounds
A council wants the cheapest set of cables linking all villages. Which algorithm?
Try an exam question
A weighted graph has vertices with , , , , and . Use Kruskal's algorithm to find a minimum spanning tree and state its total weight.
[4 marks]
- [1]Sorts the edges: 3, 4, 5, 6, 7, 8.
- [1]Adds , and and rejects any edge that forms a cycle.
- [1]Stops with edges.
- [1]Total weight .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which statement about this graph is correct?
1 mark, marked against the mark scheme
Which statement about this graph is correct?
1 mark, marked against the mark scheme