コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

「隣接行列」の版間の差分

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
m編集の要約なし
(他の1人の利用者による、間の4版が非表示)
1行目: 1行目:
{|class="wikitable" align="right" style="margin: 1em"
'''隣接行列'''(りんせつぎょうれつ、{{lang-en-short|adjacency matrix}})とは、{{仮リンク|代数的グラフ理論|en|Algebraic graph theory}}における基本的な概念で、[[グラフ理論|グラフ]]の頂点と頂点の隣接関係を表わす[[正方行列]]である。
|<div style="text-align:center;">[[File:Ungerichteter Graph mit 4 Knoten und 3 Kanten.svg|125px]]</div>
|<div style="text-align:center;"><math>
\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}
</math></div>
|-
!辺の重みと多重辺を<br />持たない[[無向グラフ]]


!左のグラフに対する<br />4x4-隣接行列
頂点集合を {{math|{{mset|1, &hellip;, ''n''}}}} とする有限[[無向グラフ]] {{mvar|G}} に対して、その'''隣接行列''' {{math|''A''(''G'') {{=}} [''a''{{sub|''ij''}}]}} とは(頂点集合によって添字づけられた){{mvar|n}} 次正方行列であって、その {{math|(''i'', ''j'')}} 成分 {{mvar|a{{sub|ij}}}} は頂点 {{mvar|i}} と頂点 {{mvar|j}} を結ぶ枝の数で定義される。これによりグラフ {{mvar|G}} の'''固有多項式'''や'''スペクトル'''がそれぞれ隣接行列 {{math|''A''(''G'')}} の[[固有多項式]]や[[行列のスペクトル|スペクトル]]として定義される。これらはグラフの不変量である(隣接行列そのものは頂点集合上の[[置換 (数学)|置換]]を除いてしか定まらない)。
|-
|[[File:CPT-Graphs-directed-weighted-ex1.svg|175px]]
|<math>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}</math>
|-
!辺の重みを持ち、多重辺を<br />持たない[[有向グラフ]]


!左のグラフに対する<br />隣接行列
[[有向グラフ]]の場合、{{mvar|i}} から {{mvar|j}} に向かう枝があるときのみ {{math|(''i'', ''j'')}} 成分を 1 に、そうでないとき {{math|(''i'', ''j'')}} 成分を 0 にする。また、枝に重みがついているグラフの場合は、 {{math|(''i'', ''j'')}} 成分を重みとする。
|-
|[[File:Adjazenzgraph.svg|200px]]
|<math>A=\begin{pmatrix}
0 & 3 & 0 & 0\\
2 & 0 & 4 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 2 & 0\\
\end{pmatrix}</math>
|-
!辺の重みを持ち、多重辺を<br />持つ[[有向グラフ]]


!ループを持たない左のグラフの<br />[[既約表現|可約]]隣接行列
==例==
6つの頂点と7つの枝から成るグラフの一例
[[画像:6n-graf.svg|center]]


|}
例えば、上の(重みなし)グラフは、次の隣接行列で表現できる。
[[グラフ理論]]および[[計算機科学]]において、'''隣接行列'''(りんせつぎょうれつ、{{lang-en-short|adjacency matrix}})は、有限{{仮リンク|グラフ (離散数学)|en|Graph (discrete mathematics)|label=グラフ}}を表わすために使われる[[正方行列]]である。この行列の要素は、頂点の対がグラフ中で{{仮リンク|近傍 (グラフ理論)|en|Neighbourhood_(graph_theory)|label=隣接}}しているか否かを示す。


有限[[単純グラフ]]の特別な例では、隣接行列はその対角上に0を持つ {{仮リンク|論理行列|en|Logical matrix|label=(0,1)-行列}}である。もしグラフが無向ならば、隣接行列は[[対称行列|対称]]である。グラフとその隣接行列の[[固有値]]および[[固有ベクトル]]との間の関係は{{仮リンク|スペクトラルグラフ理論|en|spectral graph theory}}において研究される。
::<math>\begin{bmatrix}

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

