補グラフ

補グラフ（ほグラフ、英: complement graph）は、グラフ理論の用語。グラフ $H$ にとっての補グラフとは、$H$ において隣接している頂点が補グラフでは必ず隣接していないことと同値である。したがって、あるグラフの補グラフを作成するには、そのグラフの存在しない辺を全て描き、既存の辺を全て消去すればよい。グラフの差集合とは異なり、辺だけが相補的である。

ピーターセングラフ（左）とその補グラフ（右）

形式的構築

頂点群 $V_{G}$ と辺群 $E_{G}$ のグラフ $G(V_{G},E_{G})$ があるとき、その補グラフ $H(V_{H},E_{H})$ は以下のように構築される。

• $V_{H}=V_{G}$ である。
• $n=|V_{G}|$ 個の頂点のクリーク $K^{n}(V_{K},E_{K})$ について、$E_{H}=E_{K}\setminus E_{G}$ とする。

補グラフは、ラムゼー理論などのグラフ理論で使われ、NP完全問題であることの証明にも使われる。

関連項目

• 独立集合