Adjacency matrix (vertex matrix)

Graphs can be very complicated. We can associate a matrix with each graph storing some of the information about the graph in that matrix. This matrix can be used to obtain more detailed information about the graph. If a graph has $n$ vertices, we may associate an $n\times n$ matrix $M$ which is called vertex matrix or adjacency matrix. The vertex matrix $M$ is defined by

$$M_{ij} = \left\{ \begin{array}{ll} 1 & \mbox{ if } P_i \rightarrow P_j \\ 0 & \mbox{ otherwise }\\ \end {array} \right.$$

Example: The following is a simple example of a graph with vertices $P_1, P_2, P_3$. We want to find the vertex matrix for this graph.

Figure 13

Define the vertex matrix $M$ as follow:

$${ P_1 \rightarrow P_2} \rightarrow {m_{12} = 1 }$$

,

$${ P_1 \rightarrow P_3} \rightarrow {m_{13} = 1 }$$

,

$${ P_2 \rightarrow P_3} \rightarrow {m_{23} = 1 }$$

and the rest of the entries are zero.
So the adjacency matrix or vertex matrix M is $\left[ \begin{array}{rrr} 0&1&1\\ 0&0&1\\ 0&0&0\\ \end{array} \right]$

Example: Find the vertex matrix for the following graph.

Figure 14

Assigning 1 to all $M_{ij}$ that there is directed edge from $P_i$ to $P_j$ and $0$ to the other entries we obtain the vertex matrix.

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

Note: :

It can be proved that if M is the vertex matrix of a digraph, then the entry ${m_{ij}}^{(r)}$ will show the number of r-step connections from $P_i$ to $P_j$.

Example: Consider the following graph.
a) Find the vertex matrix M of the following graph.
b) Find the number of 3 step connection (or paths of length 3) from $P_2$ to $P_5$.
c) Find the number of 1, 2 or 3-step connections from $P_3$ to $P_2$.

Figure 15

a) Find the vertex matrix M of the following graph.

solutions a) Find the vertex matrix M of the following graph.

$M= \left[ \begin{array}{rrrrr} 0&1&0&1&1\\ 1&0&1&1&0\\ 0&0&0&1&1\\ 1&0&1&0&1\\ 0&0&0&0&0\\ \end{array} \right]$
b) Find the number of 3 step connection (or paths of length 3) from $P_2$ to $P_5$.
Here is a list of 3-step connection from $P_2$ to $P_5$.
But the number can be obtained by computing $M^3$.

i) $P_2 \rightarrow P_3 \rightarrow P_4 \rightarrow P_5$
ii) $P_2 \rightarrow P_4 \rightarrow P_3 \rightarrow P_5$
iii) $P_2 \rightarrow P_4 \rightarrow P_1 \rightarrow P_5$
iv) $P_2 \rightarrow P_1 \rightarrow P_4 \rightarrow P_5$

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

Since the entry $M_{2 5} =4$, there is four 3-step connection from $P_2$ to $P_5$.
You can find the number of all 3-step connections from any point to other points just from looking at $M^3$.

Similarly you can compute $M^n$ for $n= 1, 2, 3, \cdots$, to find the number of $n$-step path.

c) Find the number of 1, 2 or 3-step connections from $P_3$ to $P_2$.
1-step connection - none, because $M_{32}=0$, or just simply from the graph.
2-step connection - none, because $M^2_{32}=0$, or just simply from the graph.
3-step connection - 2, because $M^3_{32}=2$. Or just simply from the graph.