隣接行列

辺の重みと多重辺を持たない無向グラフ	左のグラフに対する 4x4-隣接行列
	${\begin{array}{r\|c}&{\begin{matrix}1&2&3&4\end{matrix}}\\\hline {\begin{matrix}1\\2\\3\\4\end{matrix}}&{\begin{pmatrix}0&1&0&0\\1&0&1&1\\0&1&0&0\\0&1&0&0\\\end{pmatrix}}\end{array}}$
	$A={\begin{pmatrix}0&0&12&60&0\\10&0&0&0&0\\0&20&0&32&0\\0&0&0&0&0\\7&0&0&0&0\\\end{pmatrix}}$
辺の重みを持ち、多重辺を持たない有向グラフ	左のグラフに対する隣接行列
	$A={\begin{pmatrix}0&3&0&0\\2&0&4&0\\0&0&0&1\\0&0&2&0\\\end{pmatrix}}$
辺の重みを持ち、多重辺を持つ有向グラフ	ループを持たない左のグラフの可約隣接行列

グラフ理論および計算機科学において、隣接行列（りんせつぎょうれつ、英: adjacency matrix）は、有限グラフを表わすために使われる正方行列である。この行列の要素は、頂点の対がグラフ中で隣接（英語版）しているか否かを示す。

有限単純グラフの特別な例では、隣接行列はその対角上に0を持つ (0,1)-行列（英語版）である。もしグラフが無向ならば、隣接行列は対称である。グラフとその隣接行列の固有値および固有ベクトルとの間の関係はスペクトラルグラフ理論において研究される。

隣接行列はグラフに関する接続行列および次数行列と区別されなければならない。接続行列は、その要素が頂点-辺の対が接続しているか否かを示す行列表現であり、次数行列は個々の頂点の次数に関する情報を含む行列表現である。

定義[編集]

頂点の組Vを持つ単純グラフについて、隣接行列はその要素A'_ijが頂点iから頂点jへの辺が存在する時は1、辺が存在しない時は0であるような |V| × |V|正方行列Aである^[1]。この行列の対角要素は全て0である（単純グラフでは頂点からそれ自身への辺〈ループ（英語版）〉は許されないため）。また、代数的グラフ理論において代数変数を持つ非ゼロ要素を置換するために有用なこともある^[2]。

同じ概念は2つの頂点間の辺の数を対応する行列要素に格納することや非ゼロの対角要素を許容することによって多重グラフ（英語版）やループを持つグラフへと拡張することができる。ループは、一貫した慣習に従っている限り、1回（単一の辺）数えても2回（2つの頂点-辺接続として）数えてもよい。無向グラフはループを2回数える後者の慣習を使用することが多いが、有向グラフは通常前者の慣習を使用する

2部グラフ[編集]

2つの部分がr個とs個の頂点を持つ2部グラフの隣接グラフAは以下の形式で書くことができる。

A={\begin{pmatrix}0_{r,r}&B\\B^{T}&0_{s,s}\end{pmatrix}},

上式において、Bはr × s 行列、0_r,rおよび0_s,sはr × rおよびs × sゼロ行列を表す。この場合、より小さな行列Bがグラフを一意に表し、Aの残りの部分は冗長として捨てることができる。Bはbiadjacency行列と呼ばれることがある。

形式的に、G = (U, V, E)を部分U = {u₁, …, u_r}およびV = {v₁, …, v_s}を持つ2部グラフとする。Biadjacency行列は、 (u_i, v_j) ∈ Eの時かつその時に限りb_i,j = 1のr × s 0–1行列Bである。

Gが2部多重グラフまたは重み付きグラフならば、要素 b_i,jは頂点間の辺の数、または辺(u_i, v_j)の重みをそれぞれ取る。

バリエーション[編集]

単純グラフの (a, b, c)-「隣接行列」は、(i, j) が辺ならばA_i,j = a、辺でなければb、対角上にcを持つ。セイデル隣接行列（英語版）は(−1, 1, 0)-「隣接行列」である。この行列は強正則グラフとツーグラフ（英語版）の研究で使われる^[3]。

距離行列は、位置 (i, j) に頂点v_iと v_jとの間の距離を有する。この距離は頂点を連結する最短の道の長さである。辺の長さが明示的に与えられていない限り、道の長さは道中の辺の数である。距離行列は隣接行列の高冪と似ているが、2つの頂点が連結しているかどうか（すなわち、真偽値を含む連結行列）だけを教える代わりに、頂点間の正確な距離を与える。

