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.

Advertisements

Author: Joseph Nebus

I was born 198 years to the day after Johnny Appleseed. The differences between us do not end there.

13 thoughts on “A Summer 2015 Mathematics A To Z: graph”

  1. I am definitely not a mathlete. With the exception of statistics and logic. And still not mathlete in those areas (i “get” them more). So I love how your post gave the history of the bridges in Prussia and the mathematician who tried to prove the “crossing,” helping me to further understand this process. Linking math to history is right up my alley. Thanks!

    Like

    1. I’m quite happy you found it a useful comparison. I’m embarrassed to admit it’s not my own discovery, though. The bridges of Koningsburg are almost required as the introduction to graphs. But fortunately the bridges are historically correct and prime the intuition of most people for many graph theory questions.

      Like

Please Write Something Good

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s