== 定義 ==
頂点の組''V''を持つ単純グラフについて、隣接行列はその要素''A''<sub>''ij''</sub>が頂点''i''から頂点''j''への辺が存在する時は1、辺が存在しない時は0であるような {{abs|''V''}}&nbsp;×&nbsp;{{abs|''V''}}正方行列''A''である<ref>{{citation|title=Algebraic Graph Theory|edition=2nd|first=Norman|last=Biggs|series=Cambridge Mathematical Library|publisher=Cambridge University Press|year=1993|at=Definition 2.1, p.&nbsp;7}}.</ref>。この行列の対角要素は全て0である(単純グラフでは頂点からそれ自身への辺〈{{仮リンク|ループ (グラフ理論)|en|Loop (graph theory)|label=ループ}}〉は許されないため)。また、{{仮リンク|代数的グラフ理論|en|Algebraic graph theory}}において代数変数を持つ非ゼロ要素を置換するために有用なこともある<ref>{{citation
| last = Harary | first = Frank | authorlink = Frank Harary
| journal = SIAM Review
| mr = 0144330
| pages = 202–210
| title = The determinant of the adjacency matrix of a graph
| volume = 4
| issue = 3 | year = 1962
| doi=10.1137/1004057| bibcode = 1962SIAMR...4..202H }}.</ref>。

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

===2部グラフ===
2つの部分が''r''個と''s''個の頂点を持つ[[2部グラフ]]の隣接グラフ''A''は以下の形式で書くことができる。
: <math>A = \begin{pmatrix} 0_{r,r} & B \\ B^T & 0_{s,s} \end{pmatrix},</math>
上式において、''B''は{{nowrap|''r'' × ''s''}} 行列、0<sub>''r'',''r''</sub>および0<sub>''s'',''s''</sub>は{{nowrap|''r'' × ''r''}}および{{nowrap|''s'' × ''s''}}ゼロ行列を表わす。この場合、より小さな行列''B''がグラフを一意に表わし、''A''の残りの部分は冗長として捨てることができる。''B''はbiadjacency行列と呼ばれることがある。

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

''G''が2部[[多重グラフ]]または重み付きグラフならば、要素 ''b''<sub>''i'',''j''</sub>は頂点間の辺の数、または辺{{nowrap|(''u''<sub>''i''</sub>, ''v''<sub>''j''</sub>)}}の重みをそれぞれ取る。

===バリエーション===
単純グラフの {{nowrap|(''a'', ''b'', ''c'')}}-「隣接行列」は、(''i'', ''j'') が辺ならば''A''<sub>''i'',''j''</sub> = ''a''、辺でなければ''b''、対角上に''c''を持つ。{{仮リンク| セイデル隣接行列|en| Seidel adjacency matrix }}は{{nowrap|(−1, 1, 0)}}-「隣接行列」である。この行列は[[強正則グラフ]]と{{仮リンク|ツーグラフ|en|Two-graph}}の研究で使われる<ref>{{cite journal |last=Seidel |first=J. J. |title=Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3 |journal=[[Linear Algebra and its Applications|Lin. Alg. Appl.]] |volume=1 |issue=2 |pages=281–298 |year=1968 |doi=10.1016/0024-3795(68)90008-6 }}</ref>。

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

