Graphs & networks

Look at a metro map: it does not show what the city really looks like. Streets are missing, distances are wrong, the lines are neatly straightened. Yet it guides you perfectly. That is because the map shows exactly what matters: which stations exist and which are directly connected. This way of looking at things is so useful that computer science gives it its own name: the graph.

Nodes and edges

A graph is made of two ingredients. The nodes are the things themselves: stations, people, computers. The edges are the connections between them: a track, a friendship, a network cable. That is all it takes. Where the nodes are drawn does not matter, only the connections count. Two drawings that look completely different can therefore show exactly the same graph.

Paths and shortest paths

A path through a graph is a sequence of edges that takes you from node to node, just like a metro ride from station to station. There are often many possible paths between two nodes, and then the shortest one is interesting: the one with the fewest edges. Exactly this question sits inside many everyday helpers. The navigation app searches for the shortest path in the road graph, though there it is not the number of edges that counts but their length: for that, each edge is given a number, its weight. Social networks, on the other hand, ask how many acquaintances it takes to reach someone.

Graphs are everywhere

Once you know graphs, you spot them everywhere. The internet is a graph of routers and links, and because there are usually several paths between two points, it keeps working even when a link fails. A social network is a graph of people and friendships. Even the web itself is one: pages are nodes, links are edges. Whoever can draw a problem as a graph can apply the same toolbox to it, above all the search for paths.