ヌルグラフと完全グラフ
定義 1
単純グラフ $G$ が与えられたとする。
- $E(G) = \emptyset$ ならば、$G$ をヌルグラフという。
- $E \left( \overline{G} \right) = \emptyset$ ならば、$G$ を完全グラフという。
説明
ヌルグラフとは、文字通り空のグラフを意味する。EmptyではなくNullという表現を使ったのは、実際に$G \ne \emptyset$ であっても、グラフとしての意味がないためである。例えば、次の図のように頂点だけが存在しているなら、それをグラフと呼ぶ理由はほとんどない。しかし、数学で$0$ という数が非常に重要であるように、ヌルグラフはグラフ理論全般で非常に頻繁に言及される。
完全グラフは元のグラフ$G$ の補グラフ $\overline{G} $ として定義される。$\overline{G}$ がヌルグラフであることは、元のグラフ$G$ の全ての頂点が例外なく接続されていることを意味する。例えば、上のグラフの補グラフは以下の通りである。
追加定義
特に、頂点の数が$n$ の完全グラフを$K_{n}$ と表記する場合もある。
- 何らかのグラフのサブグラフとしての完全グラフは、クリークと呼ばれる。
- グラフ$G$ のクリーク$K_{n}$ の中で最大の$n$ を、$G$ のクリーク数 $\omega (G)$ と言い、
- $G$ の補グラフ$\overline{G}$ のクリーク数を、$G$ の独立数 $\beta (G) := \omega \left( \overline{G} \right)$ と言う。
- 一方、向きがある完全グラフをトーナメントと呼ぶ。
Wilson. (1970). Graph TheoryのIntroduction: p17. ↩︎