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 corresponding
to a given simple graph. In particular, the number 
of distinct adjacency matrices for a simple unlabeled
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 labeled 
-digraph 
is the binary square matrix
of order 
whose 
th
entry is 1 iff 
is an edge of 
.
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.
A different version of the adjacency is sometimes defined in which diagonal elements are 
and 
if 
and 
are adjacent and 
otherwise (e.g., Goethals and Seidel 1970).
A weighted adjacency matrix 
of a simple graph can also be defined for a real positive
symmetric function 
on the vertex degrees 
of a graph (Das et al. 2018, Zheng et al. 2022).
