ISEGORIA / MATH ENCYCLOPEDIA
Graph theory: routes, trees, and networks
Shortest paths, spanning trees, and centrality.
Before you begin: Sets and elementary algorithms
Predict, manipulate, then check your reasoning against the example and question. Graphs illustrate the mathematics; they do not replace a proof.
1. Shortest paths
Dijkstra’s algorithm repeatedly settles the unsettled node with the smallest tentative distance, then tries to improve its neighbours’ labels. Raise the traffic weight on the downtown roads, add the diagonal shortcut from A to F, and click any node to see its route from S. Play to watch the frontier grow one settled node at a time.
Worked example. With traffic weight 1 and no shortcut, the distance from S to T is 12, reached by two different routes.
Watch out. With a negative edge weight, a settled label can later turn out too large, so Dijkstra’s algorithm can return wrong distances.
Why does the frontier stay optimal?
Any other path to the settled node must leave the settled set through some frontier node, whose label is already at least as large, and nonnegative weights can only add to it.
2. Minimum spanning trees
Kruskal’s algorithm takes edges from lightest to heaviest and keeps each one that does not close a cycle. Move the cut: the lightest edge crossing it always belongs to the minimum spanning tree. Change the weight of the candidate edge 5–8 to see when it enters the tree.
Worked example. Every spanning tree on these ten vertices has nine edges.
Watch out. Every spanning tree connects all vertices without cycles, but the tree path between two vertices need not be a shortest route.
Why does the lightest crossing edge belong to some MST?
If a minimum tree avoided it, adding it would close a cycle that crosses the cut again through a heavier or equal edge; swapping the two gives a tree that is no heavier.
3. Centrality and influence
Two groups are joined through the bridge node X. Add leaves to node C to raise its degree, and add direct links between the groups to give paths that avoid X. Choose which measure sets the node size; the bars compare all three measures on the drawn graph.
Worked example. At the default settings, the bridge X has degree 4, fewer than the hub C with its leaves, yet the highest betweenness, since every path between the groups passes through it.
Watch out. Centrality is a model choice, not a universal ranking.
Which measure rewards many direct neighbours?
Degree centrality counts immediate neighbours.