next up previous
Next: References Up: Problems Previous: Problem 1:

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

\includegraphics[width=4in]{GT_fig_19.eps}

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.


next up previous
Next: References Up: Problems Previous: Problem 1:
Ali A. Daddel 2000-09-17