補グラフ

補グラフ（ほグラフ、）は、グラフ理論の用語。グラフ formula_1 にとっての補グラフとは、formula_1 において隣接している頂点が補グラフでは必ず隣接していないことと同値である。したがって、あるグラフの補グラフを作成するには、そのグラフの存在しない辺を全て描き、既存の辺を全て消去すればよい。グラフの差集合とは異なり、辺だけが相補的である。
形式的構築.
頂点群 formula_3 と辺群 formula_4 のグラフ formula_5 があるとき、その補グラフ formula_6 は以下のように構築される。
補グラフは、ラムゼー理論などのグラフ理論で使われ、NP完全問題であることの証明にも使われる。