隣接行列のソースを表示

{{混同|接続行列 (incidence matrix)|link1=接続行列}}
{|class="wikitable" align="right" style="margin: 1em"
|<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-隣接行列
|-
|[[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 />隣接行列
|-
|[[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 />[[既約表現|可約]]隣接行列
|}
[[グラフ理論]]および[[計算機科学]]において、'''隣接行列'''（りんせつぎょうれつ、{{lang-en-short|adjacency matrix}}）は、有限[[グラフ (離散数学)|グラフ]]を表わすために使われる[[正方行列]]である。この行列の要素は、頂点の対がグラフ中で{{仮リンク|近傍 (グラフ理論)|en|Neighbourhood_(graph_theory)|label=隣接}}しているか否かを示す。

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

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

== 定義 ==
頂点の組''V''を持つ単純グラフについて、隣接行列はその要素''A'{{sub|ij}}''が頂点''i''から頂点''j''への辺が存在する時は1、辺が存在しない時は0であるような {{abs|''V''}} × {{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.7}}.</ref>。この行列の対角要素は全て0である（単純グラフでは頂点からそれ自身への辺〈{{仮リンク|ループ (グラフ理論)|en|Loop (graph theory)|label=ループ}}〉は許されないため）。また、[[代数的グラフ理論]]において代数変数を持つ非ゼロ要素を置換するために有用なこともある<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''}}および0{{sub|''s'',''s''}}は{{nowrap|''r'' × ''r''}}および{{nowrap|''s'' × ''s''}}ゼロ行列を表す。この場合、より小さな行列''B''がグラフを一意に表し、''A''の残りの部分は冗長として捨てることができる。''B''はbiadjacency行列と呼ばれることがある。

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

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

===バリエーション===
単純グラフの {{nowrap|(''a'', ''b'', ''c'')}}-「隣接行列」は、(''i'', ''j'') が辺ならば''A''{{sub|''i'',''j''}} = ''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}}''と ''v{{sub|j}}''との間の距離を有する。この距離は頂点を連結する最短の道の長さである。辺の長さが明示的に与えられていない限り、道の長さは道中の辺の数である。距離行列は隣接行列の高冪と似ているが、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 |page=63 |conference=Algebraic Coding Theory and Information Theory: DIMACS Workshop, Algebraic Coding Theory and Information Theory}}</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\\
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}</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}}の[[有向グラフ|有向]][[ケイリーグラフ]]
|[[File:Symmetric group 4; Cayley graph 4,9 (adjacency matrix).svg|250px]]
<br />座標は0–23。
<br />グラフが有向であるため、隣接行列は必ずしも対称ではない。
|}

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

==性質==
===スペクトル===
無向単純グラフの隣接行列は[[対称]]であり、したがって[[実数|実]][[固有値]]および直交[[固有ベクトル]]基底の完全集合を持つ。グラフの固有値一式はグラフの'''スペクトル'''である<ref>{{harvtxt|Biggs|1993}}, Chapter 2 ("The spectrum of a graph"), pp.7–13.</ref>。通常、固有値を<math>\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n</math>と表す。

最大固有値<math>\lambda_1</math>は最大次数によって上に有界である。これは[[ペロン＝フロベニウスの定理]]の結果として見ることができるが、容易に証明することができる。''v''を<math>\lambda_1</math>と関連した1つの固有ベクトルとし、''x''を''v''が最大の絶対値を持つ成分とする。一般性を失うことなく''v{{sub|x}}''は正と仮定する。なぜならさもなければ、単純に（これも<math>\lambda_1</math>と関連した）固有ベクトル<math>-v</math>を取ると、
: <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>で境界がある。この境界は[[ラマヌジャングラフ]]においてタイトである。ラマヌジャングラフは多くの分野に応用を持つ。

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

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

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

== データ構造 ==
隣接行列は、グラフを操作するためのコンピュータプログラムにおける[[グラフ (データ構造)|グラフの表現]]のための[[データ構造]]として使うことができる。この応用のためにも使われる主な代替データ構造は[[隣接リスト]]である<ref>{{harvtxt|Goodrich|Tamassia|2015}}, p.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}}/8バイト、無向グラフを表わすためには（パック三角形式を用い、行列の下部三角部分のみを格納することによって）わずか約 {{abs|''V'' }}{{sup|2}}/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>。

== 出典 ==
{{Reflist}}

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

== 外部リンク ==
* {{高校数学の美しい物語|1241|隣接行列，接続行列，ラプラシアン行列}}

{{Normdaten}}
{{DEFAULTSORT:りんせつきようれつ}}
[[Category:行列]]
[[category:グラフ理論]]
[[Category:数学に関する記事]]
[[Category:代数的グラフ理論]]