==例==
===無向グラフ===
ここでは(無向グラフについて)、それぞれの辺が行列中の適切なセルに1を加え、それぞれのループが2を加えるという慣習に従う<ref>{{cite conference |url=https://books.google.com/books?id=wp7XsCAm_9EC&pg=PA63 |title=Expander graphs and codes |last1=Shum |first1=Kenneth |last2=Blake |first2=Ian |date=2003-12-18 |publisher=American Mathematical Society |book-title=Volume 68 of DIMACS series in discrete mathematics and theoretical computer science |pages=63 |conference=Algebraic Coding Theory and Information Theory: DIMACS Workshop, Algebraic Coding Theory and Information Theory |id= }}</ref>。これによって、隣接行列中のその対応する行または列中の値の和を取るとによって頂点の次数を容易に見付けることが可能である。

{|class="wikitable" style="text-align: center; width: 700px; height: 650px;"
!{{仮リンク|ラベル割り当て (グラフ)|en|Graph labeling|label=ラベル付きグラフ}}
!隣接行列
|-
|[[Image:6n-graph2.svg|200px]]
|<math>\begin{pmatrix}
2 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0
\end{bmatrix}</math>
\end{pmatrix}</math>
<br>座標は1–6。
|-
|[[File:Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); numbers.svg|250px]]
<br />{{仮リンク|ナウルグラフ|en|Nauru graph}}
|[[File:Symmetric group 4; Cayley graph 1,5,21 (adjacency matrix).svg|250px]]
<br />座標は0–23。
<br />白い場は0、色付けされた場は1である。
|}

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

{|class="wikitable" style="text-align: center; width: 700px; height: 400px;"
!ラベル付きグラフ
!隣接行列
|-
|[[File:Symmetric group 4; Cayley graph 4,9; numbers.svg|250px]]
<br />[[対称群|S]]<sub>4</sub>の[[有向グラフ|有向]][[ケイリーグラフ]]
|[[File:Symmetric group 4; Cayley graph 4,9 (adjacency matrix).svg|250px]]
<br />座標は0–23。
<br />グラフが有向であるため、隣接行列は必ずしも対称ではない。
|}

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


==性質==
==性質==
===スペクトル===
*重みなしグラフ ''G'' の隣接行列を ''A'' = ''A''(''G'') とすると、''A<sup>n</sup>'' で表される行列の (''i'', ''j'') 成分は、''i'' から ''j'' への相違なる長さ ''n'' の[[路]]の数と等しくなる。実際、''A<sup>n</sup>''の(''i'', ''j'')成分を''a<sub>ij</sub> <sup>(n)</sup>''とすると、
無向単純グラフの隣接行列は[[対称]]であり、したがって[[実数|実]][[固有値]]および直交[[固有ベクトル]]基底の完全集合を持つ。グラフの固有値一式はグラフの'''スペクトル'''である<ref>{{harvtxt|Biggs|1993}}, Chapter 2 ("The spectrum of a graph"), pp.&nbsp;7–13.</ref>。通常、固有値を<math>\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n</math>と表わす。
:<math>A^n = A^{n-1} A = \left( \sum_k {a_{ik}^{(n-1)} a_{kj}} \right)</math>

:であり、''a<sub>ik</sub> <sup>(n-1)</sup> a<sub>kj</sub>''は、(''i'' から ''k'' への相違なる長さ ''n-1'' の路の数)×(''k'' から ''j'' への相違なる長さ ''1'' の路の数)であることから、帰納的に従う。
最大固有値<math>\lambda_1</math>は最大次数によって上に有界である。これは[[ペロン=フロベニウスの定理]]の結果として見ることができるが、容易に証明することができる。''v''を<math>\lambda_1</math>と関連した1つの固有ベクトルとし、''x''を''v''が最大の絶対値を持つ成分とする。一般性を失うことなく''v''<sub>''x''</sub>は正と仮定する。なぜならさもなければ、単純に(これも<math>\lambda_1</math>と関連した)固有ベクトル<math>-v</math>を取ると、
:したがって、''A<sup>n</sup>'' の (''i'', ''i'') 成分が 0 でないとき、頂点 ''i'' を通る長さ ''n'' の[[ループ]]が存在し、逆も成立する。この性質は、有向グラフでも無向グラフでも成り立つ。
: <math>\lambda v_x=(A v)_x=\sum_{y=1}^n A_{x,y}v_y\leq \sum_{y=1}^n A_{x,y} v_x = v_x \deg(x)</math>
となるためである。

''d''次正則グラフについて、''d''はベクトル{{nowrap|1=''v'' = (1, …, 1)}}に対する''A''の最初の固有値である(これが固有値であり、上界により最大値であることを調べることは簡単である)。この固有値の多重度は''G''の連結成分の数であり、具体的には連結グラフでは<math>\lambda_1>\lambda_2</math>である。もし''G''が2部グラフならば、それぞれの固有値<math>\lambda_i</math>について、その[[反数]] <math>-\lambda_i=\lambda_{n+1-i}</math>も''A''の固有値である{{cn|date=March 2015}}。具体的には、-''d''は2部グラフの固有値である。

差<math>\lambda_1-\lambda_2</math>はスペクトルギャップと呼ばれ、''G''の{{仮リンク|エクスパンダーグラフ|en|Expander graph|label=展開}}と関連している。また、スペクトルギャップは、<math>\lambda(G) = \max_{|\lambda_i| < d} |\lambda_i|</math>によって示される<math>A</math>の[[スペクトル半径]]を導入するためにも有用である。この数は<math>\lambda(G)\geq 2\sqrt{d-1}-o(1)</math>で境界がある。この境界は{{仮リンク|ラマヌジャングラフ|en|Ramanujan graph}}においてタイトである。ラマヌジャングラフは多くの分野に応用を持つ。

===同型写像と不変量===
隣接行列''A''<sub>1</sub>および''A''<sub>2</sub>を持つ2つの有向または無向グラフ''G''<sub>1</sub>および''G''<sub>2</sub>が与えられと仮定する。''G''<sub>1</sub>および''G''<sub>2</sub>は、
: <math>P A_1 P^{-1} = A_2</math>
というような[[置換行列]]''P''が存在する時かつその時に限り[[グラフ同型|同型]]である。

具体的には、''A''<sub>1</sub>および''A''<sub>2</sub>は[[行列の相似|相似]]であり、したがって同一の[[最小多項式 (線型代数学)|最小多項式]]、[[固有多項式]]、固有値、[[行列式]]、[[跡 (線型代数学)|跡]]を有する。したがってこれらは、グラフの同型不変量として機能する。しかしながら、2つのグラフは同じ固有値の組を持つかもしれないが、同型ではない<ref>[[Chris Godsil|Godsil, Chris]]; [[Gordon Royle|Royle, Gordon]] ''Algebraic Graph Theory'', Springer (2001), {{ISBN|0-387-95241-1}}, p.164</ref>。こういった[[線型写像|線型作用素]]は{{仮リンク|等スペクトル|en|isospectral}}的と言われる。

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

==データ構造==
隣接行列は、グラフを操作すうためのコンピュータプログラムにおける[[グラフ (データ構造)|グラフの表現]]のための[[データ構造]]として使うことができる。この応用のためにも使われる主な代替データ構造は[[隣接リスト]]である<ref>{{harvtxt|Goodrich|Tamassia|2015}}, p.&nbsp;361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."</ref><ref name="clrs">{{citation |authorlink=Thomas H. Cormen |first=Thomas H. |last=Cormen |authorlink2=Charles E. Leiserson |first2=Charles E. |last2=Leiserson |authorlink3=Ronald L. Rivest |first3=Ronald L. |last3=Rivest |authorlink4=Clifford Stein |first4=Clifford |last4=Stein |year=2001 |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press and McGraw-Hill |isbn=0-262-03293-7 |chapter=Section 22.1: Representations of graphs |pages=527–531 }}.</ref>。

隣接行列中の各成分は1ビットしか必要としないため、隣接行列は非常にコンパクトなやり方で表すことができ、有向グラフを表わすためにはわずか{{abs|''V'' }}<sup>2</sup>/8バイト、無向グラフを表わすためには(パック三角形式を用い、行列の下部三角部分のみを格納することによって)わずか約 {{abs|''V'' }}<sup>2</sup>/16しか占めない。わずかにより簡潔な表現も可能であるものの、この方法は全ての{{mvar|n}}頂点グラフを表わすために必要な最小ビット数の情報理論的下界に近付く<ref>{{citation
| last = Turán | first = György
| doi = 10.1016/0166-218X(84)90126-4
| issue = 3
| journal = [[Discrete Applied Mathematics]]
| mr = 749658
| pages = 289–294
| title = On the succinct representation of graphs
| volume = 8
| year = 1984}}.</ref>。[[テキストファイル]]にグラフを格納するためには、全てのバイトがテキスト文字であることを(例えば[[Base64]]表現を使うことによって)保証するためにバイト毎により少ないビットした使うことができない<ref>{{citation|first1=Brendan | last1=McKay | authorlink = Brendan McKay |title=Description of graph6 and sparse6 encodings|url=http://cs.anu.edu.au/~bdm/data/formats.txt}}.</ref>。無駄な空間を避けることに加えて、このコンパクトさは[[参照の局所性]]を促す。しかしながら、大きな{{仮リンク|密グラフ|en|Dense graph|label=疎グラフ}}では、隣接リストのほうが必要とする格納空間が小さい。これは、隣接リストは存在「しない」辺を表わすためのいかなる空間も無駄にしないためである。

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

空間のトレードオフに加えて、異なるデータ構造は異なる操作をも容易にする。隣接リスト中の任意の頂点に隣接する全ての頂点を探すことはリストを読むのと同じぐらい単純であり、隣の数の比例した時間がかかる。隣接行列を使うと、代わりに全行をスキャンしなければならず、これはグラフ全体の中の頂点の数に比例したより長い時間がかかる。一方、任意の2つの頂点間に辺が存在するかどうかを調べるのは隣接行列を使うと瞬時に決定することができるのに対して、隣接リストを使うと2つの頂点の最小次数に比例した時間を要する<ref name="clrs"/><ref name="gt">{{citation|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|page=363}}.</ref>。


== 出典 ==
*''G'' が無向グラフでかつ自己ループを持たないとき、''G'' に含まれる[[三角形]]の数は、''G'' の隣接行列 ''A'' を用いて、
{{reflist}}
::<math>\frac{1}{6} \cdot {\rm tr}(A^3)</math>
:で表せる。


== 関連項目 ==
== 関連項目 ==
* [[隣接リスト]]
* [[隣接リスト]]
* {{仮リンク|接続行列|label=接続行列(incidence matrix)|en|Incidence matrix|preserve=1}}—グラフの頂点と枝の接続関係を表す行列
* {{仮リンク|接続行列|en|Incidence matrix|preserve=1}}—グラフの頂点と枝の接続関係を表す行列
* {{仮リンク|ラプラシアン行列|en|Laplacian matrix}}
* [[ラプラシアン行列]]
* {{仮リンク|スペクトラルグラフ理論|en|Spectral graph theory}}
* {{仮リンク|スペクトラルグラフ理論|en|Spectral graph theory}}



2019年8月15日 (木) 01:58時点における版

辺の重みと多重辺を
持たない無向グラフ
左のグラフに対する
4x4-隣接行列
辺の重みを持ち、多重辺を
持たない有向グラフ
左のグラフに対する
隣接行列
辺の重みを持ち、多重辺を
持つ有向グラフ
ループを持たない左のグラフの
可約隣接行列

グラフ理論および計算機科学において、隣接行列(りんせつぎょうれつ、: 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]。これによって、隣接行列中のその対応する行または列中の値の和を取るとによって頂点の次数を容易に見付けることが可能である。

ラベル付きグラフ英語版 隣接行列


座標は1–6。


ナウルグラフ英語版


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

有向グラフ

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

ラベル付きグラフ 隣接行列


S4有向ケイリーグラフ


座標は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 (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."
  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 .

関連項目