2.1. グラフの定義

有限集合 \(V\) と \(\mathcal{P}_{2}\left( V\right) \) の部分集合 \(E\) の組 \(\left( V,E\right) \) を単純グラフ (simple graph) と呼ぶ。

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

1. 集合 \(V\) を \(G\) の頂点集合 (vertex set) と呼び、\(\operatorname{V}\left( G\right) \) と表す。 [\(\operatorname{V}\left( G\right)\) の「\(\operatorname*{V}\)」は直立体であり、 \(\left( V,E\right) \) の「\(V\)」は斜体である点に注意してほしい。二つは異なる記号であり、意味も異なる。斜体の「\(V\)」は上で定義した組 \(G\) の第一要素という特定の集合を表す記号であり、直立体の「\(\operatorname*{V}\)」は任意のグラフの頂点集合を表す \(\operatorname{V}\left( G\right) \) という記法の一部である。そのため、別のグラフ \(H=\left( W,F\right) \) があるとき \(\operatorname{V}\left( H\right) \) は \(W\) であり、\(V\) ではない。]

2. \(V\) の要素を \(G\) の頂点 (vertex) またはノード (node) と呼ぶ。

3. 集合 \(E\) を \(G\) の辺集合 (edge set) と呼び、\(\operatorname{E}\left( G\right) \) と表す。 [ここでも、\(\operatorname{E}\left( G\right) \) の「\(\operatorname*{E}\)」は直立体であり、斜体の \(E\) とは異なる意味を持つ。] [任意の単純グラフ \(G\) に対して \(G=\left( \operatorname{V}\left( G\right) ,\operatorname{E}\left( G\right) \right) \) が成り立つ。]

4. \(E\) の要素を \(G\) の辺 (edge) と呼ぶ。\(V\) の二要素 \(u\), \(v\) に対して、\(\left\{ u,v\right\} \) を \(uv\) と省略する表記をこれからしばしば用いる。この記法を使うと、\(G\) の各辺は \(V\) の異なる二要素 \(u\), \(v\) を使って \(uv\) と書ける。また、当然 \(uv = vu\) が成り立つ。

5. \(u\), \(v\) を \(G\) の二つの頂点とする。\(uv \in E\) のとき、つまり \(uv\) が \(G\) の辺のとき、\(u\) と \(v\) は (互いに相手と) 隣接する (adjacent) と言う。同じ状況で、辺 \(uv\) は \(u\) と \(v\) を結ぶ (join)、あるいは接続する (connect) と言う。頂点 \(u\), \(v\) を辺 \(uv\) の端点 (endpoint) と呼ぶ。グラフ \(G\) が文脈から明らかでないときは、単に「隣接する」とは言わずに「\(G\) で隣接する」と言うことがある。

6. \(G\) の二頂点 \(u\), \(v\) が隣接しないとき、つまり \(uv \notin E\) のとき、\(u\) と \(v\) は (互いに相手と) 非隣接 (non-adjacent) と言う。

7. \(v\) を \(G\) の頂点 (つまり \(v \in V\)) とする。このとき、\(G\) の頂点 \(u\) であって \(vu \in E\) を満たすものを \(v\) の隣接頂点 (neighbor) と呼ぶ。言い換えれば、\(v\) の隣接頂点とは \(v\) と隣接する \(G\) の頂点である。