## 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

*a** _{ij}* = 1

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

*a** _{ij}* = 0

If *G* is a directed graph then

*a** _{ij}* = 1

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

*a** _{ij}* = 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, *p*≤*m*)

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 *A** ^{p}* 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.