Matrix Representation of Graphs
Definition 1
Let’s assume that a graph $G(V,E)$ is given.
Degree Matrix
Let’s denote the degree $d(v_{i})$ of each vertex $v_{i}\in V$ simply as $d_{i}$. The following matrix is called the degree matrix of $G$ and is denoted as $D(G)$ or simply $D$.
$$ D(G) = \mathrm{diag} (d_{1}, \dots, d_{n}) = \begin{bmatrix} d_{1} & 0 & \cdots & 0 \\ 0 & d_{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_{n} \end{bmatrix} $$
Here, $\mathrm{diag}$ is a diagonal matrix.
Adjacency Matrix
The following square matrix is called the adjacency matrix of $G$ and is denoted as $A(G)$ or simply $A$.
$$ A = [a_{ij}] = \begin{cases} 1 &, ij \in E(G) \\ 0 &,ij \notin E(G) \end{cases} $$
The adjacency matrix has many discrete properties and maintains the form of a matrix, which allows for the application of various linear algebra theories. Especially, its eigenvalues are frequently mentioned in various models applying networks.
Incident Matrix
The following matrix is called the incident matrix of $G$ and is denoted as $M(G)$ or simply $M$.
$$ M = [m_{ij}] = \begin{cases} 1 &, \text{vertex } i \text{ is incident with edge } j \\ 0 &, \text{otherwise} \end{cases} $$
Directed Incident Matrix
Let’s assume $G$ is a directed graph. The following matrix is called the directed incident matrix of $G$ and is denoted as $N(G)$ or simply $N$.
$$ N = [n_{ij}] = \begin{cases} 1 &, \text{vertex } i \text{ is tail of edge } j \\ -1 &, \text{vertex } i \text{ is head of edge } j \\ 0 &, \text{otherwise} \end{cases} $$
Example
For the graph shown above, the following matrices are obtained.
$$ D = \begin{matrix} & v_{1} & v_{2} & v_{3} & v_{4} & v_{5} & v_{6} & v_{7} & v_{8} \\ v_{1} & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{2} & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{3} & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ v_{4} & 0 & 0 & 0 & 6 & 0 & 0 & 0 & 0 \\ v_{5} & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 \\ v_{6} & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ v_{7} & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} $$
$$ A = \begin{matrix} & v_{1} & v_{2} & v_{3} & v_{4} & v_{5} & v_{6} & v_{7} & v_{8} \\ v_{1} & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ v_{2} & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ v_{3} & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ v_{4} & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ v_{5} & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ v_{6} & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ v_{7} & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} $$
$$ M = \begin{matrix} & e_{1} & e_{2} & e_{3} & e_{4} & e_{5} & e_{6} & e_{7} & e_{8} & e_{9} & e_{10} \\ v_{1} & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{2} & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{3} & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ v_{4} & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ v_{5} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ v_{6} & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ v_{7} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} $$
For the directed graph shown above, the directed incident matrix is as follows.
$$ N = \begin{matrix} & e_{1} & e_{2} & e_{3} & e_{4} & e_{5} & e_{6} & e_{7} & e_{8} & e_{9} & e_{10} \\ v_{1} & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{2} & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{3} & 0 & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ v_{4} & 0 & 0 & -1 & -1 & -1 & 1 & 1 & 1 & 0 & 0 \\ v_{5} & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 0 \\ v_{6} & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 \\ v_{7} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & -1 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} $$
Wilson. (1970). Introduction to Graph Theory: p14. ↩︎