隣接行列

グラフ理論とコンピュータサイエンスにおいて、隣接行列は有限グラフを表すために使用される正方行列です。行列の要素は、グラフ内で 頂点のペアが隣接しているかどうかを示します。

有限単純グラフの特殊なケースでは、隣接行列は対角線上にゼロを持つ(0,1) 行列です。グラフが無向の場合(つまり、すべての辺が双方向の場合)、隣接行列は対称です。グラフとその隣接行列の固有値と固有ベクトルの関係は、スペクトルグラフ理論で研究されています。

グラフの隣接行列は、接続行列 （頂点と辺のペアが接続されているかどうかを要素が示す別の行列表現）および次数行列 （各頂点の次数に関する情報を含む）と区別する必要があります。

頂点集合U = { u ₁ , …, u _n }を持つ単純グラフの場合、隣接行列はn  ×  nの正方行列Aで、その要素A _{ijは、頂点}u _iから頂点u _jへの辺がある場合に 1 になり、辺がない場合に 0 になります。^[1]行列の対角要素はすべて 0 です。これは、単純グラフでは頂点からその頂点自身への辺 (ループ) が許可されていないためです。代数グラフ理論では、非ゼロ要素を代数変数に置き換えることが便利な場合もあります。^[2]同じ概念を、対応する行列要素に各 2 つの頂点間の辺の数を格納し、非ゼロの対角要素を許可することで、マルチグラフやループを含むグラフに拡張できます。一貫した規則に従っている限り、ループは 1 回 (1 つの辺として) または 2 回 (2 つの頂点と辺の交差として) カウントされます。無向グラフではループを 2 回カウントする後者の規則がよく使用されますが、有向グラフでは通常前者の規則が使用されます。

2つの部分にrとsの頂点がある2部グラフの隣接行列Aは、次のように表すことができます。

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

ここで、B はr  ×  s行列であり、0 _r、rおよび0 _{s、s は}r  ×  rおよびs  ×  s のゼロ行列を表します。この場合、小さい方の行列B がグラフを一意に表し、Aの残りの部分は冗長として破棄できます。Bは、双方向隣接行列と呼ばれることもあります。

正式には、G = ( U , V , E )を、部分U = { u ₁ , ..., u _r }、V = { v ₁ , ..., v _s } 、辺Eを持つ二部グラフとします。双方向隣接行列は、r  ×  s 0–1 行列B_であり、ここでbi _{, j} = 1となるのは、 ( ui _i , v _j ) ∈ Eの場合のみです。

G が二部多重グラフまたは重み付きグラフである場合、要素b _{i,j はそれぞれ}頂点間の辺の数または辺の重み( ui、v _j )と見なされます。

単純グラフの( a , b , c )隣接行列Aは、 ( i , j )が辺の場合はA _{i , j} = a 、そうでない場合はb 、対角線上にはc が存在します。ザイデル隣接行列は(−1,1,0)隣接行列です。この行列は、強正則グラフや2 グラフの研究に使用されます。^[3]

距離行列の位置( i , j )には、頂点v _iとv _jの間の距離があります。距離は、頂点を結ぶ最短経路の長さです。辺の長さが明示的に指定されていない限り、経路の長さはその経路に含まれる辺の数です。距離行列は隣接行列の高次乗に似ていますが、2 つの頂点が接続されているかどうかだけを示すのではなく (つまり、ブール値を含む接続行列)、頂点間の正確な距離を示します。

ここで従う規則（無向グラフの場合）は、各辺が行列の適切なセルに1を追加し、各ループ（頂点からその頂点自身への辺）が行列の対角線上の適切なセルに2を追加するというものです。^[4]これにより、隣接行列のそれぞれの行または列の値の合計を取ることで、頂点の次数を簡単に見つけることができます。

有向グラフの隣接行列は非対称になることがある。有向グラフの隣接行列は次のように定義できる。

1. 非ゼロ要素A _{ij は}iからjへの辺を示す。
2. jからiへのエッジを示します。

前者の定義はグラフ理論や社会ネットワーク分析（社会学、政治学、経済学、心理学など）でよく使われています。^[5]後者は他の応用科学（力学システム、物理学、ネットワーク科学など）でより一般的で、Aはグラフ上の線形ダイナミクスを説明するために使用されることがあります。^[6]

最初の定義を使用すると、頂点の入次数は対応する列のエントリを合計することで計算でき、頂点の出次数は対応する行のエントリを合計することで計算できます。 2 番目の定義を使用する場合、頂点の入次数は対応する行の合計によって与えられ、出次数は対応する列の合計によって与えられます。

完全グラフの隣接行列には、対角線上の要素を除いてすべて 1 が含まれます。対角線上の要素には 0 のみが含まれます。空グラフの隣接行列はゼロ行列です。

無向単純グラフの隣接行列は対称であり、したがって実 固有値の完全な集合と直交固有ベクトル基底を持つ。グラフの固有値の集合はグラフのスペクトルである。 ^[7]固有値は次のように表記されることが多い。${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}.}$

最大固有値は、最大次数によって上方に制限されます。これは、ペロン・フロベニウスの定理の結果として見ることができますが、簡単に証明できます。vを に関連付けられた 1 つの固有ベクトルとし、x をv の絶対値が最大となる要素とします。一般性を失うことなく、 v _{x が}正であると仮定します。そうでない場合は、 に関連付けられた固有ベクトル を単に取ります。すると、 ${\displaystyle \lambda_{1}}$${\displaystyle \lambda_{1}}$${\displaystyle -v}$${\displaystyle \lambda_{1}}$

