📂グラフ理論

ヌルグラフと完全グラフ

定義 ¹

単純グラフ $G$ が与えられたとする。

1. $E(G) = \emptyset$ ならば、$G$ をヌルグラフという。
2. $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)$ と言う。
• 一方、向きがある完全グラフをトーナメントと呼ぶ。