Graphs and networks: the maths of things that are connected
Dots and lines, and a surprising amount of the modern world.
In this context a graph is not a chart. It is a collection of nodes (dots) joined by edges (lines). Cities joined by roads. People joined by friendships. Web pages joined by links.
Stripping a situation down to just what is connected to what turns out to be enormously powerful, because problems that look completely different become the same problem.
The bridges of Konigsberg
The city had seven bridges across a river, and a local puzzle: could you walk a route crossing every bridge exactly once? Nobody could, and nobody could explain why not.
In 1736 Euler solved it by throwing away almost everything. Distances did not matter. Shapes did not matter. Only which land masses connected to which. Reduced that way, the answer became provable.
This is often called the first theorem in graph theory. Notice what it did: converted an exhausting search over routes into a five-second count of odd numbers. Finding the right abstraction is most of the work.
Ideas that keep reappearing
- Degree - how many edges meet at a node. The whole bridges argument is about degree.
- Path - a route from one node to another.
- Cycle - a path that returns to where it started.
- Connected - whether you can get from any node to any other.
- Tree - a connected graph with no cycles. Family trees, file systems, decision trees.
- Weighted edges - edges carrying a number: distance, time, cost.
What it is used for
Shortest routes
Satnav is a weighted graph problem. Junctions are nodes, roads are edges, and the weight is time rather than distance - which is why the route offered is sometimes longer in miles. Dijkstra's algorithm, from 1956, is still what most of it rests on.
Social networks
People are nodes, friendships are edges. 'People you may know' is largely a matter of counting shared neighbours. The six-degrees idea is a claim that this graph has short paths between almost any two nodes, which large studies have broadly supported.
The web
Pages are nodes, links are edges. Google's original PageRank ranked a page by how many pages linked to it, weighted by how important those pages were - a definition that sounds circular and is made precise by repeated calculation over the graph.
Which connects directly to your own site: a page nothing links to is a node with no incoming edges, and in a link graph that means near-zero importance no matter what is written on it.
Scheduling and colouring
Exam timetabling: subjects are nodes, and two subjects share an edge if any student takes both. Assigning time slots so no student has a clash is exactly graph colouring - assigning colours so no two connected nodes match. The same algorithm schedules exams, allocates radio frequencies and assigns registers in a compiler.
The four colour theorem. Any map can be coloured with four colours so no two neighbouring regions match. Conjectured in 1852, proved in 1976 - and the proof required a computer to check 1,936 cases, which caused a genuine argument about whether a proof no human can read in full is still a proof.
Why the abstraction matters
Bridges, exam timetables, satnav and web search are unrelated as situations. As graphs, several of them are the same problem, so an algorithm written for one solves the others.
That is the recurring pay-off of abstraction in mathematics: work done once transfers everywhere the structure matches. It is also why 'when will I use this' is usually the wrong question - you will not use the bridges, you will use the shape of the reasoning.