Adjacency matrix

Adjacency Matrix

An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal.

Definition

For a simple graph with vertex set U = {u1, u2, ..., un}, the adjacency matrix is a square n × n matrix A = [aij] where the elements aij is defined as:

aij = 1 if (ui, uj) is an edge,

aij = 0 otherwise.

If the graph is undirected (i.e., all its edges are bidirectional), the adjacency matrix is symmetric. The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory.

Properties

The adjacency matrix of a graph should be distinguished from its incidence matrix, a different matrix representation whose elements indicate whether vertex-vertex pairs are connected by an edge, and its degree matrix, which contains information about the degree of each vertex.

The adjacency matrix can be used to determine the number of simple paths between two vertices, it is used in the Floyd-Warshall algorithm, which finds shortest paths in a weighted graph. It can also be used to determine the degree of a vertex.

Variations

There are several different types of adjacency matrices including the normalized adjacency matrix and the Laplacian matrix. These variations have different properties and are used in different algorithms in graph theory.

See also

• Graph
• Matrix
• Graph theory
• Spectral graph theory
• Floyd-Warshall algorithm
• Degree