# adjacency matrix

**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 *a _{ij}* = 1

if there is an edge from vertex

*i*to vertex

*j*in

*G*; otherwise

*a*= 0

_{ij}If

*G*is a directed graph then

*a*= 1

_{ij}if there is an edge directed from vertex

*i*to vertex

*j*; otherwise

*a*= 0

_{ij}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*gives the number of paths of length

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

#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**adjacency matrix**