【「接続行列」の定義と性質】

逆行列とは何か？その求め方・条件・性質の徹底解説 

接続行列の定義 : 数学 に 於いて、 接続行列 （Incidence matrix ）は、2つのオブジェクトクラス間の関係を示す 行列 である。 1つ目のクラスを X 、2つ目を Y とすると、接続行列は、 X の其々の要素について1つの行を、 Y の其々の要素について1つの列を持つ。 行 x 及び列 y 中の成分は x 及び y が関連（此の文脈に於いてincidentと呼ばれる）しているならば1であり、関連してい無いならば0である。 種々変種も存在する。 接続行列は グラフ理論 に於いて頻繁に使われる。 グラフ理論に於いて 無向グラフ は2種類の接続行列、非向き付け (unoriented) 接続行列と向き付け (oriented) 接続行列を持つ。

接続行列の性質 : 接続行列はグラフ理論において頻繁に使われる。

無向グラフと有向グラフ<button id="btn_play_audio" class="btn btn-lg fas fa-play-circle" type="button" data-index="1" data-title-class="_________________" data-placement="top" data-content=""></button>

 

無向グラフ

グラフ理論において無向グラフは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に対応）から構成される行列である

 

e1 e2 e3 e4 1 1 1 1 0 2 1 0 0 0 3 0 1 0 1 4 0 0 1 1

=

この接続行列を見てみると、それぞれの列の和は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を持つ。無向グラフに対してその向き付け接続行列は、列ごとに符号を反転させることを除いて一意的である。これは、列の成分の符号を反転させることが辺の向きの逆転に対応するためである。

以上