2.1. グラフの定義

本書では単純グラフと呼ばれる種類のグラフを最初に考える。名前の通り、単純グラフは非常に単純な定義を持つ:

定義 2.1.1

有限集合 $V$ と $P_{2} (V)$ の部分集合 $E$ の組 $(V, E)$ を単純グラフ (simple graph) と呼ぶ。

復習しておくと、 $P_{2} (V)$ は二つの要素を持つ $V$ の部分集合全体からなる集合を表す。つまり単純グラフとは組 $(V, E)$ であり、 $V$ は有限集合、 $E$ は $V$ の異なる二要素からなる $V$ の部分集合をいくつか集めた集合を表す。これから本章では「単純グラフ」を単に「グラフ」と呼ぶ。ただし、以降の章 (第 3 章) では単純グラフより高度で一般的な「グラフ」の概念を学ぶ。

例 2.1.2

単純グラフの例を示す:

({1, 2, 3, 4}, {{1, 3}, {1, 4}, {3, 4}})

例 2.1.3

任意の $n \in N$ に対して、 $V = {1, 2, \dots, n}$ および

E = {{u, v} \in P_{2} (V) ∣ g cd (u, v) = 1}

と定める。このとき組 $(V, E)$ は単純グラフである。この単純グラフを $n$ 次の共素性グラフ ( $n$ -th coprimality graph) と呼び、 $Cop_{n}$ と表記する。

[一部の文献では定義 2.1.1 で $V$ に有限性を要求しない。このとき無限グラフ (infinite graph) が定義される。このパンドラの箱は本クオーターでは開けないことにする。]

単純グラフは有限集合の要素間の関係を符号化するのに利用される ── 正確に言えば、単純グラフが符号化するのは反射的でない (自分自身とは成立しない) 対称的 (相互的) な二項 (二つの要素間の) 関係である。例えば、例 2.2.2 のグラフ $Cop_{n}$ は有限集合 ${1, 2, \dots, n}$ 上の「互いに素」という関係 (共素性) を符号化する。 [ただし厳密に言えば共素性は反射性を持つ: $1$ と $1$ は互いに素であるものの、 ${1, 1}$ は $E$ に含まれない。] 別の例として、 $V$ を人類全体の集合、 $E$ を集合 ${{u, v} \in P_{2} (V) ∣ ある時点で u と v は婚姻関係にあった}$ と定めると、 $(V, E)$ は単純グラフとなる。2022 年でさえ自分自身との婚姻は不可能なので、全ての婚姻関係は $2$ 要素の部分集合で符号化できる¹。

次の記法はグラフ $(V, E)$ の要素 $V$ と $E$ を参照する簡単な手段を提供する:

定義 2.1.4

$G = (V, E)$ を単純グラフとする。

集合 $V$ を $G$ の頂点集合 (vertex set) と呼び、 $V (G)$ と表す。 [ $V (G)$ の「 $V$ 」は直立体であり、 $(V, E)$ の「 $V$ 」は斜体である点に注意してほしい。二つは異なる記号であり、意味も異なる。斜体の「 $V$ 」は上で定義した組 $G$ の第一要素という特定の集合を表す記号であり、直立体の「 $V$ 」は任意のグラフの頂点集合を表す $V (G)$ という記法の一部である。そのため、別のグラフ $H = (W, F)$ があるとき $V (H)$ は $W$ であり、 $V$ ではない。]
$V$ の要素を $G$ の頂点 (vertex) またはノード (node) と呼ぶ。
集合 $E$ を $G$ の辺集合 (edge set) と呼び、 $E (G)$ と表す。 [ここでも、 $E (G)$ の「 $E$ 」は直立体であり、斜体の $E$ とは異なる意味を持つ。] [任意の単純グラフ $G$ に対して $G = (V (G), E (G))$ が成り立つ。]
$E$ の要素を $G$ の辺 (edge) と呼ぶ。 $V$ の二要素 $u$ , $v$ に対して、 ${u, v}$ を $uv$ と省略する表記をこれからしばしば用いる。この記法を使うと、 $G$ の各辺は $V$ の異なる二要素 $u$ , $v$ を使って $uv$ と書ける。また、当然 $uv = vu$ が成り立つ。
$u$ , $v$ を $G$ の二つの頂点とする。 $uv \in E$ のとき、つまり $uv$ が $G$ の辺のとき、 $u$ と $v$ は (互いに相手と) 隣接する (adjacent) と言う。同じ状況で、辺 $uv$ は $u$ と $v$ を結ぶ (join)、あるいは接続する (connect) と言う。頂点 $u$ , $v$ を辺 $uv$ の端点 (endpoint) と呼ぶ。グラフ $G$ が文脈から明らかでないときは、単に「隣接する」とは言わずに「 $G$ で隣接する」と言うことがある。
$G$ の二頂点 $u$ , $v$ が隣接しないとき、つまり $uv \in / E$ のとき、 $u$ と $v$ は (互いに相手と) 非隣接 (non-adjacent) と言う。
$v$ を $G$ の頂点 (つまり $v \in V$ ) とする。このとき、 $G$ の頂点 $u$ であって $vu \in E$ を満たすものを $v$ の隣接頂点 (neighbor) と呼ぶ。言い換えれば、 $v$ の隣接頂点とは $v$ と隣接する $G$ の頂点である。

例 2.1.5

$G$ を (例 2.1.2 と同じ) 次の単純グラフとする:

({1, 2, 3, 4}, {{1, 3}, {1, 4}, {3, 4}})

このとき、 $G$ の頂点集合 $V (G)$ と辺集合 $E (G)$ は次の通りである:

V (G) E (G) = {1, 2, 3, 4} = {{1, 3}, {1, 4}, {3, 4}} = {13, 14, 34}

最後の行では ${u, v}$ を $uv$ と省略する記法を使っている。頂点 $1$ と頂点 $3$ は ( $13 \in E (G)$ なので) 隣接する。しかし頂点 $1$ と頂点 $2$ は ( $12 \in / E (G)$ なので) 隣接しない。 $1$ の隣接頂点は $3$ と $4$ であり、辺 $34$ の端点は $3$ と $4$ である。

これより一般的な社会的グラフの例として「友達関係グラフ」がある。ここでも $V$ は人類全体の集合であるものの、 $E$ は集合 ${{u, v} \in P_{2} (V) ∣ u と v は友達}$ となる。当然、この定義は友達関係が必ず相互的であることを仮定している (Facebook では正しいが、現実世界では疑わしい)。 ↩︎