補グラフ

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

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

形式的構築

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

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

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

関連項目