A graph (first studied by Euler) is a collection of elements (points,
and ordered pairs (Pi
) representing a connection
(edge) from Pi
. 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 Mij
1 if there is an edge from Pi
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,
for the sum of the rows and sum(sum(M))
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 M2
= 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 M2
the (1,3) entry is 2. Continuing this idea, M3
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 Mk
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 M5
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
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 + M2
would not have any zeros in
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 + ... + Mn
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").
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.