Read More
Date: 6-5-2022
![]()
Date: 23-3-2022
![]()
Date: 18-3-2022
![]() |
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.
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).
Chartrand, G. Introductory Graph Theory. New York: Dover, p. 218, 1985.
Devillers, J. and A. T. Balaban (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.
|
|
في الشهر العالمي للمناعة.. تعرف على دور اللقاحات في الحماية
|
|
|
|
|
بعد حادث نادر.. سحب صواريخ "فالكون 9" من الخدمة
|
|
|
|
|
العتبة العباسية تنهي أعمال واجهة شباك في الصحن العلوي المطهر
|
|
|