Graph Representations and Matrices

Graph representations bridge combinatorial structures and linear algebra, enabling both efficient algorithms and powerful spectral analysis techniques. The choice of representation significantly impacts computational complexity and analytical capabilities.

DefinitionAdjacency Matrix

For a graph $G = (V, E)$ with $V = \{v_1, \ldots, v_n\}$ , the adjacency matrix $A(G) = [a_{ij}]$ is the $n \times n$ matrix where: $a_{ij} = \begin{cases} 1 & \text{if } \{v_i, v_j\} \in E \\ 0 & \text{otherwise} \end{cases}$

For undirected graphs, $A$ is symmetric. The matrix $A^k$ counts walks of length $k$ : entry $(A^k)_{ij}$ gives the number of walks from $v_i$ to $v_j$ using exactly $k$ edges.

The adjacency matrix has time complexity $O(n^2)$ for storage and $O(1)$ for edge existence queries, but $O(n^2)$ to iterate over all neighbors. This is inefficient for sparse graphs where $m \ll n^2$ .

DefinitionAdjacency List

An adjacency list representation stores for each vertex $v \in V$ a list $\text{Adj}(v)$ of its neighbors. Total space is $\Theta(n + m)$ , optimal for sparse graphs. Neighbor iteration takes $O(\deg(v))$ time, but edge existence queries require $O(\deg(v))$ .

ExamplePath Graph Representation

For the path $P_4$ with vertices $\{1,2,3,4\}$ and edges $\{\{1,2\}, \{2,3\}, \{3,4\}\}$ :

Adjacency matrix: $A = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$

Adjacency lists: $\text{Adj}(1) = \{2\}$ , $\text{Adj}(2) = \{1,3\}$ , $\text{Adj}(3) = \{2,4\}$ , $\text{Adj}(4) = \{3\}$ .

DefinitionIncidence Matrix

The incidence matrix $B(G) = [b_{ve}]$ is an $n \times m$ matrix where: $b_{ve} = \begin{cases} 1 & \text{if vertex } v \text{ is incident to edge } e \\ 0 & \text{otherwise} \end{cases}$

For directed graphs, we use $b_{ve} \in \{-1, 0, 1\}$ to indicate edge orientation.

DefinitionLaplacian Matrix

The Laplacian matrix $L(G) = D - A$ where $D$ is the diagonal degree matrix with $d_{ii} = \deg(v_i)$ . The Laplacian is positive semidefinite with: $L_{ij} = \begin{cases} \deg(v_i) & \text{if } i = j \\ -1 & \text{if } \{v_i, v_j\} \in E \\ 0 & \text{otherwise} \end{cases}$

Remark

The Laplacian eigenvalues encode deep structural information: the number of zero eigenvalues equals the number of connected components, and the second-smallest eigenvalue (algebraic connectivity) measures how well-connected the graph is. This connection between linear algebra and graph structure is central to spectral graph theory.

Matrix representations enable efficient algorithms (BFS, DFS, shortest paths) and provide tools for spectral analysis, random walks, and graph partitioning. The interplay between combinatorial and algebraic perspectives is a recurring theme in modern graph theory.