A Summer 2015 Mathematics A To Z: graph

Graph. (As in Graph Theory)

When I started this A to Z I figured it would be a nice string of quick, two-to-four paragraph compositions. So far each one has been a monster post instead. I’m hoping to get to some easier ones. For today I mean to talk about a graph, as in graph theory. That’s not the kind of graph that’s a plot of some function or a pie chart or a labelled map or something like that.

This kind of graph we do study as pictures, though. Specifically, they’re pictures with two essential pieces: a bunch of points or dots and a bunch of curves connecting dots. The dots we call vertices. The curves we call edges. My mental model tends to be of a bunch of points in a pegboard connected by wire or string. That might not work for you, but the idea of connecting things is what graphs, and graph theory, are good for studying.

The field traces its origins back to early-18th-century Königsburg, Prussia (now Kaliningrad, Russia) where seven bridges spanned the river Preger and some islands in the river. The question that occurred to anyone walking around them would be: is it possible to walk over each bridge in a single trip, and get back to where you started, without using any bridge twice? You can’t; Leonard Euler, taking time out from proving everything else in mathematics, proved that you couldn’t.

The field really got organized in the 1930s, although the bridges of Königsburg is probably the best intuitive introduction you’ll get. We still use the metaphor of travelling from island to island across bridges when talking about graphs. Each bridge is an edge. Each plot of land has a vertex somewhere on it. The bridge problem becomes “is it possible to start at some vertex, and visit every other vertex on a path that uses every edge one and only one time?” Part of graph theory is answering when you can, and when you can’t.

If these vertices and edges aren’t interesting enough for you, you can add a restriction: make some of the bridges one way. That is, you can specify that some edges may be travelled in one direction, or the other, or both. This created a “directed graph”, since some or all of the edges allow movement in only some directions. If “directed graph” is too hard to say we might say “digraph” instead.

And if that’s not interesting enough we can draw from bridges again and imagine there’s a cost to using a bridge. If we add to the edges of a graph (or digraph) some cost, some weight, which is imposed for using that edge then we have something called a “network”.

Graph theory and its spinoff fields allow us to study questions about how things are connected, and how they can pass things from one to the other. And it’s a fun field because you can do a lot of work by drawing pictures, yet you don’t have to be any good at drawing.