数学 において、接続行列 （せつぞくぎょうれつ、英 : incidence matrix ）は、2つのオブジェクトクラス間の関係を示す行列 である。1つ目のクラスをX 、2つ目をY とすると、接続行列は、X のそれぞれの要素について1つの行を、Y のそれぞれの要素について1つの列を持つ。行x および列y 中の成分はx およびy が関連（この文脈においてincidentと呼ばれる）しているならば1であり、関連していないならば0である。以下に示すように変種が存在する。
接続行列はグラフ理論 において頻繁に使われる。
無向グラフ グラフ理論において無向グラフ は2種類の接続行列、非向き付け (unoriented) 接続行列と向き付け (oriented) 接続行列を持つ。
無向グラフの「非向き付け接続行列」（または単に「接続行列」）はn × m B である（n およびm はそれぞれ頂点 および辺 の数）。頂点vi と辺ej が接続しているならばB i ,j
例えば、右に示す無向グラフの接続行列は4つの行（4つの頂点1–4に対応）と4つの列（4つの辺e1–e4に対応）から構成される行列である
e1
e2
e3
e4
1
1
1
1
0
2
1
0
0
0
3
0
1
0
1
4
0
0
1
1
=
(
1
1
1
0
1
0
0
0
0
1
0
1
0
0
1
1
)
{\displaystyle {\begin{pmatrix}1&1&1&0\\1&0&0&0\\0&1&0&1\\0&0&1&1\\\end{pmatrix}}}
この接続行列を見てみると、それぞれの列の和は2に等しい。これは、それぞれの辺が両端で頂点と連結しているためである。
有向グラフ の「接続行列」はn × m B である（n およびm はそれぞれ頂点 および辺 の数）。辺ej が頂点vi を出発しているならばB i ,j vi に到着しているならば1、それ以外は0である（符号が逆の慣習を用いる著者も多くいることに注意）。
無向グラフの「向き付け接続行列」は、各辺に任意に向きをつけて得られる有向グラフの接続行列である。すなわち、辺e の列中には、e の片方の頂点に対応する行に1つの1、もう片方の頂点に対応する行に1つの −1が存在し、その他全ての行は0を持つ。無向グラフに対してその向き付け接続行列は、列ごとに符号を反転させることを除いて一意的である。これは、列の成分の符号を反転させることが辺の向きの逆転に対応するためである。
グラフG の非向き付け接続行列は定理
A
(
L
(
G
)
)
=
B
(
G
)
T
B
(
G
)
− − -->
2
I
m
{\displaystyle A(L(G))=B(G)^{\textsf {T}}B(G)-2I_{m}}
によってその線グラフ （英語版 ） L (G ) の隣接行列 と関連している。上式において、A (L (G )) はG の線グラフの隣接行列、B (G ) は接続行列、Im は次元m の単位行列 である。
離散ラプラシアン （またはキルヒホッフ行列）は式
B
(
G
)
B
(
G
)
T
{\displaystyle B(G)B(G)^{\textsf {T}}}
によって向き付け接続行列B (G ) から得られる。
グラフの整数サイクル空間 （英語版 ） 整数 または実数 または複素数 上の行列と見なした場合の行列の零空間 に等しい。二値サイクル空間はその向き付けまたは非向き付け接続行列を二元体 上のものとみなしたときの、行列の零空間である。
符号付きグラフ （英語版 ） 双向グラフ （英語版 ）
接続行列の定義は、ループ （英語版 ） 多重辺 （英語版 ）
普通のグラフの辺は2つの頂点のみを持つことができる（それぞれの端に1つ）ため、グラフに対する接続行列の列は2つの非ゼロ成分のみを持つことができる。対照的に、ハイパーグラフ は1つの辺に割り当てられた多数の頂点を持つことができる。ゆえに、非負整数の一般行列がハイパーグラフを記述する。
結合構造 （英語版 ） C の「接続行列」はp × q B （またはその転置）である。ここで、p およびq はそれぞれ「点」および「線」の数であり、点pi およびLj が接続しているならばB i ,j レフィグラフ （英語版 ） ハイパーグラフ が存在し、その逆もまた同様であるため、結合構造の接続行列はハイパーグラフを記述する。
重要な例は有限幾何 である。例えば、有限平面において、X は点の集合、Y は線の集合である。高次元の有限幾何において、X は点の集合、Y は空間全体の次元よりも1つ小さな部分空間（超平面 ）の集合かもしれない。あるいは、より一般的には、包含として定義されるincidenceを持つ、X はある次元d の全ての部分空間の集合、y は別の次元e の全ての部分空間の集合かもしれない。
同様のやり方で、ポリトープ （超多面体）内で次元が1つ異なる胞（セル）間の関係は、接続行列によって表すことができる[ 1]
もう一つの例がブロックデザイン である。ここでは、X は「点」の有限集合、Y はデザインの種類に依存した規則に従うX の部分集合クラス（「ブロック」と呼ばれる）である。接続行列はブロックデザインの理論において重要な道具である。例えば、ブロックの数が少なくとも点の数である、という釣合い型不完備ブロックデザイン (BIBD) の基本定理であるフィッシャーの不等式 （英語版 ） [ 2] パーマネント は完全代表系 （英語版 ）
^ Coxeter, H.S.M. (1973) [1963], Regular Polytopes ISBN 0-486-61480-8 ^ Ryser, Herbert John (1963), Combinatorial Mathematics , The Carus Mathematical Monographs #14, The Mathematical Association of America, p. 99
Diestel, Reinhard (2005), Graph Theory , Graduate Texts in Mathematics], 173 (3rd ed.), 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)
ウィキメディア・コモンズには、
接続行列 に関連するカテゴリがあります。
