Tidbits of graphs

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


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.


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

Create a free website or blog at WordPress.com.

Up ↑

%d bloggers like this: