隣接行列

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Ungerichteter Graph mit 4 Knoten und 3 Kanten.svg
辺の重みと多重辺を
持たない無向グラフ
左のグラフに対する
4x4-隣接行列
CPT-Graphs-directed-weighted-ex1.svg
辺の重みを持ち、多重辺を
持たない有向グラフ
左のグラフに対する
隣接行列
Adjazenzgraph.svg
辺の重みを持ち、多重辺を
持つ有向グラフ
ループを持たない左のグラフの
可約隣接行列

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

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

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

定義[編集]

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

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

2部グラフ[編集]

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

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

形式的に、G = (U, V, E)を部分U = {u1, …, ur}およびV = {v1, …, vs}を持つ2部グラフとする。Biadjacency行列は、 (ui, vj)Eの時かつその時に限りbi,j = 1r × s 0–1行列Bである。

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

バリエーション[編集]

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

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

[編集]

無向グラフ[編集]

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

ラベル付きグラフ英語版 隣接行列
6n-graph2.svg


座標は1–6。

Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); numbers.svg


ナウルグラフ英語版

Symmetric group 4; Cayley graph 1,5,21 (adjacency matrix).svg


座標は0–23。
白い場は0、色付けされた場は1である。

有向グラフ[編集]

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

ラベル付きグラフ 隣接行列
Symmetric group 4; Cayley graph 4,9; numbers.svg


S4有向ケイリーグラフ

Symmetric group 4; Cayley graph 4,9 (adjacency matrix).svg


座標は0–23。
グラフが有向であるため、隣接行列は必ずしも対称ではない。

自明なグラフ[編集]

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

性質[編集]

スペクトル[編集]

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

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

となるためである。

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

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

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

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

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

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

行列の冪[編集]

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

データ構造[編集]

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

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

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

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

出典[編集]

  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, Bibcode1962SIAMR...4..202H, doi:10.1137/1004057, MR0144330 .
  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 (2003-12-18). “Expander graphs and codes”. Algebraic Coding Theory and Information Theory: DIMACS Workshop, Algebraic Coding Theory and Information Theory. American Mathematical Society. pp. 63. https://books.google.com/books?id=wp7XsCAm_9EC&pg=PA63 
  5. ^ Biggs (1993), Chapter 2 ("The spectrum of a graph"), pp. 7–13.
  6. ^ Godsil, Chris; Royle, Gordon Algebraic Graph Theory, Springer (2001), 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."
  8. ^ 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 .
  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, http://cs.anu.edu.au/~bdm/data/formats.txt .
  11. ^ a b Goodrich, Michael T.; Tamassia, Roberto (2015), Algorithm Design and Applications, Wiley, p. 363 .

関連項目[編集]