Adjacency Matrix
The adjacency matrix, sometimes also called the connection matrix, of a simple labeled graph is a matrix with rows and columns labeled by graph vertices, with a 1 or 0 in position 
according
to whether 
and 
are adjacent
or not. For a simple graph with no self-loops, the adjacency matrix must have 0s
on the diagonal. For an undirected graph, the
adjacency matrix is symmetric.
The illustration above shows adjacency matrices for particular labelings of the claw graph, cycle graph 
, and complete graph 
.
Since the labels of a graph may be permuted without changing the underlying graph being represented, there are in general multiple possible adjacency matrices for
a given graph. In particular, the number 
of distinct
adjacency matrices for a graph 
with vertex
count 
and automorphism
group order 
is given by
 |
where 
is the number or permutations of
vertex labels. The illustration above shows the 
possible
adjacency matrices of the cycle graph 
.
The adjacency matrix of a graph can be computed in the Wolfram Language using AdjacencyMatrix[g], with the result being returned as a sparse array.
Contact the MathWorld Team
adjacency matrix of
trees
