3.16 Graph algorithms: trees, cycles and routes

3.16 Graph algorithms: trees, cycles and routes

IB Maths: Applications and Interpretation HL: Revision notes

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 (n−1n-1 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 nn vertices it has n−1n-1 edges. A complete graph has an edge between every pair of vertices.

ABCDE
A graph with five vertices and seven edges. The shaded triangle A, B, C is a cycle: a closed route that repeats no vertex.

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 2,3,4,3,22,3,4,3,2. Only BB and DD are odd, so a trail runs from BB to DD, for example B→A→C→B→D→C→E→DB\to A\to C\to B\to D\to C\to E\to D.

ABCDE
The example graph. Degrees: A 2, B 3, C 4, D 3, E 2.

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 n≥3n\ge3 vertices always has one.

In the five-vertex graph, A→B→D→E→C→AA\to B\to D\to E\to C\to A is a Hamiltonian cycle. It uses 5 of the 7 edges.

ABCDE
The Hamiltonian cycle A, B, D, E, C, A uses the five solid edges; the dashed edges BC and CD are not used

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 n−1n-1 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 AA and circle column AA; 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.

weight 5weight 3weight 8weight 6weight 4weight 7ABCD
AB = 5, AC = 3, AD = 8, BC = 6, BD = 4, CD = 7.

Worked example (Kruskal)

Find the minimum spanning tree of the graph above.

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

    List the odd vertices

  2. 2

    Find least distances

    a table helps if a direct edge is not shortest

  3. 3

    List every pairing

    total the least distances

  4. 4

    Choose the least total

    and repeat those paths

  5. 5

    Add up

    all edge weights plus the repeated distance

The algorithm (up to four odd vertices)

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.

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 lower≤L≤upper\text{lower}\le L\le\text{upper}.

  1. 1

    Complete the graph

    table of least distances

  2. 2

    Upper bound

    nearest neighbour tour

  3. 3

    Lower bound

    delete a vertex, MST, add two shortest edges

  4. 4

    State both

    lower bound ≤L≤\le L\le upper bound

Bounding the tour

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 A,B,C,DA,B,C,D with AB=5AB=5, AC=3AC=3, AD=8AD=8, BC=6BC=6, BD=4BD=4 and CD=7CD=7. Use Kruskal's algorithm to find a minimum spanning tree and state its total weight.

[4 marks]

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

Revision notes