補グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
ピーターセングラフ(左)とその補グラフ(右)

補グラフ(ほグラフ、: 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完全問題であることの証明にも使われる。

関連項目[編集]