Problem 1:

consider the following directed graph.

a) Find the vertex matrix of g.
b) Find the number of all paths of length 3.
c) Is the graph connected?
d) Find all paths of length 6 from $P_7 \rightarrow P_6$.
e) Find the number of all 4 step connections from $P_1$ to $P_3$.
f) Find all cliques of the graph g.
g) Is g a tournament graph?

Figure 18

Solution to Problem 1

a) The vertex matrix of g is $M=\left[ \begin{array}{rrrrrrr} 0&0&0&0&1&1&1\\ 1&0&1&1&1&0&0\\ 0&1&0&1&... ...\\ 0&0&0&0&0&0&0\\ 0&0&1&0&0&0&1\\ 0&0&0&0&0&1&0\\ \end{array} \right]$
b) All the paths of lengths 3 are listed below: List of all paths of length 3.

$P_1 \rightarrow P_6 \rightarrow P_3 \rightarrow P_2$
$P_1 \rightarrow P_6 \rightarrow P_3 \rightarrow P_4$
$P_1 \rightarrow P_6 \rightarrow P_7 \rightarrow P_6$
$P_1 \rightarrow P_7 \rightarrow P_6 \rightarrow P_3$
$P_1 \rightarrow P_7 \rightarrow P_6 \rightarrow P_7$
$P_2 \rightarrow P_1 \rightarrow P_6 \rightarrow P_3$
$P_2 \rightarrow P_1 \rightarrow P_6 \rightarrow P_7$
$P_2 \rightarrow P_1 \rightarrow P_7 \rightarrow P_6$
$P_2 \rightarrow P_3 \rightarrow P_2 \rightarrow P_1$
$P_2 \rightarrow P_3 \rightarrow P_2 \rightarrow P_5$
$P_2 \rightarrow P_3 \rightarrow P_2 \rightarrow P_4$
$P_2 \rightarrow P_3 \rightarrow P_2 \rightarrow P_3$
$P_2 \rightarrow P_3 \rightarrow P_4 \rightarrow P_2$
$P_2 \rightarrow P_3 \rightarrow P_4 \rightarrow P_3$
$P_2 \rightarrow P_4 \rightarrow P_2 \rightarrow P_1$
$P_2 \rightarrow P_4 \rightarrow P_2 \rightarrow P_3$
$P_2 \rightarrow P_4 \rightarrow P_2 \rightarrow P_4$
$P_2 \rightarrow P_4 \rightarrow P_2 \rightarrow P_5$
$P_2 \rightarrow P_4 \rightarrow P_3 \rightarrow P_2$
$P_2 \rightarrow P_4 \rightarrow P_3 \rightarrow P_4$
$P_3 \rightarrow P_2 \rightarrow P_1 \rightarrow P_5$
$P_3 \rightarrow P_2 \rightarrow P_1 \rightarrow P_6$
$P_3 \rightarrow P_2 \rightarrow P_1 \rightarrow P_7$
$P_3 \rightarrow P_2 \rightarrow P_4 \rightarrow P_2$
$P_3 \rightarrow P_2 \rightarrow P_4 \rightarrow P_3$
$P_3 \rightarrow P_2 \rightarrow P_3 \rightarrow P_2$
$P_3 \rightarrow P_2 \rightarrow P_3 \rightarrow P_4$
$P_3 \rightarrow P_4 \rightarrow P_2 \rightarrow P_1$
$P_3 \rightarrow P_4 \rightarrow P_2 \rightarrow P_3$
$P_3 \rightarrow P_4 \rightarrow P_2 \rightarrow P_4$
$P_3 \rightarrow P_4 \rightarrow P_2 \rightarrow P_5$
$P_3 \rightarrow P_4 \rightarrow P_3 \rightarrow P_2$
$P_3 \rightarrow P_4 \rightarrow P_3 \rightarrow P_4$
$P_4 \rightarrow P_2 \rightarrow P_1 \rightarrow P_5$
$P_4 \rightarrow P_2 \rightarrow P_1 \rightarrow P_6$
$P_4 \rightarrow P_2 \rightarrow P_1 \rightarrow P_7$
$P_4 \rightarrow P_2 \rightarrow P_4 \rightarrow P_2$
$P_4 \rightarrow P_2 \rightarrow P_4 \rightarrow P_3$
$P_4 \rightarrow P_2 \rightarrow P_3 \rightarrow P_2$
$P_4 \rightarrow P_2 \rightarrow P_3 \rightarrow P_4$
$P_4 \rightarrow P_3 \rightarrow P_2 \rightarrow P_1$
$P_4 \rightarrow P_3 \rightarrow P_2 \rightarrow P_3$
$P_4 \rightarrow P_3 \rightarrow P_2 \rightarrow P_4$
$P_4 \rightarrow P_3 \rightarrow P_2 \rightarrow P_5$
$P_4 \rightarrow P_3 \rightarrow P_4 \rightarrow P_2$
$P_4 \rightarrow P_3 \rightarrow P_4 \rightarrow P_3$
$P_6 \rightarrow P_3 \rightarrow P_2 \rightarrow P_1$
$P_6 \rightarrow P_3 \rightarrow P_2 \rightarrow P_3$
$P_6 \rightarrow P_3 \rightarrow P_2 \rightarrow P_4$
$P_6 \rightarrow P_3 \rightarrow P_2 \rightarrow P_5$
$P_6 \rightarrow P_3 \rightarrow P_4 \rightarrow P_2$
$P_6 \rightarrow P_3 \rightarrow P_4 \rightarrow P_3$
$P_6 \rightarrow P_7 \rightarrow P_6 \rightarrow P_3$
$P_6 \rightarrow P_7 \rightarrow P_6 \rightarrow P_7$
$P_7 \rightarrow P_6 \rightarrow P_3 \rightarrow P_2$
$P_7 \rightarrow P_6 \rightarrow P_3 \rightarrow P_4$
$P_7 \rightarrow P_6 \rightarrow P_7 \rightarrow P_6$

