In graph theory, a graph is a bunch of points (nodes) and lines connecting them (edges).

graph.PNGYou can use it to represent all kinds of information – cities, where the edges are roads, for example. Ways around a city block. It’s a pretty versatile system for representing data, and has all kinds of useful applications, but here I’m going to look at the graphs themselves, and some interesting properties they possess.

The formal way to represent a graph is with an adjacency matrix – it’s simply a matrix where the coordinate (i,j) tells you how many edges connect node i to node j. The adjacency matrix for this graph would be

graphAdj.PNG

Notice that, as there are no nodes with multiple edges between them, there are only 1’s and 0’s, and because no nodes connect to themselves, the main diagonal only has 0’s. Also notice that it is symmetrical about the diagonal – the entry (i,j) is the same as (j,i), because they both essentially mean the same thing, the number of edges between i & j, the order isn’t relevant. Once you have a graph in this form, you can do all kinds of useful things to it – for example, say I want to walk from 1 to 10 in exactly 7 steps. How many ways can I do this?

As it turns out, there’s a really neat trick that lets you find out. So you want to find how many 7 step walks there are between a and b? Simply raise the adjacency matrix to the power of 7, then go to the entry (a,b), or (b,a), and it’ll be the number of 7 step walks from a to b. Raising the above matrix to the power of 7 gives

Power of matrix

If we go to (1,10) or (10,1) We find that there are 7 ways to go from node 1 to node 10 in 7 steps. It’s fairly obvious that this extends more generally – to find the number of n steps walks between points a and b, raise the adjacency matrix to the power n, and the entry (a,b) will be the number of walks.

Advertisements