接続行列のソースを表示

{{混同|隣接行列 (adjacency matrix)|link1=隣接行列}}
[[数学]]において、'''接続行列'''（せつぞくぎょうれつ、{{lang-en-short|incidence matrix}}）は、2つのオブジェクトクラス間の関係を示す[[行列]]である。1つ目のクラスを''X''、2つ目を''Y''とすると、接続行列は、''X''のそれぞれの要素について1つの行を、''Y''のそれぞれの要素について1つの列を持つ。行''x''および列''y''中の成分は''x''および''y''が関連（この文脈においてincidentと呼ばれる）しているならば1であり、関連していないならば0である。以下に示すように変種が存在する。

== グラフ理論 ==
接続行列は[[グラフ理論]]において頻繁に使われる。

=== 無向グラフと有向グラフ ===
[[画像:Labeled undirected graph.svg|250px|thumb|無向グラフ]]
グラフ理論において[[無向グラフ]]は2種類の接続行列、非向き付け (unoriented) 接続行列と向き付け (oriented) 接続行列を持つ。

無向グラフの「非向き付け接続行列」（または単に「接続行列」）は{{nowrap|''n'' × ''m''}}行列''B''である（''n''および''m''はそれぞれ[[頂点 (グラフ理論)|頂点]]および[[辺 (グラフ理論)|辺]]の数）。頂点''v{{sub|i}}''と辺''e{{sub|j}}''が接続しているならば{{nowrap|1=''B''{{sub|''i'',''j''}} = 1}}、それ以外は0である。

例えば、右に示す無向グラフの接続行列は4つの行（4つの頂点1–4に対応）と4つの列（4つの辺e1–e4に対応）から構成される行列である
{|
|
{|align="left" class="wikitable"
! !!e{{sub|1}}!!e{{sub|2}}!!e{{sub|3}}!!e{{sub|4}}
|-
!1
|1||1||1||0
|-
!2
|1||0||0||0 
|-
!3
|0||1||0||1 
|-
!4
|0||0||1||1
|}
| =
|
<math>\begin{pmatrix}
1 &1 &1 &0 \\
1 &0 &0 &0 \\
0 &1 &0 &1 \\
0 &0 &1 &1 \\
\end{pmatrix}</math>
|}
この接続行列を見てみると、それぞれの列の和は2に等しい。これは、それぞれの辺が両端で頂点と連結しているためである。

[[有向グラフ]]の「接続行列」は{{nowrap|''n'' × ''m''}}行列''B''である（''n''および''m''はそれぞれ[[頂点 (グラフ理論)|頂点]]および[[辺 (グラフ理論)|辺]]の数）。辺''e{{sub|j}}''が頂点''v{{sub|i}}''を出発しているならば{{nowrap|1=''B''{{sub|''i'',''j''}} = −1}}、''v{{sub|i}}''に到着しているならば1、それ以外は0である（符号が逆の慣習を用いる著者も多くいることに注意）。

無向グラフの「向き付け接続行列」は、各辺に任意に向きをつけて得られる有向グラフの接続行列である。すなわち、辺''e''の列中には、''e''の片方の頂点に対応する行に1つの1、もう片方の頂点に対応する行に1つの −1が存在し、その他全ての行は0を持つ。無向グラフに対してその向き付け接続行列は、列ごとに符号を反転させることを除いて一意的である。これは、列の成分の符号を反転させることが辺の向きの逆転に対応するためである。

グラフ''G''の非向き付け接続行列は定理
: <math>A(L(G)) = B(G)^\textsf{T}B(G) - 2I_m</math>
によってその{{仮リンク|線グラフ|en|Line graph}} ''L''(''G'') の[[隣接行列]]と関連している。上式において、''A''(''L''(''G'')) は''G''の線グラフの隣接行列、''B''(''G'') は接続行列、''I{{sub|m}}''は次元''m''の[[単位行列]]である。

離散[[ラプラシアン行列|ラプラシアン]]（またはキルヒホッフ行列）は式
: <math>B(G) B(G)^\textsf{T}</math>
によって向き付け接続行列''B''(''G'') から得られる。

グラフの整数{{仮リンク|サイクル空間|en|Cycle space}}はその向き付け接続行列を[[整数]]または[[実数]]または[[複素数]]上の行列と見なした場合の行列の[[零空間]]に等しい。二値サイクル空間はその向き付けまたは非向き付け接続行列を二元[[可換体|体]]上のものとみなしたときの、行列の零空間である。

=== 符号付きグラフと双向グラフ ===
{{仮リンク|符号付きグラフ|en|signed graph}}の接続行列は向き付き接続行列の一般化である。これは、任意の符号付きグラフを適応させた全ての{{仮リンク|双向グラフ|en|Bidirected graph}}の接続行列である。正の辺の列は、普通の（符号無し）グラフにおける辺と全く同じように、一方の端点に対応する行に1を持ち、もう一方の端点に対応する行に −1を持つ。負の辺の列は両方の行に1または −1のいずれかを持つ。線グラフおよびキルヒホッフ行列の性質は符号付きグラフに一般化される。

