Map Coloring and Conflict Resolution

This week we look at one of the big achievements in math, figuring out the minimum number of colors needed to permit adjacent countries to be shown in contrasting colors on any map, and connect it with a type of conflict resolution. Applications include efficient timetables for meetings, relatively peaceful assignments of students to cars for a field trip, and even putting as many types of fish as you can into the display window of a store that sells tropical fish. All of these applications have two steps: make a graph of the situation and then color that graph properly. We will explain the terms in italics in the rest of the post.

The fascinating mathematical fact here is that all these applications use exactly the same math.

Suppose that we want to color a map so that any two countries that share a border are different colors. The map shown below, from Carom Maths, a collection of math activities, illustrates the big result. First — four colors are always enough and, as their inset shows, sometimes four colors are required.

africa

A graph is a bunch of nodes connected by lines (which are called edges). Like this:

k44

To make a graph from a map we think of each country as a node in the graph and put a line between two nodes if the countries share a border. An example of a simple map and the corresponding graph are shown below. Turning a map into a graph is done to make a simple abstraction of the map that still contains all the information we need to color the countries to avoid the same color on both sides of any border. This property of having different colors on either end of an edge is the property that makes a coloring proper.

mapgraph

Once we’ve turned a map into a graph, we need only color the nodes of the graph so that any two nodes that are connected by an edge are different colors. Why not just color the map? One simple reason is that, if we need to fiddle with the colors a lot, the graph requires less ink and is easier to make a new copy of than the whole map. A more persuasive reason is that if we think of countries sharing a border as having a potential conflict because of their colors, the graph becomes a gateway to the general notion of using graphs for conflict resolution. Let’s look at this in light of the problem of assigning students to cars for a field trip.

The real application: keeping the peace on a field trip!

Checking with teachers, a person planning a school trip finds that the following pairs of students do not get along: Billy and Jen, Sherri and Thomas, Anne and Bob, Mark and Sue, Sue and Jen, Sherri and Mark, Jen and Thomas, and Bob and Tim. There are some students that don’t have conflicts with anyone, but they can be put wherever there is room. The students are represented by nodes in the graph and the edges are between any two students that have a conflict. Let’s make and color the graph:

transport

This picture shows that three colors are enough to permit nodes joined by an edge to be different colors. Each color is a car — because students that are the same color do not have a conflict — and so the cars work out like this.

  • Red car: Anne, Jen, Mark, Tim.
  • Green car: Bob, Sue, Thomas.
  • Blue car: Billy, Sherri

Three cars are needed — the fact that there is a pentagon in the graph forces this. If you could use two colors, then they must alternate, which gets stuck if there is any odd-length closed path. This is also not the only solution. It may be possible to use three colors without getting such uneven numbers of students in the cars — a nice example of a secondary factor in optimizing. See if you can manage a 3:3:3 distribution of these nine students?

What about meeting timetables and arranging fish in tanks?

Now that we have a good intuitive example, let’s see how this lets us deal with getting meetings done as fast as possible or putting tropical fish in a display window. Before reading on, can you guess how to do it yourself? Let’s present by analogy: meetings are analogous to students and conflicts are created by a person that must attend both meetings. Make a graph with meetings as nodes and edges when meetings have a person in common. A proper coloring of the graph gives you a plan (colors are different time slots for meetings) to schedule the meetings without conflicts. Minimize the number of colors and you minimize the amount of time needed, overall, for the meetings.

The tropical fish are similar. The nodes represent fish, conflicts are pairs of fish that will fight with or eat one another. The colors are fish tanks. After you properly color the (nodes=fish edges=conflict) graph, then any two fish assigned the same color have no conflict and can be in the same tank. Cool, no? The fish example brings up an additional issue. A loop is an edge from a node to itself. Since male Betas (Siamese fighting fish) attack one another, their node has an edge with itself, which has the special interpretation “no more than one of these in a tank.” A self-edge looks like this:

beta

If you start using this technique to map out and minimize potential conflicts, then you may run into the following fact. There are lots of different ways to present any given graph. This is another field of research called graph drawing. If you are a computer nerd, then the free software called GraphVis can do a pretty good job of drawing graphs for you. There are even graph drawing contests! The entries are programs that can turn a list of nodes and edges into a good drawing. GraphVis actually gives you lots of options for different ways to do this.

The graph you get from a map always can be drawn so that you never need to have two edges cross one another. This isn’t always the case. If you have five students who all have conflicts with one another, then there is no way to draw the conflict graph without crossing edges — but that doesn’t stop the conflict resolution technique from working. This issue has come up before in the post Believing Things are Impossible. Look for the utility problem.

Another thing Occupy Math has not yet mentioned is that the mathematical proof that four colors are enough to color a map was incredibly hard and quite controversial. The form of the proof is as follows. The core of the proof consisted of laboriously finding a list of maps with the property that, if they can all be colored in four or fewer colors, every map can be colored in four or fewer colors. The procedure would either color a map or create additional maps from the map under consideration that also needed to be colored. In the end thousands of maps had to be colored and it was done with a computer — the first ever computer proof. This was about 100 years after a couple of subtly incorrect proofs, by Alfred Kempe and Peter Tait appeared.

Occupy Math hopes that this post on graph theory and conflict resolution was interesting and will someday be helpful. Other graph theory posts in the past include topics like trying to bake cookies efficiently and the very recent post on influence mapping. All of this is part of Occupy Math’s attempt to make the point that graph theory — or any of a number of other topics — might be better “advanced math” for college and university students than math related to the physical sciences. Can you think of another situation where conflicts could be diagrammed with graphs? Please comment or tweet!

I hope to see you here again
Daniel Ashlock
University of Guelph
Department of Mathematics and Statistics

Advertisements

Leave a Reply

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