${\displaystyle \lambda _{1}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の連結成分の数です。 Gが二部グラフである場合、各固有値について、その反対もAの固有値であることが示されます。^[8]特に、 − d は任意のd正則二部グラフの固有値です。 ${\displaystyle \lambda _{1}>\lambda _{2}}$${\displaystyle \lambda_{i}}$${\displaystyle -\lambda _{i}=\lambda _{n+1-i}}$

この差はスペクトルギャップと呼ばれ、 Gの展開に関係しています。で表されるのスペクトル半径を導入することも有用です。この数は によって制限されます。この制限はラマヌジャン グラフでは厳密であり、多くの分野で応用されています。 ${\displaystyle \lambda_{1}-\lambda_{2}}$${\displaystyle A}$${\displaystyle \lambda (G)=\max _{\left|\lambda _{i}\right|<d}|\lambda _{i}|}$${\displaystyle \lambda (G)\geq 2{\sqrt {d-1}}-o(1)}$

隣接行列A ₁とA _2を持つ2つの有向グラフまたは無向グラフG ₁とG ₂が与えられているとする。G 1とG ₂が同型であるためには、次の置換行列Pが存在する_必要がある。

${\displaystyle PA_{1}P^{-1}=A_{2}.}$

特に、A ₁とA _{2 は}類似しており、したがって同じ最小多項式、特性多項式、固有値、行列式、トレースを持ちます。したがって、これらはグラフの同型不変量として機能します。ただし、2つのグラフが同じ固有値のセットを持っていても、同型ではない場合があります。^[9]このような線形演算子は、等スペクトルであると言われています。

A が有向グラフまたは無向グラフGの隣接行列である場合、行列A ⁿ (すなわち、Aのn個のコピーの行列積) には興味深い解釈があります。つまり、要素( i、j )は、頂点iから頂点jまでの長さnの (有向または無向の)ウォークの数を示します。nが最小の非負整数で、あるi、jに対してA ⁿの要素( i、j )が正である場合、nは頂点iと頂点jの間の距離です。これがどのように役立つかを示す良い例は、無向グラフGの三角形の数を数えることです。これは、グラフが有向かどうかに応じて、 A ³のトレースを 3 または 6 で割ったものとまったく同じです。各三角形が過剰に数えられていることを補正するために、これらの値で割ります。無向グラフでは、パスは時計回りまたは反時計回り (ijk または ikj) でたどることができるため、各三角形は 3 つのノードすべてで 2 回カウントされます。隣接行列はグラフが接続されているかどうかを判断するために使用できます。

有向グラフが冪零隣接行列を持つ場合（つまり、 An^が零行列となるようなnが存在する場合）、それは有向非巡回グラフである。^[10]

隣接行列は、グラフを操作するコンピュータプログラムでグラフを表現するためのデータ構造として使用されることがあります。このアプリケーションでも使用されている主な代替データ構造は、隣接リストです。^{[11] [12]}

隣接行列を表現するために必要なスペースと、それに対する演算を実行するために必要な時間は、基になる行列に選択された行列表現に依存します。スパース行列表現は、非ゼロ行列エントリのみを格納し、ゼロエントリを暗黙的に表現します。たとえば、スパースグラフの隣接行列に多数のゼロエントリを格納することによるスペースオーバーヘッドを発生させることなく、スパースグラフを表現するために使用できます。次のセクションでは、隣接行列は配列データ構造によって表現され、ゼロエントリと非ゼロエントリがすべてストレージ内で直接表現されると想定します。

隣接行列の各エントリは 1 ビットしか必要としないため、非常にコンパクトに表現でき、有向グラフを表現する場合は |  V | 2 / 8 バイトしか占有せず、無向グラフを表現する場合は (パックされた三角形式を使用し、行列の下三角部分のみを格納することで) 約 | V  | ² /  16^{バイトしか占有しません。もう少し簡潔な表現も可能ですが、この方法は、すべての}n頂点グラフ を表現するために必要な最小ビット数の情報理論的な下限に近づきます。^{[13]グラフを}テキスト ファイルに格納する場合、たとえばBase64表現を使用することで、バイトあたりのビット数を減らして、すべてのバイトがテキスト文字であることを保証できます。^[14]このコンパクトさは、無駄なスペースを回避するだけでなく、参照の局所性を促進します。ただし、大規模なスパース グラフの場合、隣接リストは存在しないエッジを表すスペースを無駄にしないため、必要なストレージ スペースが少なくなります。^{[12] [15]}

隣接行列の別の形式（ただし、より多くのスペースが必要）では、行列の各要素の数値をエッジオブジェクトへのポインタ（エッジが存在する場合）またはヌルポインタ（エッジが存在しない場合）に置き換えます。^[15]隣接行列の要素にエッジの重みを直接格納することもできます。 ^[12]

スペースのトレードオフに加えて、異なるデータ構造は異なる操作も容易にします。隣接リストで特定の頂点に隣接するすべての頂点を見つけるのはリストを読むのと同じくらい簡単で、隣接する頂点の数に比例した時間がかかります。隣接行列では、代わりに行全体をスキャンする必要があり、グラフ全体の頂点の数に比例して長い時間がかかります。一方、隣接行列では、2つの頂点の間に辺があるかどうかを一度にテストできますが、隣接リストでは2つの頂点の最小次数に比例した時間がかかります。^{[12] [15]}

• ラプラシアン行列
• 自己相似行列

ウィキメディア・コモンズには、グラフの隣接行列に関連するメディアがあります。

• Weisstein、Eric W.「隣接行列」。MathWorld。
• Fluffschack — 隣接行列とグラフの関係を示す教育用 Java Web スタート ゲーム。
• オープン データ構造 - セクション 12.1 - AdjacencyMatrix: グラフを行列で表現する、Pat Morin
• カフェ数学: グラフの隣接行列: ウォークの系列を生成する計算への隣接行列の応用。