Adjacency Matrix/Connectivity Matrix/Reachability Matrix) Definition/Meaning:
A matrix used as a
means of representing 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 x m. If
A x A x ... x A
(p terms, p≤m)
is evaluated, the nonzero entries indicate those vertices that are joined by a
'path of length p; indeed the valued the i,jth 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 = l,2,...,m - l
it can be determined whether two vertices are connected.
It is also possible for adjacency matrices to
be formed from Boolean matrices.
|