Number of paths of length 3

Compute $M^3= \left[ \begin{array}{rrrrrrr} 0&1&1&1&0&1&1\\ 2&2&4&3&2&1&1\\ 1&3&2&... ...\\ 0&0&0&0&0&0&0\\ 1&1&3&1&1&0&1\\ 0&1&0&1&0&1&0\\ \end{array} \right]$

Compute the sum of entries for each row and then add them to obtain $4+15 + 13+ 13+0+8+3=56$.

c) Is the graph connected?

The answer is NO, because there is no path from $P_5$ to any other point. Another way to check the connectivity of the graph is to compute the matrices $C = M + M^2 + \dots + M^6$. Graph is connected if and only if C has no zero entry.

$M=\left[ \begin{array}{rrrrrrr} 0&0&0&0&1&1&1\\ 1&0&1&1&1&0&0\\ 0&1&0&1&... ...\\ 0&0&0&0&0&0&0\\ 0&0&1&0&0&0&1\\ 0&0&0&0&0&1&0\\ \end{array} \right]$
and

$M^2 = \left[ \begin{array}{rrrrrrr} 0&0&1&0&0&1&1\\ 0&2&1&1&1&1&1\\ 1&1&2... ...\\ 0&0&0&0&0&0&0\\ 0&1&0&1&0&1&0\\ 0&0&1&0&0&0&1\\ \end{array} \right]$
and

$M^3= \left[ \begin{array}{rrrrrrr} 0&1&1&1&0&1&1\\ 2&2&4&3&2&1&1\\ 1&3&2&... ...\\ 0&0&0&0&0&0&0\\ 1&1&3&1&1&0&1\\ 0&1&0&1&0&1&0\\ \end{array} \right]$
and

