Graph Theory

The matrix is called a vertex or adjacency matrix and for a directed graph it is called an incidence matrix.

Sometimes graphs are described by giving the set of objects and a rule for them having an edge. For example, we could take all GSS students as our points and then say there is an edge between two people if they knew each other before comming to GSS. Or we could take the set of all counting numbers less than 1000 and say there is an edge between two numbers if they have a common factor > 1. It may be hard to draw such graphs, but it can be pretty easy to create the adjacency matrix M.

A graph is connected if you can go along the edges from any vertex to any other vertex. If we think of M as representing all the 1-step connections, then M

eye(5) + M + M^2 + M^3 + M^4 + M^5 + ...using as many terms as we need (we start with eye(5) as we assume each vertex is connected to itself). For our graph above, going up to the M

1 7 10 1 6 0 6 7 0 4 0 4 6 0 3 0 5 7 1 4 0 3 4 0 3This tells us that there are 7 paths of length 5 or less from vertex 4 to vertex 3, but that there are no paths from vertex 2, 3, 4, or 5 to vertex 1. If we keep using higher powers, we will find there is no connection between some vertices and thus this graph is not-connected.

In MATLAB, one way to check this is to do the following after you've entered M:

I = eye(5); X = I + M X = I + M*X X = I + M*X X = I + M*Xrepeating the statement X = I + M*X until either all entries are non-zero or it becomes clear that some entries will never become non-zero.

The Six Degrees of Kevin Bacon game is a version of this where you try to connect any actor to Kevin Bacon in 6 steps or less, where 2 actors are connected if they appeared in the same film. In this case, we'd form the adjacency matrix for actors and then for a particular actor (say he's number k and Kevin Bacon is number 1), we'd want to find the smallest power n so that the (1,k) entry of I + M + ... + M

2. Construct the adjacency matrix for the numbers 1-24, where 2 numbers
are connected if they have a common factor larger than 1,
i.e. if their GCD is > 1.
Each connection is two-way, so for example, since 8 and 12 have a common
factor of 4
then both the (8,12) and the (12,8) entries of M should be set to 1.

Determine the number of edges in this graph.

Clearly this graph is not connected since 1 and primes larger than 12
don't connect with any other numbers. Still,
find out which number(s) have the most connections with other numbers
for paths of length 1, 2 and 3.