What is Graph Theory?

Occupy Math has done several posts that use a part of mathematics called graph theory. Occupy Math was trained in graph theory and his university is finally getting a course in graph theory which he gets to teach next winter! In the last ten years Occupy Math has taught reading courses in graph theory four times, because students needed the material to do their research. This is done as an overload, extra work with no comp time or added pay. Graph theory is really useful, showing up in everything from urban planning to particle physics, and getting to teach it to a whole class again will be wonderful.

A graph is just dots (called vertices) with some pairs of dots connected by lines (called edges). The graph at the top of the post is remarkable, for reasons we will get into a little later. A list of Occupy Math’s posts that use graph theory appears near the end of this post. Graph theory is one of the simplest types of advanced math to learn. In Cookies or Calculus, Occupy Math argues that graph theory is easier than calculus and — except for STEM students — more useful than calculus. Graph theory includes the study of networks, like contact networks in an epidemic, or influence networks in social or business situations. Graph theory is useful in some types of conflict resolution. This post is the first in a series that will introduce the power and beauty of graph theory.

Just dots connected by lines?

The lines connecting the dots can be arrows that show a direction. If the lines have a cost or represent a distance, we may put numbers on the lines. We may color the dots, to show different categories of dots, e.g. “men and women” in a social network or “8:00, 10:00 and 12:00 meetings” in a conflict resolution graph. Mostly, though, graph theory is the study of collections of dots with some of the pairs of dots connected by lines. In spite of this simplicity, there are tens of thousands of scholarly publications on graph theory.

Graph theory needs a lot of words. A path in a graph is a sequence of vertices (the math name for the dots) so that the dots, in the order given, are pairs connected by edges. If a path begins and ends at the same place, we call it a cycle. This gives us the words we need to explain why the graph at the top of the post is special. It has thirty vertices, each vertex is at the end of three edges, and the shortest cycle in the graph is an octagon (has eight vertices in it). Check — all the closed paths in the graph are length eight or more. Among graphs with three edges ending at each vertex, this graph has the smallest number of vertices that allows the shortest cycles to be length eight. This may seem pretty abstract, but this graph is connected in a way that makes it very spread out — which means it can be used to design communications network connectors that spread out messages as efficiently as possible across a data or telephone network. Weird, abstract properties often imply useful real world properties in graph theory.

A simple, useful application of graph theory

Imagine that the graph above — with numbers representing distances on its edges — is a simplified version of a map of all the bus stops in a small town. If, after a blizzard, we want to get the buses running as fast as possible, then it would be nice to know the shortest possible collection of roads to plow. The darkened collection of edges, above, is exactly that. A very simple set of rules can be used to find this collection of roads to plow:

1. Start by picking the shortest edge (road segment).
2. Among the remaining edges, pick the shortest one that does not create a closed loop of roads.
3. Repeat step 2 until everything is connected.

This set of rules is called Kruskal’s algorithm. It is easy to see that it will connect everything — Kruskal also proved that no other collection of street choices can find a shorter connecting network than the one produced by his algorithm. There are many algorithms for finding this sort of shortest connecting network — Kruskal’s is the easiest to explain, in Occupy Math’s opinion.

Graph Theory appears as a tool in epidemiology.

Contact networks or graphs are representations of how a disease is spread. These graphs are used all the time when trying to figure out epidemics. Occupy Math, with his students Lisa Shiller and Colin Lee, won the best paper award at the 2011 Congress on Evolutionary Computation, against a field of 811 papers, for a paper entitled Comparison of Evolved Epidemic Networks with Diffusion Characters. The core of this paper was a system for using digital evolution to fit graphs to the progress of an epidemic. The graphs in this question are contact graphs. The vertices are people and the edges are contacts that might spread the disease.

We often know how many people get sick in a week, but the pattern of contacts is almost impossible to reconstruct. Occupy Math’s project is to locate connection networks that are likely to have produced the observed infection numbers. These graphs (the technique finds many plausible contact graphs) can then be used to model interventions. You use the collection of plausible contact networks to game different techniques for slowing down or stopping the disease next time. This project is ongoing. Joseph Brown and I are working on modeling best-case and worst-case scenarios for the spread of a disease in a small group, given a fixed number of contacts. This is to help figure out rules for how strict a lockdown is needed during a pandemic.

Some graph theory puzzles

Here are some puzzles to get you started on graph theory. These are serious math problems, but they are also pastimes in case you are currently not allowed to go out for some reason. Occupy Math has the answers (dashlock@uoguelph.ca) if you want to know if you got these problems right.

1. You invite at least three strangers to an event. You make some introductions. Show that at least two people must have been introduced to the same number of people, no matter how you make the introductions. When diagramming this problem, the people are the vertices and introductions form edges.
2. Suppose that you have the numbers 1, 2, 3, 4, 5, 6 in circles on a piece of paper. These are your vertices. Make edges connecting even numbers to odd numbers, but one edge may not cross another or cross a vertex. What is the largest number of edges you can draw?
3. Put five dots on a piece of paper. Connect as many of the dots with lines (you may use curved lines) as you can. Same rules as Puzzle 2 for lines crossing things: what is the largest number of lines you can draw?
4. The graph shown above is famous for having no cycles shorter than length 5. What is the longest cycle in this graph? It cannot be more than length ten, because there are only ten vertices.
5. Suppose that, in a group of people, every pair of people is either acquainted or not acquainted. How may people are needed before there must be either three mutual acquaintances or three mutual strangers? For this, vertices are people and edges are acquainted pairs. What you want is either a 3-cycle or to find three people with no connections between any of them. Remember — this must be forced by the number of people, no matter how the patterns of acquaintanceship are laid down.

The graph in Puzzle 4, called the Petersen graph, is actually famous for a lot of reasons. A whole book was written about it and its cousins in graph theory.

Past Occupy Math Posts Using Graph Theory

Here is the promised graph theory sampler or earlier Occupy Math posts.

• Cookies or calculus introduces critical path planning in the context of baking chocolate chip cookies. The post argues for teaching graph theory rather than calculus as the required math course for non-STEM students in university.
• Can you draw this? shows the graph theory that lets you know ahead of time if it is possible to draw a shape without lifting your pencil.
• Believing things are impossible gives examples of graph theory problems that cannot be solved — but seem like they should be solvable. This is an important lesson for problem solvers.
• Organization Math: Influence Maps shows how graphs can be used to diagram things like the influence rock groups had on one another’s music. It also suggests techniques for determining who the key individuals are in a group.
• Map Coloring and Conflict Resolution introduces the famous four-color problem in map coloring and shows its relationship to conflict resolution.
• Unsolved Mysteries: What is the Chromatic Number of the Plane? presents an unsolved coloring problem which has the odd property that almost all the progress has been made by amateur mathematicians.
• Euler’s Map Theorem, a Surprising Activity presents an activity for home math or math class enrichment. The exercise is not complex, but it demonstrates a subtle universal behavior of maps — even maps the students make up for themselves.
• Graph Puzzles to Sharpen Your Skills uses graphs to generate a whole bunch of arithmetic practice puzzles. It is based on Dr. Peter Hamilton’s Bovine Math exercises.

More graph theory in the future!

Graph theory includes so many topics that it will take several posts to do even a moderate sampler platter of the available topics. Today’s post tries to give the basic definitions and establish that the field is useful. Future posts will look at trees, colorings, counting problems, cages, hypercubes, and map abstractions for use in games. If you have a graph theory topic you are interested in, please mention it in the comments.

I hope to see you here again,
So remember to wash your hands,
Daniel Ashlock,
University of Guelph,
Department of Mathematics and Statistics

 

Advertisement