Primer: graphs

Read first

• Nothing. This primer assumes no background beyond school arithmetic: adding distances and measuring a straight line between two points.

The question this primer answers: what is a graph, and which pieces of one (paths, cycles, trees, matchings) does routing keep coming back to?

Intuition

Every routing problem in this series starts the same way: a set of places, and a cost for travelling between each pair. A graph is the mathematical name for exactly that. The places are vertices (also called nodes), the connections are edges, and the number on an edge is its weight: a distance, a travel time or a cost.

Here are the eight stops used throughout the series. Coordinates are in kilometres.

A van can drive from any stop to any other, so every pair of stops has an edge. A graph like that is called complete. With 8 vertices it has 8 × 7 / 2 = 28 edges. We write all their weights down in a distance matrix: row A, column B holds the weight of edge A–B. The weight is the straight-line distance in units of 100 m, rounded, so A–B is √17 ≈ 4.12 km, written 41. In the heatmap below, short edges are light and long ones dark.

The matrix is symmetric: the entry for A→B equals the one for B→A. That makes the graph undirected: an edge is a two-way road with one weight.

The shapes routing cares about

A graph on its own is just a list of options. The things we look for inside it have names. Step through the diagram to see each one on the eight stops. The numbers on the edges are lengths in kilometres, so 4.12 on the map is 41 in the matrix.

The tour is the object the Traveling Salesman Problem asks for: in a tour every vertex has degree exactly 2. The tree and the matching come back in Post 5, where trees give lower bounds, and in Post 10, where Christofides’ algorithm combines exactly this tree and this matching.

Growing the minimum spanning tree by hand

How do you find the cheapest spanning tree among all of them? Grow it. Start with one vertex. Then repeatedly add the cheapest edge that joins a vertex already in the tree to one that is not. This rule is known as Prim’s algorithm. Step through it from A; filled stops are in the tree, green is the edge being added.

The tree weighs 259 and the optimal tour 315. That is no accident. Delete any one edge from a tour and what is left is a path through all eight stops, which is a spanning tree. So every tour weighs more than some spanning tree, and therefore at least 259. Post 5 builds a whole exact method on that idea.

When direction matters

Real roads are not always two-way. A one-way street can make the trip from H to D longer than the trip from D to H. Then the graph is directed: each edge has a direction, and the matrix is no longer symmetric. Post 1 uses exactly this example, with H→D at 50 while D→H stays 28.

flowchart LR
  D -->|"28"| H
  H -->|"50, one-way detour"| D

In a directed graph, an edge is usually called an arc, and a vertex has an in-degree and an out-degree instead of one degree.

The formal idea

A graph G = (V, E) is a set V of vertices and a set E of edges, each edge joining two vertices. In a weighted graph each edge e has a weight w(e). Write n = |V| for the number of vertices and m = |E| for the number of edges.

Two small facts get used later in the series. First, adding up the degrees of all vertices counts every edge twice, once at each end:

Σ over v ∈ V of deg(v) = 2m

So the sum of degrees is even, and the number of odd-degree vertices is always even. That is why the odd vertices of a tree can always be paired up into a perfect matching, the step Christofides’ algorithm relies on in Post 10. With four odd vertices you can simply try the three possible pairings; for many, Edmonds’ (1965) blossom algorithm finds the cheapest perfect matching in polynomial time. Second, a tree on n vertices has exactly n − 1 edges, so a spanning tree of berlin52 has 51.

Prim’s algorithm. The diagram below is the loop you ran by hand. It works because of the cut property: for any split of the vertices into two groups, the cheapest edge crossing between them belongs to some minimum spanning tree. Each step adds the cheapest edge across the split “in the tree / not in the tree”, so it never makes a choice it has to undo.

flowchart TD
  S["Tree = one vertex"] --> Q{"All vertices in tree?"}
  Q -- yes --> R["Return the tree"]
  Q -- no --> C["Cheapest edge, tree to non-tree"]
  C --> A["Add edge and its new vertex"]
  A --> Q

