接続行列

数学において、接続行列（せつぞくぎょうれつ、英: 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はそれぞれ頂点および辺の数）。頂点v_iと辺e_jが接続しているならばB_i,j = 1、それ以外は0である。

例えば、右に示す無向グラフの接続行列は4つの行（4つの頂点1–4に対応）と4つの列（4つの辺e1–e4に対応）から構成される行列である

	e₁	e₂	e₃	e₄
1	1	1	1	0
2	1	0	0	0
3	0	1	0	1
4	0	0	1	1

${\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はそれぞれ頂点および辺の数）。辺e_jが頂点v_iを出発しているならばB_i,j = −1、v_iに到着しているならば1、それ以外は0である（多くの著者らは符号が逆の慣習を使う）。

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

グラフGの非向き付け接続行列は定理

A(L(G))=B(G)^{\textsf {T}}B(G)-2I_{m}

によってその線グラフ（英語版） L(G) の隣接行列と関連している。上式において、A(L(G)) はGの線グラフの隣接行列、B(G) は接続行列、I_mは次元mの単位行列である。

離散ラプラシアン（またはキルヒホッフ行列）は式

B(G)B(G)^{\textsf {T}}

によって向き付け接続行列B(G) から得られる。

グラフの整数サイクル空間（英語版）はその向き付け接続行列の零空間に等しい。これは整数または実数または複素数にわたる行列と見なされる。二値サイクル空間はその向き付けまたは非向き付け接続行列の零空間である。これは、二元体にわたる行列と見なされる。

符号付きグラフと双向グラフ

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

多重グラフ

接続行列の定義は、ループ（英語版）と多重辺（英語版）を持つグラフに適用される。グラフが符号付きでループが負でない限り、ループに対応する向き付き接続行列の列は全て0である。すると、その接続頂点の行で±2であることを除いて、列は全て0である。

ハイパーグラフ

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

結合構造

結合構造（英語版）（Incidence structure）Cの「接続行列」はp × q行列B（またはその転置）である。ここで、pおよびqはそれぞれ「点」および「線」の数であり、点p_iおよびL_jが接続しているならばB_i,j = 1、それ以外は0となる。この場合、接続行列はこの構造のレフィグラフ（英語版）のbiadjacency行列でもある。全てのレフィグラフに対してハイパーグラフが存在し、その逆もまた同様であるため、結合構造の接続行列はハイパーグラフを記述する。

有限幾何

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

ポリトープ

同様のやり方で、ポリトープ（超多面体）内で次元が1つ異なる胞（セル）間の関係は、接続行列によって表すことができる^[1]。

ブロックデザイン

もう一つの例がブロックデザインである。ここでは、Xは「点」の有限集合、Yはデザインの種類に依存した規則に従うXの部分集合クラス（「ブロック」と呼ばれる）である。接続行列はブロックデザインの理論において重要な道具である。例えば、ブロックの数が少なくとも点の数である、という釣合い型不完備ブロックデザイン (BIBD) の基本定理であるフィッシャーの不等式（英語版）を証明するために使うことができる^[2]。ブロックを集合の系と見なすと、接続行列のパーマネントは完全代表系（英語版） (SDR) の数である。

出典

^ Coxeter, H.S.M. (1973) [1963], Regular Polytopes (3rd ed.), Dover, pp. 166-167, 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)