隣接行列

グラフ理論および計算機科学において、隣接行列は、有限グラフを表わすために使われる正方行列である。この行列の要素は、頂点の対がグラフ中で近傍 しているか否かを示す。

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

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

1. 定義
-----

頂点の組//V//を持つ単純グラフについて、隣接行列はその要素//A'ij}}//が頂点//i//から頂点//j//への辺が存在する時は1、辺が存在しない時は0であるような //V//}} × //V//}}正方行列//A//である。この行列の対角要素は全て0である。また、代数的グラフ理論において代数変数を持つ非ゼロ要素を置換するために有用なこともある。

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

1.1. 2部グラフ
----------

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

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

形式的に、1=//G// = }}を部分1=//U// = //u//subおよび1=//V// = //v//subを持つ2部グラフとする。Biadjacency行列は、 (//usub ∈ //E//の時かつその時に限り1=//b//subの//r// × //s//}} 0–1行列//B//である。//

//G//が2部多重グラフまたは重み付きグラフならば、要素 //b''//i//,//j//}}は頂点間の辺の数、または辺(//usubの重みをそれぞれ取る。

1.2. バリエーション
------------

単純グラフの }}-「隣接行列」は、 が辺ならば//A'i//,//j//}} = //a//、辺でなければ//b//、対角上に//c//を持つ。 セイデル隣接行列は}}-「隣接行列」である。この行列は強正則グラフとツーグラフの研究で使われる。

距離行列は、位置  に頂点//vi}}//と //vj}}//との間の距離を有する。この距離は頂点を連結する最短の道の長さである。辺の長さが明示的に与えられていない限り、道の長さは道中の辺の数である。距離行列は隣接行列の高冪と似ているが、2つの頂点が連結しているかどうかだけを教える代わりに、頂点間の正確な距離を与える。

2. 例
----

2.1. 無向グラフ
----------

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



2.2. 有向グラフ
----------

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



2.3. 自明なグラフ
-----------

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

3. 性質
-----

3.1. スペクトル
----------

無向単純グラフの隣接行列は対称であり、したがって実固有値および直交固有ベクトル基底の完全集合を持つ。グラフの固有値一式はグラフのスペクトルである。通常、固有値をと表す。

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

となるためである。

//d//次正則グラフについて、//d//はベクトル1=//v// = }}に対する//A//の最初の固有値である。この固有値の多重度は//G//の連結成分の数であり、具体的には連結グラフではである。もし//G//が2部グラフならば、それぞれの固有値について、その反数 も//A//の固有値であるdate=March 2015}}。具体的には、-//d//は2部グラフの固有値である。

差はスペクトルギャップと呼ばれ、//G//のエクスパンダーグラフと関連している。また、スペクトルギャップは、によって示されるのスペクトル半径を導入するためにも有用である。この数はで境界がある。この境界はラマヌジャングラフにおいてタイトである。ラマヌジャングラフは多くの分野に応用を持つ。

3.2. 同型写像と不変量
-------------

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

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

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

3.3. 行列の冪
---------

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

4. データ構造
--------

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

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

隣接行列の別形式は行列の個々の要素中の数を辺オブジェクトへのポインタあるいはヌルポインタで置き換える。また、辺の重みを隣接行列の要素中に直接格納することも可能である。

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

5. 出典
-----

6. 関連項目
-------

隣接リスト
接続行列 - グラフの頂点と枝の接続関係を表す行列
ラプラシアン行列
スペクトラルグラフ理論

7. 外部リンク
--------