利用者:Next49/sandbox

グラフ理論の形式的な定義の編集

形式的な定義

グラフ

グラフGは、頂点（あるいは、点、節点）の集合Vと順序を考慮しない頂点の対の集合Eの二つ組で構成される。

$G:=(V,E)$

$V:=\{v_{1},v_{2},...,v_{n}\}\ (0\leq n)$

$E:=\{\{v_{i},v_{j}\}|v_{i},v_{j}\in V,\ i\not =j,\ 1\leq i,j\leq n\}$

E の元を G の辺と呼ぶ。辺に向きを持たせたグラフを有向グラフ（後述）と呼ぶのに対し、向きを持たないグラフのことを無向グラフと呼ぶこともある。

上述のグラフの定義では、グラフ中の2頂点間を結ぶ辺の数は高々1本しか許されていない。また、同一の頂点を結ぶ辺（ループ）も許されていない。一方で、2頂点間を複数の辺（多重辺）で結ぶこと、および、ループを許すグラフの定義もある。そのようなグラフは以下の定義になる。ただし、以下の定義中のEは多重集合（族）とする。

$G:=(V,E)$

$V:=\{v_{1},v_{2},...,v_{n}\}\ (0\leq n)$

$E:=\{\{v_{i},v_{j}\}|v_{i},v_{j}\in V,\ 1\leq i,j\leq n\}$

1つ目の定義に基づくグラフをグラフと呼ぶ場合、2つ目の定義に基づくグラフを多重グラフと呼ぶ。2つ目の定義に基づくグラフをグラフと呼ぶ場合、1つ目の定義に基づくグラフを単純グラフと呼ぶ。

有向グラフ

集合 V , E と、E の元（げん、要素）に、二つの V を元の対で対応させる写像

$f\colon \ E\to V\times V$

の三つ組

$G:=(f,V,E)$

を有向グラフという。V の元を G の頂点またはノード、E の元を G の辺または弧と呼ぶ。

無向グラフ

P(V) を V の冪集合とする。E の元に V の 部分集合を対応させる写像

$g\colon \ E\to P(V)$

があって、E の任意の元 e の像が g(e) = {v₁, v₂} のようにちょうど二つの元の集合になっているとする。このとき、三つ組

$G:=(g,V,E)$

を無向グラフという。V の元を G の頂点、E の元を G の辺と呼ぶ。g の値が常にk > 2個の元の集合となっているとき、k-ハイパーグラフという。

E を最初からある集合の部分集合と考えれば、写像を用いずにグラフを定義することもできる：有向グラフでは、E を V×V の部分集合、無向グラフでは、E を P(V) の部分集合で、二つの元の集合だけからなるものとすればよい。