$M^4 = \left[ \begin{array}{rrrrrrr} 1&2&3&2&1&1&1\\ 2&7&6&6&4&3&3\\ 3&5&7... ...\\ 0&0&0&0&0&0&0\\ 1&4&2&4&2&2&1\\ 1&1&3&1&1&0&1\\ \end{array} \right]$
and

$M^5 = \left[ \begin{array}{rrrrrrr} 2&5&5&5&3&2&2\\ 7&12&16&13&9&5&5\\ 5&... ...\ 0&0&0&0&0&0&0\\ 4&6&10&6&5&2&3\\ 1&4&2&4&2&2&1\\ \end{array} \right]$
and

$M^6 = \left[ \begin{array}{rrrrrrr} 5&10&12&10&7&4&4\\ 12&29&30&28&19&12&12... ...0&0&0&0&0&0&0\\ 6&16&14&16&10&7&6\\ 4&6&10&6&5&2&3\\ \end{array} \right]$
Since $C$ has one row of zero,namely the fifth row, the graph is not connected.

d)Find all paths of length 6 from $P_7 \rightarrow P_6$.

Compute $M^6 = \left[ \begin{array}{rrrrrrr} 5&10&12&10&7&4&4\\ 12&29&30&28&19&12&12... ...0&0&0&0&0&0&0\\ 6&16&14&16&10&7&6\\ 4&6&10&6&5&2&3\\ \end{array} \right]$

The $(7, 6)$ entry is 2. Therefore, there is two connections from $P_7$ to $P_6$, and they are:

$P_7 \rightarrow P_6 \rightarrow P_3 \rightarrow P_4 \rightarrow P_2 \rightarrow P_1 \rightarrow P_6$

$P_7 \rightarrow P_6 \rightarrow P_3 \rightarrow P_2 \rightarrow P_1 \rightarrow P_7 \rightarrow P_6$

e) Find the number of all 4 step connections from $P_1$ to $P_3$.

By investigation of the graph we can list all 4-step connections from $P_1$ to $P_3$:

$P_1 \rightarrow P_6 \rightarrow P_3 \rightarrow P_2 \rightarrow P_3$
$P_1 \rightarrow P_6 \rightarrow P_3 \rightarrow P_4 \rightarrow P_3$
$P_1 \rightarrow P_6 \rightarrow P_7 \rightarrow P_6 \rightarrow P_3$

We can also look at the (1,3) entry of $M^4$ which is equal to 3.

$M^4 = \left[ \begin{array}{rrrrrrr} 1&2&3&2&1&1&1\\ 2&7&6&6&4&3&3\\ 3&5&7... ...\\ 0&0&0&0&0&0&0\\ 1&4&2&4&2&2&1\\ 1&1&3&1&1&0&1\\ \end{array} \right]$

So the number of all 4 step connections from $P_1$ to $P_3$is 3.

f) Find all cliques of the graph g.

Use the graph to find the matrix

$S =\left[ \begin{array}{rrrrrrr} 0&0&0&0&0&0&0\\ 0&0&1&1&0&0&0\\ 0&1&0&1&... ...\ 0&0&0&0&0&0&0\\ 0&0&0&0&0&0&1\\ 0&0&0&0&0&1&0\\ \end{array} \right]$

Then compute the matrix

$S^3=\left[ \begin{array}{rrrrrrr} 0&0&0&0&0&0&0\\ 0&2&3&3&0&0&0\\ 0&3&2&3... ...0\\ 0&0&0&0&0&0&0\\ 0&0&0&0&0&0&1\\ 0&0&0&0&0&1&0\\ \end{array} \right]$ Therefore there is only one clique which is $C = \{ P_2, P_3, P_4 \}$

g) Is g a tournament graph?

The answer is No, because there are pair of points $P_i \leftrightarrow P_j$ holds, for example $P_6 \leftrightarrow \P_7$ holds.