## Graph Theory 101

3/31/2011

Last time, we talked about the problem presented in the beginning of the film Good Will Hunting.  I said that it was an easy problem, and now I'll show you just how easy it is!

But first, let's learn a little bit about graph theory.  The graphs we use in graph theory don't use an x-axis and a y-axis.  We don't have functions of x or variables that change over time.

Graph theory graphs chart relationships.  In our Bridges of Konigsberg video, we looked at what would happen if we wanted to walk around a city, crossing every bridge exactly once and returning home.  If I wanted to draw the city of Konigsberg as a graph, I would draw each land mass as a dot and connect the dots with lines to represent the bridges.  Likewise, I could represent the people at a party by drawing a dot for each person and drawing lines to connect people who are friends with each other.  These types of graphs are very useful for solving problems relating to networks, scheduling, and planning routes.

In the problem at the beginning of Good Will Hunting, we're given the graph above. Each vertex (dot) is labeled with a number.  The edges (lines) connect the vertices in a pattern.  The first thing we are asked to do with this graph is:

An adjacency matrix is simply a way of writing down which vertices are connected by edges.  We'll make a little 4x4 table and write the number of edges connecting each vertex to each other vertex:
If we then wanted to know how many edges connect vertices 2 and 3, we just find the column for 2 and the row for 3 (or vice versa--it doesn't matter) and follow them until they meet--at the number 2.  That means that 2 edges connect 2 and 3 (which you'll see is true if you look at the graph).  If this seems confusing, just think of it like your old multiplication table.  To find out what 6x7 was you had to find the 6 column and the 7 row and find where they met.

You'll notice there's some redundancy in this matrix.  We really only need half of it, cut along the diagonal.  But, mathematicians like things to be square, so this is what we've got!

The second task asked of us is to create "The matrix giving the number of 3 step walks."  This sounds confusing, but if we think of ourselves as walking around on the graph, we just need to figure out how many ways we can get from one vertex to another by taking three steps.  Each step is just a move to the next vertex--and the vertices have to be connected by edges, or else we can't walk there.  It's kind of like a little board game.  We'll make a 4x4 table to chart our findings, just like last time.  So if I wanted to start making my table, I'd figure out how many 3-step walks I can take from vertex 1 and end up back at 1 again.  If I look back at my graph, I'll see that I have two choices: I can go from 1 to 2 to 4 and back to 1, or I can go from 1 to 4 to 2 and back to 1.  Any other walk would take too many steps.  To get from 1 to 2, I can go from 1 to 2 to 3 and back to 2 four different ways (remember, we can walk the same edge more than once).  See if you can find all four ways.  Then find the three other ways you can get from 1 to 2.  We build it this way, and the matrix for the number of 3-step walks will look like this:
So, as you can see, the first two parts of the problem are easy.  They just involve reading the graph and counting.  The second two parts, which ask for some generating functions, are a bit more advanced.  But we can understand the concept behind them even if we can't do the math.  If you want to see how to do the math, you can see the solution here.

We'll start by looking at the last part of the problem: "Find the generating function for walks from points 1 to 3."  All this is really asking is to find a nice way to count all the walks (of any length) we could take from point 1 to 3.  Of course, this will be a huge number--there are 12 walks of length 3 alone!  The good news is, we don't have to give the actual number (it would be infinite anyway since we could take walks of any length we wanted).  We just have to figure out how to express that number.  So the generating function from walks from point 1 to 3 involves adding up all the walks of length 1, length 2, length 3, and so on.

For the third part of the problem, "Find the generating function for walks from point i to j," we are asked to find the way to write the number of walks of any length for any two vertices--i and j are just used to represent any two points on the graph.

So there you go!  You're well on your way to becoming a graph theorist.