Preliminaries

This is based on Section 11.7 in the text. You should read both this lab and the material in 11.7.

Basics

A graph (first studied by Euler) is a collection of elements (points, vertices) (P₁, P₂, ...) and ordered pairs (P_i,P_j) representing a connection (edge) from P_i to P_j. In a directed graph the order matters as the connection is one-way. In a general graph the connections are two-way. We can represent a graph (of either type) by either drawing it as a collection of points and edges, or, since the location of the points doesn't matter, as a matrix M where M_ij is 1 if there is an edge from P_i to P_j and 0 otherwise. For example, here's a graph an its matrix.

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.

Properties of M

The sum of each row is the number of edges from each vertex (called the degree). The sum of each column in the number of edges to each vertex (called the in-degree). The total number of 1s is the total number of edges (twice the number if the edges are two-way). In MATLAB you can compute these by sum(M) for the sum of the columns, sum(M') for the sum of the rows and sum(sum(M)) for the total number of 1s.
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² = M*M represents all the 2-step connections. For example there are 2 2-step connections in the graph above from 1 to 3, (1-2-3 and 1-4-3) and in M² the (1,3) entry is 2. Continuing this idea, M³ has all the 3-step connections, etc. So if a graph is connected then there is a connection of some length between every pair of vertices and that means that for each set of indices (i,j) there is a power k such that the (i,j) entry of M^k is non-zero. We can check this by computing the following:

     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⁵ term we get

     1     7    10     1     6
     0     6     7     0     4
     0     4     6     0     3
     0     5     7     1     4
     0     3     4     0     3

This 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*X

repeating 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.

Six Degrees of Separation and Six Degrees of Kevin Bacon

There is a theory that anyone on earth can be connected to any other person on the planet is a path of six steps or less. In mathematics, this means if we form the adjacency matrix for people then I + M + M² + M³ + M⁴ + M⁵ + M⁶ would not have any zeros in it.
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ⁿ is non-zero. Some fan has used a database of all movies to create such a matrix and to process this information (search for "Oracle of Kevin Bacon").

Exercises

1. Construct the adjacency matrices for the directed graphs in Figure Ex-5 in the book p. 627. Determine if each graph is connected or not. If it is connected, find the smallest value k such that you can reach any vertex from any other vertex in a path of k steps or less.

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.

---