Problem 2:

a) Draw a diagram corresponding to the following vertex matrix.

$\left[ \begin{array}{rrrrr} 0&0&1&1&1\\ 0&0&1&0&1\\ 1&0&0&0&1\\ 0&0&1&0&1\\ 1&1&1&0&0\\ \end{array} \right]$
b) Find all paths of length 3 from $P_4$ to $P_2$.
c) Is the graph connected?
d) Find all the loops of link 4 from $P_4$ to $P_4$.
e) Find the number of all 4 step connections from $P_1$ to $P_2$.
f) Find all cliques of the graph g.
g) Is g a tournament graph?

solution to Problem 2

a) The diagram corresponding to the vertex matrix is

Figure 19

b) Compute the matrix $M^3$ :

$\left[ \begin{array}{rrrrr} 4&2&5&2&5\\ 2&1&4&2&4\\ 3&1&4&1&5\\ 2&1&4&2&4\\ 5&3&5&1&4\\ \end{array} \right]$
According to the forth row and the second column's entry, there is only one 3-step connection from $P_4$ to $P_2$, and it is $P_4 \rightarrow P_3 \rightarrow P_5 \rightarrow P_2$.

c) Compute $C= M +M^2 +M^3 +M^4$.

$\left[ \begin{array}{rrrrr} 16 & 8 & 21 & 7 & 21\\ 12 & 6 & 15 & 4 & 15 ... ...& 16\\ 12 & 6 & 15 & 4 & 15\\ 16 & 8 & 21 & 7 & 21\\ \end{array} \right]$

Since $C$ do not have any zero entry, the graph is connected.

d)Find all the loops of link 4 from $P_4$ to $P_4$.

Compute $M^4$:

$M^4 =\left[ \begin{array}{rrrrr} 10 & 5 & 13 & 4 & 13\\ 8 & 4 & 9 & 2 & 9\... ... & 3 & 9\\ 8 & 4 & 9 & 2 & 9\\ 9 & 4 & 13 & 5 & 14\\ \end{array} \right]$

Considering the matrix $M^4$, since $m_{12} = 2$, there are two ways to loop from $P_4$ back to itself, and they are:

$P_4 \rightarrow P_3 \rightarrow P_5 \rightarrow P_1 \rightarrow P_4$
$P_4 \rightarrow P_5 \rightarrow P_3 \rightarrow P_1 \rightarrow P_4$

Compute $M^4$:

e) Using the $( 1, 2)$ entry of $M^4$ we realize that the number of all 4 step connections from $P_1$ to $P_2$ is 5 and they are listed below:

$P_1 \rightarrow P_3 \rightarrow P_1 \rightarrow P_5 \rightarrow P_2$

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

$P_1 \rightarrow P_5 \rightarrow P_1 \rightarrow P_5 \rightarrow P_2$

$P_1 \rightarrow P_5 \rightarrow P_2 \rightarrow P_5 \rightarrow P_2$

$P_1 \rightarrow P_5 \rightarrow P_3 \rightarrow P_5 \rightarrow P_2$

f) Similar to part (f) of problem 1 . Find the matrix $S$ and compute $S^2$, then $P_i$ belongs to a clique if $s_{ii}$ in nonzero.then find out that the only clique is $C = \{ 1, 3, 5 \}$

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_3 \leftrightarrow \P_5$ holds.