グラフ (無向)とは?

二つの集合 V と E を考えます。 また

N(V) = {A:AV, 1 <=Card (A)<=2}.

と置きます。これはVの、高々二点の、空でない部分集合全体からなる集合です。今T() を E から N(V) の写像とします。このとき三つ組

G = (V,E,T())

グラフ または 無向グラフ といいます。

V を頂点の集合(a set of vertices) E を 辺の集合(a set of edges) ということもあります。なぜ G をグラフというかですが、それは G が次の例のような意味で線図形に対応するからです。

例 1

V = {A,B,C,D}, E = {s,t,u,v},

T(s) = {A,B}
T(t) = {B,C}
T(u) = {C,D}
T(v) = {D,A}

これは下の四角形に対応します.四つの頂点 A,B,C,D が V の要素になっています。辺が s,t,u,v でこれらは Eの要素です。写像Tは各辺がどの頂点と頂点を結ぶかを示します。