Adjacency matrix
Square matrix encoding vertex adjacency in a graph.
Last updated
An adjacency matrix is a square matrix that records which vertices of a graph are connected by edges.[1] For a simple graph, each matrix element is 1 if an edge exists and 0 otherwise, with zeros on the diagonal.[1] This matrix can also represent multigraphs, graphs with loops, and directed graphs by storing edge counts or using different conventions.[2][3]
Quick Facts
- Field
- Graph theory, computer science
- Definition
- Square matrix representing adjacency of vertices in a graph
- Key variants
- Biadjacency matrix
- Seidel adjacency matrix
- distance matrix
- Properties
- Symmetric for undirected graphs; eigenvalues studied in spectral graph theory
- Related matrices
- Incidence matrix, degree matrix
Facts from the source article.
Key facts and history
For a d-regular graph, d is the first eigenvalue λ₁, and its multiplicity equals the number of connected components.[4] For a simple undirected graph, the adjacency matrix is symmetric, which implies that its eigenvalues are all real and that there exists an orthogonal basis composed of eigenvectors.[5] The collection of a graph's eigenvalues is termed its spectrum, and these eigenvalues are typically ordered as λ₁ ≥ λ₂ ≥... ≥ λₙ.[5] In computer programs, the adjacency matrix serves as one possible data structure for graph representation.[6]
The adjacency list is the primary alternative data structure to the adjacency matrix.[6] Checking for the presence of an edge between two vertices is a constant-time operation with an adjacency matrix, but with an adjacency list it takes time proportional to the smaller of the two vertices' degrees.[7]
What the research sources say
The same source notes that for bipartite graphs, the eigenvalues come in opposite pairs.[8][4] The textbook "Introduction to Algorithms" (MIT Press, 2001) describes the adjacency matrix as one of two main data structures for graph representation, alongside the adjacency list.[9][6] This textbook also explains that finding all neighbors of a vertex requires scanning an entire row in an adjacency matrix, taking time proportional to the number of vertices.[9][7]
References
- Wikipedia, "Adjacency matrix" (CC BY-SA 4.0), which cites: Biggs, "Algebraic Graph Theory", Cambridge University Press, 1993 (original not read by us) en.wikipedia.org
- Wikipedia, "Adjacency matrix" (CC BY-SA 4.0), which cites: Harary, "The determinant of the adjacency matrix of a graph", SIAM Review, 1962, p. 202–210 (original not read by us) en.wikipedia.org
- Wikipedia, "Adjacency matrix" (CC BY-SA 4.0), which cites: Shum, "Expander graphs and codes", American Mathematical Society, 2003-12-18, p. 63 (original not read by us) en.wikipedia.org
- Wikipedia, "Adjacency matrix" (CC BY-SA 4.0), which cites: Brouwer, "Spectra of Graphs", Springer, 2012, p. 6–7 (we also read that source) en.wikipedia.org
- Wikipedia, "Adjacency matrix" (CC BY-SA 4.0), which cites: , Chapter 2 ("The spectrum of a graph"), pp. 7–13. (original not read by us) en.wikipedia.org
- Wikipedia, "Adjacency matrix" (CC BY-SA 4.0), which cites: , p. 361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."; Cormen, "Introduction to Algorithms", MIT Press and McGraw-Hill, 2001, p. 527–531 (we also read that source) en.wikipedia.org
- Wikipedia, "Adjacency matrix" (CC BY-SA 4.0), which cites: Cormen, "Introduction to Algorithms", MIT Press and McGraw-Hill, 2001, p. 527–531; Goodrich, "Algorithm Design and Applications", Wiley, 2015, p. 363 (we also read that source) en.wikipedia.org
- Open Library record, ISBN 9781461419389 ("Spectra of Graphs"). CC0 (metadata); book content not read. openlibrary.org
- Open Library record, ISBN 0262032937 ("Introduction to algorithms"). CC0 (metadata); book content not read. openlibrary.org
Each numbered sentence above was checked against the source it cites before publication. Sentences citing Wikipedia adapt text from the English Wikipedia article Adjacency matrix (contributors), used under CC BY-SA 4.0; this entry is available under the same licence. Other sources were used for facts only; no text or images are copied from them.
More in Mathematical Logic And Computation
Sources
Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.
- Wikipedia: Adjacency matrix (CC BY-SA 4.0).
- Word definitions: the , each quoted from its Wikipedia article.
Spotted an error? Know more?
Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced