adjacency matrix

Quick Reference

A matrix used as a means of representing an adjacency structure, which in turn represents a graph. If A is the adjacency matrix corresponding to a given graph G, then

aij = 1

if there is an edge from vertex i to vertex j in G; otherwise

aij = 0

If G is a directed graph then

aij = 1

if there is an edge directed from vertex i to vertex j; otherwise

aij = 0

If the vertices of the graph are numbered 1,2,…m, the adjacency matrix is of a type m×m. if

A×A×…×A (p terms, pm)

is evaluated, the nonzero entries indicate those vertices that are joined by a path of length p; indeed the value of the (i,j)th entry of Ap gives the number of paths of length p from the vertex i to vertex j. By examining the set of such matrices,

p = 1,2,…, m−1

it can be determined whether two vertices are connected.

It is also possible for adjacency matrices to be formed from Boolean matrices.

Subjects: Computing.

Reference entries