📂Graph Theory

Matrix Representation of Graphs

Definition ¹

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} $$