adjacency matrix

A Dictionary of Computing | 2004 | 700+ words | Copyright

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_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.

Cite this article
Pick a style below, and copy the text for your bibliography.

MLA
Chicago
APA

JOHN DAINTITH. "adjacency matrix." A Dictionary of Computing. 2004. Encyclopedia.com. 27 May. 2012 <http://www.encyclopedia.com>.

JOHN DAINTITH. "adjacency matrix." A Dictionary of Computing. 2004. Encyclopedia.com. (May 27, 2012). http://www.encyclopedia.com/doc/1O11-adjacencymatrix.html

JOHN DAINTITH. "adjacency matrix." A Dictionary of Computing. 2004. Retrieved May 27, 2012 from Encyclopedia.com: http://www.encyclopedia.com/doc/1O11-adjacencymatrix.html

Learn more about citation styles