📂グラフ理論

グラフの補完

定義 ¹

シンプルグラフ $G$ について、以下の条件を満たすグラフ $\overline{G}$ を $G$ のコンプリメントという。 $$V \left( \overline{G} \right) = V(G) \\ vw \in E \left( \overline{G} \right) \iff vw \notin E(G)$$

説明

普通の数学でのコンプリメントがそうであるように、グラフのコンプリメントは補の概念を意味する。韓国語で素直に翻訳すると余グラフ^{complement graph}になるけど、どれも気に入らないからそのままコンプリメントと書く。

図を見て直感的に理解するのは難しくないが、数式だけで説明するとちょっと厄介な部分がある。この表現を導入することで、グラフをもっと便利で簡単に扱えるようになる。コンプリメントグラフの例として、次の図を見てみよう：

二つのグラフ $G$ と $\overline{G}$ は同じ頂点を持っているが、エッジは正反対を持っている。この説明で「正反対」という言葉を使うのは数学的に良いとは言えないだろう。それを $$vw \in E \left( \overline{G} \right) \iff vw \notin E(G)$$ で説明すると数学的にはスッキリするけど、自然に読むのが少し難しくなる。代わりに単にコンプリメントと表現すれば、一つの例で理解して、数式なしで数学的な議論を続けやすくなる。