The graphs we have been dealing with so far have been symmetric in the sense that if vertex a is related to vertex b then vertex b is related to vertex a. This will not always be the case as you will discover when we talk about directed graphs. Think of a relation between people defined by " a is related to b if a is taller than b ". That is surely not going to be symmetric. In such a case we shall call the edge a directed edge and we shall refer to a as the initial vertex and b as the terminal vertex. We now introduce the idea of a path and this time we will have a concept of direction.
A path of length n , n ≥1 , from vertex a to vertex b is a sequence of directed edges e_{1}, e_{2}, ...,e_{n} such that the initial vertex of e_{1} is a , and the terminal vertex of e_{n} is b, and for i=2, ..., n , the initial vertex of e_{i} is the terminal vertex of e_{i1} . When it is more convenient we shall list the vertices in order (rather than the edges) to represent the path. Since for the time being our relations are assumed to be symmetric, it means that if vertex a and vertex b are adjacent there is a path of length 1 from a to b and there is also a path of length 1 from b to a.
If a path starts and ends at the same vertex we say the path is a closed path. If a path does not visit any vertex more than once it is a simple path. A path that is both simple and closed is a cycle.
Java Web Start Activity:
To clarify the idea launch the Java Web Start application below and
draw a graph in the left pane like you have in other applications.
This time on the right side you have the adjacency matrix written on a
keypad. If you click on an entry (green box) with a
1
on it the corresponding path of length
1
will be traced out on the graph.
Recall from your linear algebra classes that you can sometimes multiply matrices together. (When?). If you multiply an adjacency matrix A by itself you get a new matrix A². Remember that if A is an n x n matrix and B = A² then the entries b_{i,j} of B are obtained as
Therefore b_{i,j} = 1 if and only if there is a vertex k with a_{i,k} = 1 and a_{k,j} = 1. Well this is the same as saying that there is a path of length 2 from vertex i to vertex j. So we can conclude that b_{i,j} is the number of paths of length 2 from i to j. (If i = j then you just get the degree of the vertex).
Java Web Start Activity:
Launch the Java Web Start application below and draw a graph in the
left pane. This time on the right side you have the square of the
adjacency matrix,
A
^{
2
}
written on a keypad. If you click on an entry (green box) the
corresponding paths of length
2
will be traced out on the graph.
 How are the entries on the leading diagonal of A^{2} related to the degrees of the vertices?
 If A is the adjacency matrix of the complete graph K_{n}, what will be value of the entries on the leading diagonal of A^{2}?
 If a graph has an odd number of vertices why is it impossible for all the entries on the leading diagonal of A^{2} to be ones?
 For any graph why is it impossible to have an odd number of odd entries on the leading diagonal of A^{2}?
 From your observations, what does the trace of A^{2} represent?
Java Web Start Activity:
The Java Web Start application below will allow you to examine the
relationship between the cube of the adjacency matrix and paths of
length
3.
Java Web Start Activity:
The Java Web Start application below will allow you to examine the
relationship between the
n^{th}
power of the adjacency matrix and paths of length
n.
Use the
+
and

buttons to change the value of
n.
Java Web Start Activity:
In the programming exercise you will be asked to list all the paths of
a given length
n
from a chosen start vertex to a chosen end vertex in an arbitrary
graph. One way to do that is by using a backtracking algorithm. Study
the way that the Java Web Start application below works to get ideas
on how you will implement your algorithm.
Programming Task
Answers
© C. Mawata