Keeping, for each outside vertex, its cheapest edge into the tree makes each step O(n), so the whole run is O(n²) on a complete graph. Vojtěch Jarník described this algorithm in 1930, in a letter-style paper following Otakar Borůvka’s 1926 solution of the same problem. Robert Prim rediscovered it in 1957, and Edsger Dijkstra published it again in 1959. Joseph Kruskal’s 1956 rule builds the same tree differently: sort all edges and take each one that does not close a cycle. His paper’s title already mentions the traveling salesman problem.

Storing a graph. A distance matrix stores all n² entries, which suits a complete graph. An adjacency list stores, for each vertex, only its neighbours and the weights of those edges, about n + m entries. That suits a road network, where each intersection touches only a few streets. A matrix grows with the square of the number of stops: 1,326 distinct pairs for berlin52’s 52, about 50 million for 10,000 stops, which is why large routing systems compute only the pairs they need.

Common misconceptions

“An edge in the distance matrix is a road.” In this series the matrix is a complete graph, and its edge A–H is “the cost of getting from A to H”, not a street. On a real map that cost comes from a different graph, the road network, where vertices are intersections and edges are street segments. A shortest-path algorithm such as Dijkstra’s (1959) runs on the road graph once per pair of stops to fill in the matrix. Routing therefore uses two graphs: a sparse road graph to compute costs, and a complete graph of stops to plan the order.

“The minimum spanning tree is unique.” Only when no two edges tie in a way that matters. On our eight stops, taking G–E instead of A–B at step 2 grows a different tree, A–G, G–E, E–D, D–H, C–D, B–C and E–F, that also weighs 259. The minimum weight is unique; the tree need not be.

“A shortest path visits all the stops on the way.” A shortest path from A to H only has to start at A and end at H; it may skip every other stop. On our matrix the cheapest way from A to H is the direct edge, 106 (A→D→H ties at 106). A tour has to visit everything and come back, which is a very different and much harder problem, as Post 1 and Post 2 show.

Try it in Python

The script builds the complete graph’s distance matrix from coordinates, grows the minimum spanning tree with Prim’s algorithm, and counts degrees. It does this for the eight stops and for berlin52, the 52-city instance the series uses throughout. You need berlin52.tsp from TSPLIB. Ties go to the lower-numbered vertex, so the output is reproducible.

import math
from collections import Counter

def distance_matrix(points, scale=1):
    """Complete graph: the weight of every pair, Euclidean distance rounded to an integer."""
    return [[int(scale * math.hypot(p[0] - q[0], p[1] - q[1]) + 0.5) for q in points] for p in points]

def prim(d):
    """Minimum spanning tree, grown from vertex 0 one cheapest edge at a time."""
    n = len(d)
    in_tree = [False] * n
    cost_to_tree, link = [math.inf] * n, [None] * n  # cheapest known edge from each vertex into the tree
    cost_to_tree[0] = 0
    edges = []
    for _ in range(n):
        v = min((u for u in range(n) if not in_tree[u]), key=lambda u: cost_to_tree[u])  # ties: lowest number
        in_tree[v] = True
        if link[v] is not None:
            edges.append((link[v], v))
        for u in range(n):
            if not in_tree[u] and d[v][u] < cost_to_tree[u]:
                cost_to_tree[u], link[u] = d[v][u], v
    return edges

def describe(name, d, optimum):
    n = len(d)
    tree = prim(d)
    weight = sum(d[a][b] for a, b in tree)
    degree = Counter(v for edge in tree for v in edge)
    odd = [v for v in range(n) if degree[v] % 2 == 1]
    print(f"{name}: {n} vertices, {n * (n - 1) // 2} edges in the complete graph, "
          f"MST {len(tree)} edges weighing {weight}, {sum(degree[v] == 1 for v in range(n))} leaves, "
          f"{len(odd)} odd-degree vertices, optimal tour {optimum}, MST/optimum {weight / optimum:.3f}")
    return tree, odd

