The Mathematics of Graphs and their Games


The very word graph is a most confusing term. In fact, most of the special terminology of graph theory consists of familiar words that have special meaning in the context of graphs.

The concept of a graph is very simple to grasp, yet these mathematical objects are extremely varied. The specialized vocabulary for talking about graphs is most useful for trying to describe the various graphs and their properties.. Graphs are useful for modeling a wide variety of real-world situations.

Of course you can learn about graphs and their properties by studying them, but a much easier way to begin to understand them is by playing games.

Graph: a confusing term

When mathematicians talk about graphs, they are most likely to be thinking of the collections of dots and lines that you see in the illustrations of this section. Sometimes graphs are called networks, and a glance at pictures of them will show you why. The graphs of Graph Theory are not the same as the graphs which are used to plot or chart statistical information. The potential for confusion between these two very different kinds of objects that have the same name is unfortunate. When mathematicians talk about graphs, it is always clear from the context which type of graph they are considering.

The Vocabulary of Graphs

Of course there is a vocabulary of terms for talking about graphs. The following discussion of graph terminology is not a prerequisite for understanding graphs. (In fact students will quickly find graphs quite boring if they have to learn all these terms before they can do anything interesting with graphs!) The terms become quite useful, however, when students try to talk about their observations or their strategies for playing games. Familiarize yourself with these terms so that when students find themselves using round-about awkward constructions to try to explain something, you can supply word that are useful to describe it.

Each dot is called a vertex. The plural of vertex is vertices. (Although many excited young students experiencing graph games and puzzles for the first time use the word verticie as the singular of vertices!) The lines that connect the vertices are called edges. Edges can connect any or all of the vertices. Edges in a graph can cross one another without there being a vertex at the place where they cross, but edges cannot "hang loose" with no vertex on the very end.

The edges of a graph can be stretched, shrunk, pulled out of place, or deformed in any imaginable way and it will still be the same graph. All of the different representations of the same graph, are said to be isomorphic to one another.

Sometimes it is not so easy to tell that two graphs are isomorphic. It takes quite a bit of moving edges around to see that the graphs above are isomorphic. In fact, no one knows a reliable way to quickly determine quickly if two graphs, no matter how large they are, are isomorphic--although it is fun to experiment with graphs to see if they are isomorphic.


Mathematical Objects and their Properties

A graph is an example of a mathematical object. A number is the mathematical object that is probably the most familiar to everyone. Some other examples of mathematical objects are knots, maps, and finite state machines.

One way mathematicians try to understand objects is in terms of their properties. The number 6, for instance, is a positive, even number divisible by 3 and less than 10. These are properties of the number 6. We could list many more. Depending on what you are trying to find out, some properties of the object you are looking at are more useful than others.

Some Properties of Graphs

Three properties of graphs that are important in many problems are size, regularity, diameter.

The size of a graph is the number of vertices it has. A graph is regular if all of the vertices have the same degree. The degree of a vertex is the number of edges that touch it.

Mathematicians would use the term 3-regular to describe a graph in which all the vertices were of degree 3. 4-regular graphs have vertices of degree 4, and so on.

Just like the diameter of a circle measures the distance across a circle, diameter is a measure of distance between vertices in a graph. The idea of "distance" in a graph is different from the "distance" we commonly measure with a tape measure, however, because we can stretch or shrink the edges of a graph to be any length at all.

Imagine traveling from vertex to vertex along the edges of a graph. Each trip along one edge, no matter how long or short the edge happens to be, counts as one move. The distance from one vertex to another is the smallest number of moves that it takes to get there.

The diameter of a circle measures the distance between two points on the circle that are farthest apart. Similarly, the diameter of a graph is the distance between the two vertices of the graph that are farthest apart.

A Real-World Problem that Uses Graphs

The connecting dots and lines of graphs make the ideas in graph theory particularly useful to people who design computer systems. On the smallest end of the scale, a graph can be used to model the way that tiny pulses of electricity flow through the silicon chips that are built into electronic devices. In the big picture, a graph can model the ways that computing systems can be interconnected, even when the computers are located all over the world and connected by telephone wires and satellites. When graphs are used to model circuits for silicon chips or large computer systems, properties like size, regularity, and distance and diameter are important.

For example, imagine that you have been given the task of deciding how to link 12 computers together. Each one of these computers will use information that is generated by all the others, so that all of them will need to exchange information with each other. Unless each computer can be connected directly to all eleven of the other ones, the computers will have to interrupt the work that they are supposed to be doing just to relay messages. It would be nice if every computer could be connected to all of the others, but that can get expensive.

Suppose that each computer is made to be connected to only three others. Suppose further, that someone has figured out that the whole system can handle the traffic only if messages don't have to pass through more than two computers on their way to their destination. If messages have to pass through three or more computers, it is likely that the whole system will get bogged down because it is doing to much work just passing messages around. How will you decide how to plug these computers together?

When you try and solve such a problem, a good way to show these connections is with a graph. Draw the computers as vertices or dots and the connecting wires are edges or lines.

For this problem, ou will be trying to construct a graph that is 3-regular whose is not greater than three. With a little bit of experimentation, you can figure out how to connect all 12 computers so that these criteria are met.

Now suppose you are given a similar task, but instead of connecting computers, you have been asked to lay out where the electric impulses should go on a silicon chip. You are allowed to use only one side of the chip, because the other side of the chip is being used for something else. If any of your connections cross, the whole thing will short-circuit and be useless. It is quite a bit harder to find a way to draw the graph that represents the right set of connections.

This graph will be 3-regular and it's diameter will be 3, (just like the graph that you drew to connect the computers in the problem above) but it will have the additional property of being planar. That means that it can be drawn in a flat plane so that edges only touch each other at a vertex. If you can draw this graph without peeking at the the solution you should be triumphant! When you look at the solution, it is easy to verify that the graph is indeed 3-regular and planar. It may take some experimentation to verify that the diameter is also 3. Specifications about the relationship between degree and diameter in graphs occurs over and over again in questions that come up in computer system design.

Understanding Properties by Playing Games

It is difficult and confusing to pore over pictures of dots and lines and try to apply what you have memorized about graph properties to the graph that may happen to be in front of you. If you use a graph as a game board, however, and invent games with game pieces that move about it in a variety of ways, many of the properties of the graph will emerge as you develop strategies for playing the games.

The activities and stories wil help you do just that.

What next?