隣接行列
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/06/25 07:00 UTC 版)
グラフ理論および計算機科学において、隣接行列（りんせつぎょうれつ、英: adjacency matrix）は、有限グラフを表わすために使われる正方行列である。この行列の要素は、頂点の対がグラフ中で隣接しているか否かを示す。
- ^ Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library (2nd ed.), Cambridge University Press, Definition 2.1, p.7.
- ^ Harary, Frank (1962), “The determinant of the adjacency matrix of a graph”, SIAM Review 4 (3): 202-210, Bibcode: 1962SIAMR...4..202H, doi:10.1137/1004057, MR0144330.
- ^ Seidel, J. J. (1968). “Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3”. Lin. Alg. Appl. 1 (2): 281-298. doi:10.1016/0024-3795(68)90008-6.
- ^ Shum, Kenneth; Blake, Ian (18 December 2003). "Expander graphs and codes". Volume 68 of DIMACS series in discrete mathematics and theoretical computer science. Algebraic Coding Theory and Information Theory: DIMACS Workshop, Algebraic Coding Theory and Information Theory. American Mathematical Society. p. 63.
- ^ Biggs (1993), Chapter 2 ("The spectrum of a graph"), pp.7–13.
- ^ Godsil, Chris; Royle, Gordon Algebraic Graph Theory, Springer (2001), ISBN 0-387-95241-1, p.164
- ^ Goodrich & Tamassia (2015), p.361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."
- ^ a b c Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), “Section 22.1: Representations of graphs”, Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, pp. 527-531, ISBN 0-262-03293-7.
- ^ Turán, György (1984), “On the succinct representation of graphs”, Discrete Applied Mathematics 8 (3): 289-294, doi:10.1016/0166-218X(84)90126-4, MR749658.
- ^ McKay, Brendan, Description of graph6 and sparse6 encodings.
- ^ a b Goodrich, Michael T.; Tamassia, Roberto (2015), Algorithm Design and Applications, Wiley, p. 363.
隣接行列
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/14 07:02 UTC 版)
I を単位行列、J を matrix of ones（英語版）（全成分が1の行列）で、いずれも v 次（行列）であるとする。強正則グラフの隣接行列 A は2つの方程式を満たさねばならない。まず、 A J = J A = k J {\displaystyle AJ=JA=kJ} これはグラフの正則性を述べなおした自明な関係である。これより、k は隣接行列の固有値で、全成分が1のベクトルがそれに対する固有ベクトルであることがわかる。 次は2次式の関係式で、グラフの強正則性を表す。 A 2 = k I + λ A + μ ( J − I − A ) {\displaystyle {A}^{2}=k{I}+\lambda {A}+\mu ({J-I-A})} 左辺の ij-成分は、頂点 i から頂点 j への長さ2の道の本数を表す。右辺の最初の項は頂点 i を自分自身と結ぶ、つまり k 本の「出」と「入り」の辺の数である。第2項は頂点 i と頂点 j が隣接しているときに、2辺でこれらを結ぶ道の本数を表す。第3項は頂点 i と頂点 j が隣接していないときの本数である。これら3つの場合は排他的で、かつ全てを尽くしているから、単純に和をとって等式が得られる。 逆に、グラフの隣接行列がこれら2条件を満たし、完全グラフでも空グラフでもないとき、強正則グラフである。
※この「隣接行列」の解説は、「強正則グラフ」の解説の一部です。
「隣接行列」を含む「強正則グラフ」の記事については、「強正則グラフ」の概要を参照ください。
隣接行列と同じ種類の言葉
- 隣接行列のページへのリンク
