Adjacency Matrix

graph-theory data-structures

Definition

Adjacency Matrix

An adjacency matrix is a square matrix used to represent a finite graph $G=(V,E)$. For a graph with $|V|=n$ vertices, the adjacency matrix $A\in \{0,1{\}}^{n\times n}$ is defined such that:

$$A_{ij}=\{\begin{array}{ll}1& \text{if }\{v_i,v_j\}\in E\\ 0& \text{otherwise}\end{array}$$

Structural Properties

Symmetry: For undirected graphs, the matrix is symmetric ($A=A^{\top }$). In the case of weighted graphs, the entries $A_{ij}$ correspond to the scalar edge weights $w_{ij}$.

Complexity: The representation requires $O(|V{|}^2)$ space, making it most suitable for dense graphs. Checking the existence of a specific edge $(v_i,v_j)$ is highly efficient, requiring only $O(1)$ time.

Permutation Invariance: The structure of the graph is independent of the vertex ordering; however, changing the ordering results in a symmetric permutation of the matrix rows and columns ($A^{\prime }=PA{P}^{\top }$).