例[編集]

無向グラフ[編集]

ここでは（無向グラフについて）、それぞれの辺が行列中の適切なセルに1を加え、それぞれのループが2を加えるという慣習に従う^[4]。これによって、隣接行列中のその対応する行または列中の値の和を取るとによって頂点の次数を容易に見付けることが可能である。

ラベル付きグラフ（英語版）	隣接行列
	${\begin{pmatrix}2&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{pmatrix}}$ 座標は1–6。
ナウルグラフ（英語版）	座標は0–23。白い場は0、色付けされた場は1である。

有向グラフ[編集]

有向グラフでは、頂点の入次数は対応する列の成分の和を取ることによって計算でき、出次数は対応する行の成分の和を取ることによって計算できる。

ラベル付きグラフ	隣接行列
S₄の有向ケイリーグラフ	座標は0–23。グラフが有向であるため、隣接行列は必ずしも対称ではない。

自明なグラフ[編集]

完全グラフの隣接行列は、成分が0の対角要素以外は全て1を含む。空グラフの隣接行列はゼロ行列である。

性質[編集]

スペクトル[編集]

無向単純グラフの隣接行列は対称であり、したがって実固有値および直交固有ベクトル基底の完全集合を持つ。グラフの固有値一式はグラフのスペクトルである^[5]。通常、固有値を $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ と表す。

最大固有値 $\lambda _{1}$ は最大次数によって上に有界である。これはペロン＝フロベニウスの定理の結果として見ることができるが、容易に証明することができる。vを $\lambda _{1}$ と関連した1つの固有ベクトルとし、xをvが最大の絶対値を持つ成分とする。一般性を失うことなくv_xは正と仮定する。なぜならさもなければ、単純に（これも $\lambda _{1}$ と関連した）固有ベクトル $-v$ を取ると、

\lambda v_{x}=(Av)_{x}=\sum _{y=1}^{n}A_{x,y}v_{y}\leq \sum _{y=1}^{n}A_{x,y}v_{x}=v_{x}\deg(x)

となるためである。

d次正則グラフについて、dはベクトルv = (1, …, 1)に対するAの最初の固有値である（これが固有値であり、上界により最大値であることを調べることは簡単である）。この固有値の多重度はGの連結成分の数であり、具体的には連結グラフでは $\lambda _{1}>\lambda _{2}$ である。もしGが2部グラフならば、それぞれの固有値 $\lambda _{i}$ について、その反数 $-\lambda _{i}=\lambda _{n+1-i}$ もAの固有値である^[要出典]。具体的には、-dは2部グラフの固有値である。

差 $\lambda _{1}-\lambda _{2}$ はスペクトルギャップと呼ばれ、Gの展開（英語版）と関連している。また、スペクトルギャップは、 $\lambda (G)=\max _{|\lambda _{i}|<d}|\lambda _{i}|$ によって示される $A$ のスペクトル半径を導入するためにも有用である。この数は $\lambda (G)\geq 2{\sqrt {d-1}}-o(1)$ で境界がある。この境界はラマヌジャングラフにおいてタイトである。ラマヌジャングラフは多くの分野に応用を持つ。

同型写像と不変量[編集]

隣接行列A₁およびA₂を持つ2つの有向または無向グラフG₁およびG₂が与えられると仮定する。G₁およびG₂は、

PA_{1}P^{-1}=A_{2}

というような置換行列Pが存在する時かつその時に限り同型である。

具体的には、A₁およびA₂は相似であり、したがって同一の最小多項式、固有多項式、固有値、行列式、跡を有する。したがってこれらは、グラフの同型不変量として機能する。しかしながら、2つのグラフは同じ固有値の組を持つかもしれないが、同型ではない^[6]。こういった線型作用素は等スペクトル（英語版）的と言われる。

行列の冪[編集]

Aが無向または有向グラフGの隣接行列とすると、行列Aⁿ（すなわちAのn個の複製の積）は興味深い解釈を持つ: 要素(i, j)は頂点iから頂点jへの長さnの（有向または無向）歩道の数を与える。nが、あるi、jについてAⁿの要素(i, j)が正となるような最小の非負整数とすると、nは頂点iと頂点jとの間の距離である。これは、例えば、無向グラフG中の三角形の数が厳密にA³の跡を6で割った数となることを暗に示す。ここで留意すべきは、隣接行列はグラフが連結しているかどうかを決定するために使うことができることである。

