12.3 特別なグラフ
頻繁に登場する特別なグラフには名前が付いている。\(n\) 個の頂点を持ち任意の異なる二頂点間に辺が存在するグラフを完全グラフ (complete graph) \(K_{n}\) と呼ぶ。\(K_{n}\) は \(n(n-1)/2\) 個の辺を持つ。\(K_{5}\) を図 \(\text{12.3}\) に示す。
辺を持たないグラフを空グラフ (empty graph) と呼ぶ。\(5\) 個の頂点を持つ空グラフを図 \(\text{12.4}\) に示す。
\(n\) 個の頂点が \(n-1\) 個の辺によって一列に並んだグラフを線グラフ (line graph) \(L_{n}\) と呼ぶ。形式的には、線グラフ \(L_{n}\) は次の頂点集合と辺集合を持つ:
\[ \begin{aligned} V(L_{n}) &= \left\{ v_{1}, v_{2}, \ldots, v_{n} \right\} \\ E(L_{n}) &= \left\{ \langle v_{1}\>\text{---}\> v_{2} \rangle,\ \langle v_{2}\>\text{---}\> v_{3} \rangle,\ \ldots,\ \langle v_{n-1}\>\text{---}\> v_{n} \rangle \right\} \end{aligned} \]
\(L_{5}\) を図 \(\text{12.5}\) に示す。
また、無限線グラフ \(L_{\infty}\) も考えられる: 非負整数全体の集合 \(\mathbb{N}\) が頂点集合で、全ての \(k \in \mathbb{N}\) に対して辺 \(\langle k\>\text{---}\>(k+1) \rangle\) が存在するグラフと定義できる。
線グラフ \(L_{n}\) に辺 \(\langle v_{n}\>\text{---}\>v_{1} \rangle\) を加えたグラフを閉路グラフ (cycle graph) \(C_{n}\) と呼ぶ。\(C_{5}\) を図 \(\text{12.6}\) に示す。
