image
Graph Theory Lessons

rule

previous index next Lesson 11: Paths in Graphs

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 e1, e2, ...,en such that the initial vertex of e1 is a , and the terminal vertex of en is b, and for i=2, ..., n , the initial vertex of ei is the terminal vertex of ei-1 . 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 = then the entries bi,j of B are obtained as

product of matrices .

Therefore bi,j = 1 if and only if there is a vertex k with ai,k = 1 and ak,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 bi,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.


Questions:
  1. How are the entries on the leading diagonal of A2 related to the degrees of the vertices?
  2. If A is the adjacency matrix of the complete graph Kn, what will be value of the entries on the leading diagonal of A2?
  3. If a graph has an odd number of vertices why is it impossible for all the entries on the leading diagonal of A2 to be ones?
  4. For any graph why is it impossible to have an odd number of odd entries on the leading diagonal of A2?

The trace of a matrix A is the sum of the elements along the leading diagonal,

Trace of matrix .

Question:
  1. From your observations, what does the trace of A2 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.


Questions:
  1. From your observations, what does the trace of A3 represent?
    Hint: I would first study some small graphs like
    triangle graph
    Fig 11.1
    diamond graph
    Fig 11.2
    complete graph K(4)
    Fig 11.3

Java Web Start Activity:
The Java Web Start application below will allow you to examine the relationship between the nth 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