データ構造[編集]

隣接行列は、グラフを操作するためのコンピュータプログラムにおけるグラフの表現のためのデータ構造として使うことができる。この応用のためにも使われる主な代替データ構造は隣接リストである^[7]^[8]。

隣接行列中の各成分は1ビットしか必要としないため、隣接行列は非常にコンパクトなやり方で表すことができ、有向グラフを表わすためにはわずか|V |²/8バイト、無向グラフを表わすためには（パック三角形式を用い、行列の下部三角部分のみを格納することによって）わずか約 |V |²/16しか占めない。わずかにより簡潔な表現も可能であるものの、この方法は全ての $n$ 頂点グラフを表すために必要な最小ビット数の情報理論的下界に近付く^[9]。テキストファイルにグラフを格納するためには、全てのバイトがテキスト文字であることを（例えばBase64表現を使うことによって）保証するためにバイト毎により少ないビットした使うことができない^[10]。無駄な空間を避けることに加えて、このコンパクトさは参照の局所性を促す。しかしながら、大きな疎グラフ（英語版）では、隣接リストの方が必要とする格納空間が小さい。これは、隣接リストは存在「しない」辺を表わすためのいかなる空間も無駄にしないためである。

隣接行列の別形式（しかし、より大きな空間量を必要とする）は行列の個々の要素中の数を（辺が存在する時は）辺オブジェクトへのポインタあるいは（辺が存在しない時は）ヌルポインタで置き換える^[11]。また、辺の重みを隣接行列の要素中に直接格納することも可能である^[8]。

空間のトレードオフに加えて、異なるデータ構造は異なる操作をも容易にする。隣接リスト中の任意の頂点に隣接する全ての頂点を探すことはリストを読むのと同じぐらい単純であり、隣の数の比例した時間がかかる。隣接行列を使うと、代わりに全行をスキャンしなければならず、これはグラフ全体の中の頂点の数に比例したより長い時間がかかる。一方、任意の2つの頂点間に辺が存在するかどうかを調べるのは隣接行列を使うと瞬時に決定することができるのに対して、隣接リストを使うと2つの頂点の最小次数に比例した時間を要する^[8]^[11]。

出典[編集]

^ 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, MR 0144330 .
^ 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 .

外部リンク[編集]

『隣接行列，接続行列，ラプラシアン行列』 - 高校数学の美しい物語

[1] Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library (2nd ed.), Cambridge University Press, Definition 2.1, p.7 .

[2] 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, MR 0144330 .

[3] 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.

[4] 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.

[5] Biggs (1993), Chapter 2 ("The spectrum of a graph"), pp.7–13.

[6] Godsil, Chris; Royle, Gordon Algebraic Graph Theory, Springer (2001), ISBN 0-387-95241-1, p.164

[7] Goodrich & Tamassia (2015), p.361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."

[clrs-8] 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 .

[9] 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 .

[10] McKay, Brendan, Description of graph6 and sparse6 encodings .

[gt-11] Goodrich, Michael T.; Tamassia, Roberto (2015), Algorithm Design and Applications, Wiley, p. 363 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

辺の重みと多重辺を持たない無向グラフ	左のグラフに対する 4x4-隣接行列
	${\begin{array}{r\|c}&{\begin{matrix}1&2&3&4\end{matrix}}\\\hline {\begin{matrix}1\\2\\3\\4\end{matrix}}&{\begin{pmatrix}0&1&0&0\\1&0&1&1\\0&1&0&0\\0&1&0&0\\\end{pmatrix}}\end{array}}$
	$A={\begin{pmatrix}0&0&12&60&0\\10&0&0&0&0\\0&20&0&32&0\\0&0&0&0&0\\7&0&0&0&0\\\end{pmatrix}}$
辺の重みを持ち、多重辺を持たない有向グラフ	左のグラフに対する隣接行列
	$A={\begin{pmatrix}0&3&0&0\\2&0&4&0\\0&0&0&1\\0&0&2&0\\\end{pmatrix}}$
辺の重みを持ち、多重辺を持つ有向グラフ	ループを持たない左のグラフの可約隣接行列