=== 多重グラフ ===
接続行列の定義は、{{仮リンク|ループ (グラフ理論)|en|Loop (graph theory)|label=ループ}}と{{仮リンク|多重辺|en|Multiple edges}}を持つグラフに適用される。グラフが符号付きでループが負でない限り、ループに対応する向き付き接続行列の列は全て0である。すると、その接続頂点の行で±2であることを除いて、列は全て0である。

=== ハイパーグラフ ===
普通のグラフの辺は2つの頂点のみを持つことができる（それぞれの端に1つ）ため、グラフに対する接続行列の列は2つの非ゼロ成分のみを持つことができる。対照的に、[[ハイパーグラフ]]は1つの辺に割り当てられた多数の頂点を持つことができる。ゆえに、非負整数の一般行列がハイパーグラフを記述する。

== 結合構造 ==
{{仮リンク|結合構造|en|Incidence structure}}（Incidence structure）''C''の「接続行列」は{{nowrap|''p'' × ''q''}}行列''B''（またはその転置）である。ここで、''p''および''q''はそれぞれ「点」および「線」の数であり、点''p{{sub|i}}''および''L{{sub|j}}''が接続しているならば{{nowrap|1=''B''{{sub|''i'',''j''}} = 1}}、それ以外は0となる。この場合、接続行列はこの構造の{{仮リンク|レフィグラフ|en|Levi graph}}のbiadjacency行列でもある。全てのレフィグラフに対して[[ハイパーグラフ]]が存在し、その逆もまた同様であるため、結合構造の接続行列はハイパーグラフを記述する。

=== 有限幾何 ===
重要な例は[[有限幾何学|有限幾何]]である。例えば、有限平面において、''X''は点の集合、''Y''は線の集合である。高次元の有限幾何において、''X''は点の集合、''Y''は空間全体の次元よりも1つ小さな部分空間（[[超平面]]）の集合かもしれない。あるいは、より一般的には、包含として定義されるincidenceを持つ、''X''はある次元''d''の全ての部分空間の集合、''y''は別の次元''e''の全ての部分空間の集合かもしれない。

=== ポリトープ ===
同様のやり方で、[[ポリトープ]]（超多面体）内で次元が1つ異なる胞（セル）間の関係は、接続行列によって表すことができる<ref>{{Citation |first=H.S.M. |last=Coxeter|author-link=Coxeter| title=[[Regular Polytopes (book)|Regular Polytopes]] |year=1973 |edition=3rd |origyear=1963 |publisher=Dover |isbn=0-486-61480-8 |pages=166-167}}</ref>。

=== ブロックデザイン ===
もう一つの例が[[ブロックデザイン (数学)|ブロックデザイン]]である。ここでは、''X''は「点」の有限集合、''Y''はデザインの種類に依存した規則に従う''X''の部分集合クラス（「ブロック」と呼ばれる）である。接続行列はブロックデザインの理論において重要な道具である。例えば、ブロックの数が少なくとも点の数である、という釣合い型不完備ブロックデザイン (BIBD) の基本定理である{{仮リンク|フィッシャーの不等式|en|Fisher's inequality}}を証明するために使うことができる<ref>{{Citation |page=99 |first=Herbert John |last=Ryser |title=Combinatorial Mathematics |series=The Carus Mathematical Monographs #14 |publisher=The Mathematical Association of America |year=1963}}</ref>。ブロックを集合の系と見なすと、接続行列の[[パーマネント (数学)|パーマネント]]は{{仮リンク|横断集合|en|Transversal (combinatorics)|label=完全代表系}} (SDR) の数である。

== 出典 ==
{{Reflist}}

== 参考文献 ==
* {{Citation |last=Diestel |first=Reinhard |title=Graph Theory |series=Graduate Texts in Mathematics] |volume=173 |edition=3rd |year=2005 |publisher=Springer-Verlag |isbn=3-540-26183-4}}
* Jonathan L Gross, Jay Yellen, ''Graph Theory and its applications'', second edition, 2006 (p 97, Incidence Matrices for undirected graphs; p 98, incidence matrices for digraphs)

== 外部リンク ==
{{Commonscat|Incidence matrices of graphs}}
{{Wiktionary|Incidence matrix}}
* {{高校数学の美しい物語|1241|隣接行列，接続行列，ラプラシアン行列}}
* {{Mathworld |urlname=IncidenceMatrix |title=Incidence matrix}}

{{Normdaten}}
{{DEFAULTSORT:せつそくきようれつ}}
[[Category:行列]]
[[Category:組合せ論]]
[[Category:グラフ理論]]
[[Category:代数的グラフ理論]]
[[Category:データ構造]]