Graph Algorithms

An Eulerian trail is a walk through a graph that uses every edge exactly once. An Eulerian circuit is an Eulerian trail that starts and ends at the same vertex. Euler proved in 1736 (solving the Königsberg Bridge Problem) that an Eulerian circuit exists if and only if every vertex has even degree, and the graph is connected. An Eulerian trail (not a circuit) exists if and only if exactly two vertices have odd degree — these become the start and end points. The degree of a vertex is the number of edges incident to it. Check degrees first before attempting any route.

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle does the same and returns to the start. Unlike Eulerian circuits, no simple degree condition guarantees a Hamiltonian cycle — this is an NP-complete problem. Dirac's Theorem gives a sufficient (not necessary) condition: if every vertex in an n-vertex graph (n ≥ 3) has degree at least n/2, a Hamiltonian cycle is guaranteed to exist. In practice at school level, Hamiltonian cycles are found by inspection or with heuristic algorithms like nearest-neighbour.

A spanning tree of a connected graph is a subgraph that includes all vertices and is a tree (connected, no cycles). Its weight is the sum of its edge weights. Kruskal's algorithm finds the minimum spanning tree (MST) by a greedy edge-selection strategy: (1) List all edges in ascending order of weight. (2) Add the cheapest edge that does NOT create a cycle in the edges already selected. (3) Repeat until n−1 edges have been chosen (where n = number of vertices). The result is the MST. Checking for cycles can be done visually at school level; formally it uses a Union-Find data structure.

Prim's algorithm grows the MST one vertex at a time: (1) Choose any starting vertex; add it to the tree T. (2) From all edges connecting T to vertices NOT yet in T, select the minimum-weight edge and add it (and its new vertex) to T. (3) Repeat step 2 until all vertices are in T. Both Kruskal's and Prim's always produce the same MST weight (though the tree may look different if tie-breaking differs). Prim's is often easier to track in a table — note the current cheapest connection to each unvisited vertex and update as new vertices join.

A postman must traverse every street (edge) at least once and return to the start — minimising total distance. If the graph already has an Eulerian circuit (all vertices even degree), the optimal route simply follows that circuit. If some vertices have odd degree, we must repeat (duplicate) some edges to make all degrees even. The algorithm: (1) Identify all odd-degree vertices. (2) Find the minimum-weight perfect matching among them — i.e., pair them up so the total weight of shortest paths between pairs is minimised. (3) Add those paths as repeated edges. (4) Find an Eulerian circuit on the augmented graph. The minimum total route = (sum of all edge weights) + (weight of the minimum matching).

The TSP asks: given a complete weighted graph, find the Hamiltonian cycle of minimum total weight. This is NP-hard, so we use heuristics for large problems. The Nearest-Neighbour (NN) heuristic gives an upper bound: (1) Start at any vertex. (2) Move to the nearest unvisited vertex. (3) Repeat until all vertices are visited. (4) Return to the start. The result is a valid Hamiltonian cycle but not necessarily optimal. Applying NN from different starting vertices and taking the best result improves the bound.

To find a lower bound for TSP: (1) Delete one vertex (and all its edges) from the graph. (2) Find the MST of the remaining graph using Kruskal's or Prim's — call its weight W. (3) Add back the two cheapest edges that originally connected the deleted vertex to the rest of the graph — call their total weight C. (4) Lower bound = W + C. This bound is valid because any Hamiltonian cycle, when vertex v is removed, leaves a Hamiltonian path on the remaining vertices, which must be at least as heavy as the MST; and the cycle must also use at least 2 edges at v. Repeating for several deleted vertices and taking the largest lower bound gives the best (tightest) lower bound.

• W_{\text{MST}} — MST total weight (same as edge weights (e.g. km, £)): The sum of all edge weights in the spanning tree, which is minimised over all possible spanning trees.
• T — spanning tree edge set (dimensionless): The set of n−1 edges selected to form the minimum spanning tree.
• w(e) — edge weight (km, £, minutes, etc.): The numerical cost or distance assigned to each edge e in the graph.
• n — number of vertices (dimensionless): The total count of vertices (nodes) in the graph; a spanning tree always has exactly n−1 edges.

Problem. A weighted graph has 5 vertices: A, B, C, D, E. The edge weights are: AB=4, AC=2, AD=7, BC=5, BD=3, BE=6, CD=1, CE=8, DE=4. Apply Kruskal's algorithm to find the MST and state its total weight. Then find an upper bound for the TSP using the nearest-neighbour heuristic starting at A.

Answer. MST weight = 10 (edges CD, AC, BD, DE). Nearest-neighbour TSP upper bound starting at A = 21 (route A–C–D–B–E–A).

• Graph Theory Fundamentals — Understanding vertices, edges, degree, and types of graphs is essential before applying algorithms like Kruskal's or Prim's.
• Greedy Algorithms — Both Kruskal's and Prim's are greedy algorithms — they make the locally optimal choice at each step, which happens to produce a globally optimal MST.
• Network Flow and Optimisation — Network flow problems extend graph theory to maximising flow through a network, sharing the same framework of weighted directed graphs.
• Linear Programming — The TSP can be formulated as an integer linear programme; understanding LP helps appreciate why TSP is computationally difficult and how bounds are derived.
• Mathematical Modelling — Graph algorithms are a prime example of mathematical modelling — real-world logistics problems are abstracted into graphs so that algorithms can find optimal or near-optimal solutions.