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).
See also
Adjacency List, Graph Bandwidth, Incidence Matrix, Integer Matrix, Weighted Adjacency Matrix
Portions of this entry contributed by Lorenzo Sauras-Altuzarra
Explore with Wolfram|Alpha
References
Chartrand, G. Introductory Graph Theory. New York: Dover, p. 218, 1985.Das, K.; Gutman, I.; Milovanović, I.; Milovanović, E.; and Furtula, B. "Degree-Based Energies of Graphs." Linear Algebra Appl. 554, 185-204, 2018.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 69-73, 2000.Goethals, J.-M. and Seidel, J. J. "Strongly Regular Graphs Derived from Combinatorial Designs." Can. J. Math. 22, 597-514, 1970.Skiena, S. "Adjacency Matrices." §3.1.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 81-85, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 6-9, 2000.Zheng, R.; Su, P.; and Jin. S. "Arithmetic-Geometric Matrix of Graphs and Its Applications." Appl. Math. Comput. 42, 127764, 1-11, 2023.
Referenced on Wolfram|Alpha
Cite this as:
Sauras-Altuzarra, Lorenzo and Weisstein, Eric W. "Adjacency Matrix." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AdjacencyMatrix.html