無向グラフと有向グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/05 03:40 UTC 版)
グラフ理論において無向グラフは2種類の接続行列、非向き付け (unoriented) 接続行列と向き付け (oriented) 接続行列を持つ。 無向グラフの「非向き付け接続行列」（または単に「接続行列」）はn × m行列Bである（nおよびmはそれぞれ頂点および辺の数）。頂点viと辺ejが接続しているならばBi,j = 1、それ以外は0である。 例えば、右に示す無向グラフの接続行列は4つの行（4つの頂点1–4に対応）と4つの列（4つの辺e1–e4に対応）から構成される行列である e1e2e3e411 1 1 0 21 0 0 0 30 1 0 1 40 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を出発しているならばBi,j = −1、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) から得られる。 グラフの整数サイクル空間（英語版）はその向き付け接続行列の零空間に等しい。これは整数または実数または複素数にわたる行列と見なされる。二値サイクル空間はその向き付けまたは非向き付け接続行列の零空間である。これは、二元体にわたる行列と見なされる。
※この「無向グラフと有向グラフ」の解説は、「接続行列」の解説の一部です。
「無向グラフと有向グラフ」を含む「接続行列」の記事については、「接続行列」の概要を参照ください。
- 無向グラフと有向グラフのページへのリンク
