接続行列
グラフ理論において無向グラフは2種類の接続行列、非向き付け (unoriented) 接続行列と向き付け (oriented) 接続行列を持つ。
無向グラフの「非向き付け接続行列」(または単に「接続行列」)はn × m行列Bである(nおよびmはそれぞれ頂点および辺の数)。頂点viと辺ejが接続しているならばBi,j = 1、それ以外は0である。
例えば、右に示す無向グラフの接続行列は4つの行(4つの頂点1–4に対応)と4つの列(4つの辺e1–e4に対応)から構成される行列である
この接続行列を見てみると、それぞれの列の和は2に等しい。これは、それぞれの辺が両端で頂点と連結しているためである。
有向グラフの「接続行列」はn × m行列Bである(nおよびmはそれぞれ頂点および辺の数)。辺ejが頂点viを出発しているならばBi,j = −1、viに到着しているならば1、それ以外は0である(多くの著者らは符号が逆の慣習を使う)。
無向グラフの「向き付け接続行列」は、各辺に任意に向きをつけて得られる有向グラフの接続行列である。すなわち、辺eの列中には、eの片方の頂点に対応する行に1つの1、もう片方の頂点に対応する行に1つの −1が存在し、その他全ての行は0を持つ。