stops = {"A": (2, 2), "B": (6, 1), "C": (9, 3), "D": (8, 7), "E": (5, 9), "F": (1, 8), "G": (4, 5), "H": (10, 9)}
names = list(stops)
d8 = distance_matrix(list(stops.values()), scale=10)  # units of 100 m
tree, odd = describe("eight stops", d8, 315)
print("  tree edges in the order Prim adds them:", ", ".join(f"{names[a]}-{names[b]}" for a, b in tree))
print("  odd-degree vertices:", ", ".join(names[v] for v in odd))

body = open("berlin52.tsp").read().split("NODE_COORD_SECTION")[1].split("EOF")[0]
xy = [tuple(map(float, ln.split()[1:])) for ln in body.strip().splitlines()]
describe("berlin52", distance_matrix(xy), 7542)  # EUC_2D

It prints:

For the eight stops it also prints the tree edges in the order of the hand-worked run, A-G, A-B, B-C, C-D, D-H, D-E, E-F, and the odd-degree vertices D, F, G and H.

On both instances the tree is a little over 80% of the optimal tour: a cheap, reliable lower bound, computed in O(n²). The number of odd-degree vertices is even on both, as the degree-sum fact promises. berlin52’s 22 odd vertices are the ones Christofides’ algorithm pairs up in Post 10.

Exercise

Find the minimum spanning tree of the eight stops again, this time with Kruskal’s rule: list all 28 edges from cheapest to most expensive, and go down the list taking each edge that does not close a cycle with the edges already taken. Stop when you have 7 edges. Do you get weight 259? Which edges does your tree contain, and is it the same tree Prim’s algorithm found?

Hint: the cheapest edge is D–H at 28, then three edges at 36. At 41 there are four edges, A–B, C–D, E–F and G–E, and the order in which you take tied edges decides which tree you end with. Check each one for a cycle before you take it.

Where to go next

• Primer B: algorithms and complexity explains what O(n²) means and why some problems grow much faster.
• Post 1: What is the TSP? defines the tour on the complete graph, and shows why a shortest path and a spanning tree are not tours.
• Post 5: Branch and bound turns the minimum spanning tree into the 1-tree lower bound.
• Post 10: Approximation algorithms combines the tree and a perfect matching into Christofides’ algorithm.

References

• Euler, L. (1741). “Solutio problematis ad geometriam situs pertinentis.” Commentarii Academiae Scientiarum Petropolitanae 8: 128–140. Presented to the St. Petersburg Academy in 1735; the Königsberg bridges problem, usually taken as the start of graph theory.
• Borůvka, O. (1926). “O jistém problému minimálním.” Práce Moravské přírodovědecké společnosti 3: 37–58.
• Jarník, V. (1930). “O jistém problému minimálním.” Práce Moravské přírodovědecké společnosti 6: 57–63.
• Kruskal, J. B. (1956). “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” Proceedings of the American Mathematical Society 7(1): 48–50.
• Prim, R. C. (1957). “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36(6): 1389–1401.
• Dijkstra, E. W. (1959). “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1: 269–271.
• Edmonds, J. (1965). “Paths, Trees, and Flowers.” Canadian Journal of Mathematics 17: 449–467.
• Edmonds, J. (1965). “Maximum Matching and a Polyhedron with 0,1-Vertices.” Journal of Research of the National Bureau of Standards 69B: 125–130.
• Graham, R. L., and Hell, P. (1985). “On the History of the Minimum Spanning Tree Problem.” Annals of the History of Computing 7(1): 43–57.
• Reinelt, G. (1991). “TSPLIB—A Traveling Salesman Problem Library.” ORSA Journal on Computing 3(4): 376–384; berlin52 files and list of optimal solutions.

See the whole series · ← All writing