adjacency matrix

views updated

adjacency matrix (connectivity matrix; reachability matrix) 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.