12.1 頂点の連結性と次数

単純グラフは有向グラフと同様に定義される。唯一の違いは辺が無向 (undirected) なことである ── 辺が接続する二点の間に始点と終点の区別は存在しない。始点 \(v\) と終点 \(w\) を持つ有向辺が \(\langle u \to w \rangle\) と表記されるのと同様に、\(v\) と \(w\) を端点に持つ無向辺は本書で \(\langle v\>\text{---}\>w \rangle\) と表記される。

端点 \(u\), \(v\) を持つ無向辺は二要素集合 \(\left\{ u, v \right\}\) で表現でき、\(\langle u\>\text{---}\>v \rangle\) と表記される。\(\langle u\>\text{---}\>v \rangle\) と \(\langle v\>\text{---}\>u \rangle\) は \(u\) と \(v\) を端点に持つ同じ辺を表す。無向辺は単に辺 (edge) とも呼ばれる。

例えば、図 \(\text{12.1}\) に示された単純グラフを \(H\) とすれば、\(H\) の頂点は図中の \(9\) 個の点に対応する。つまり次の等式が成り立つ:

また、辺集合については次の等式が成り立つ:

数学的には、二つの集合 \(V(G)\), \(E(H)\) が単純グラフ \(H\) を完全に定義する。

例えば図 \(\text{12.1}\) に示した単純グラフ \(H\) で頂点 \(a\) は頂点 \(b\) に隣接し、頂点 \(b\) は頂点 \(d\) に隣接する。また、辺 \(\langle a\>\text{---}\>c \rangle\) は頂点 \(a\), \(c\) に接続する。頂点 \(h\) の次数は \(1\) で、頂点 \(d\) の次数は \(2\) である。加えて \(\text{deg}(e) = 3\) が成り立つ。なお、どの頂点とも隣接しない頂点の次数は \(0\) となる。\(G\) が一つ以上の辺を持たなければならない制約は存在しないので、\(E(G)\) は空集合でも構わない。そのとき単純グラフの全ての頂点の次数は \(0\) となる。一方で \(V(G)\) は非空集合と定義されるので、任意の単純グラフは少なくとも一つの頂点を持つ。

単純グラフでは同じ二頂点を結ぶ辺が高々 \(1\) 個しか存在できない事実に注意してほしい¹。また、自己ループ ── 同じ頂点を結ぶ無向辺 ── は単純グラフで許されていない。

頂点がノード (node) と呼ばれる場合もある。本書は二つの単語を全く同じ意味の単語として用いる。単純グラフがネットワーク (network) と呼ばれ、辺が弧 (arc) や直線 (line) と呼ばれることもある。こういった呼称は本書で使われないものの、グラフ理論の他の文献を読むときに注意が必要なので言及しておく。