3.16 Graph algorithms: trees, cycles and routesIB Maths: Applications and Interpretation HL: Revision notes

A graph has vertices joined by edges; the degree of a vertex is the number of edges meeting it. A walk is any sequence of edges linking vertices. A trail is a walk with no repeated edge. A path is a walk with no repeated vertex. A circuit is a closed trail (starts and ends at the same vertex). A cycle is a closed path: no vertex repeats except the start and end. A tree is a connected graph with no cycles; a tree with $n$ vertices has $n-1$ edges. A complete graph has an edge between every pair of vertices. A graph is connected if there is a walk between any two vertices.

An Eulerian trail uses every edge exactly once; an Eulerian circuit does so and returns to the start. For a connected graph:

• all vertices of even degree $\Rightarrow$ an Eulerian circuit exists (and every vertex is a possible start);
• exactly two vertices of odd degree $\Rightarrow$ an Eulerian trail exists, but no circuit, and it must start at one odd vertex and end at the other;
• more than two odd vertices $\Rightarrow$ neither exists. Example: edges $AB, AC, BC, BD, CD, CE, DE$ give degrees $2,3,4,3,2$. Only $B$ and $D$ are odd, so there is an Eulerian trail from $B$ to $D$, e.g. $B\to A\to C\to B\to D\to C\to E\to D$.

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does so and returns to the start. Unlike the Eulerian case, there is no simple rule for deciding whether one exists: you find one by trial, or show none exists by checking that a vertex cannot be reached with the edges available. In a complete graph with $n\ge3$ vertices a Hamiltonian cycle always exists. A Hamiltonian cycle need not use every edge.

A minimum spanning tree (MST) of a connected weighted graph is a tree containing every vertex with the least possible total weight. Kruskal's algorithm: sort the edges by weight; add the smallest edge that does not form a cycle; stop at $n-1$ edges. Prim's algorithm: start at any vertex; repeatedly add the smallest edge joining a vertex in the tree to a vertex outside; stop when all vertices are included. Kruskal suits a list of edges; Prim suits a table of distances. Prim's matrix method: write the distance matrix. Start at $A$: delete row $A$ and circle column $A$ entries. Choose the smallest uncrossed entry in the circled columns; its row gives the new vertex, so delete that row and mark its column. Repeat until all rows are deleted. Example: $AB=5, AC=3, AD=8, BC=6, BD=4, CD=7$. Prim from $A$ adds $AC$ (3), $AB$ (5), $BD$ (4): total $12$. Kruskal gives the same tree.

The Chinese postman problem asks for the shortest closed route that traverses 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. Algorithm (up to four odd vertices):

1. List the odd vertices.
2. Use a table of least distances if edges are not the shortest connection.
3. List every way to pair the odd vertices and total the least distances.
4. Choose the pairing with the least total and repeat those paths.
5. Route length $=$ total of all edge weights $+$ repeated distance. Why it works: the repeated edges make every vertex even, giving an Eulerian circuit, and the least total repeated distance gives the shortest such route. With two odd vertices only one pairing exists; with four odd vertices there are three pairings. Example: $AB=9, AC=4, AD=6, BC=3, BD=8, CD=5$. All four vertices are odd. Pairings: $AB\&CD=7+5=12$, $AC\&BD=4+8=12$, $AD\&BC=6+3=9$. Route $=35+9=44$.

The travelling salesman problem (TSP) asks for the Hamiltonian cycle of least weight in a weighted complete graph. No quick exact algorithm is known, so we find bounds. If the practical problem is not a complete graph (some roads missing, or a shorter route exists via another vertex), first complete a table of least distances to make it a complete graph. Upper bound: nearest neighbour algorithm. From the start, go to the nearest unvisited vertex; repeat; return to the start. The tour is valid, so the optimum is at most its length. Try different starts to improve it. Lower bound: deleted vertex algorithm. Delete a vertex $v$; find the MST of the remaining graph; add the two shortest edges incident to $v$. Any tour contains such a structure, so the optimum is at least this total. Repeating with each vertex deleted and taking the largest gives the best lower bound. Example: with the distances in the exam question, nearest neighbour from $A$ gives $62$, deleting $E$ gives $54$, so $54\le L\le62$.

• Need a cheapest connected network (cables, pipes, roads)? Use a minimum spanning tree (Kruskal or Prim).
• Need to traverse every edge (street cleaning, post)? Chinese postman.
• Need to visit every vertex once and return (delivery, inspection)? Travelling salesman: give bounds. Justify the choice by stating what must be visited: every edge, every vertex, or just connect everything.