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 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, 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 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.
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, 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 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.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
adjacency matrix