補グラフ

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

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

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

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

• 独立集合

• グラフ理論
• 数学に関する記事

• 英語版ウィキペディアからの翻訳を必要とする記事