Adjacency Matrix

graph-theory data-structures

Definition

Adjacency Matrix

An adjacency matrix is a square matrix used to represent a finite graph . For a graph with vertices, the adjacency matrix is defined such that:

Structural Properties

Symmetry: For undirected graphs, the matrix is symmetric (). In the case of weighted graphs, the entries correspond to the scalar edge weights .

Complexity: The representation requires space, making it most suitable for dense graphs. Checking the existence of a specific edge is highly efficient, requiring only 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 ().