補グラフのソースを表示

{{Expand English|Complement graph|date=2024年5月}}
[[ファイル:Complement_graph_sample.png|frame|right|[[ピーターセングラフ]]（左）とその補グラフ（右）]]
'''補グラフ'''（ほグラフ、{{lang-en-short|complement graph}}）は、[[グラフ理論]]の用語。グラフ <math>H</math> にとっての補グラフとは、<math>H</math> において隣接している頂点が補グラフでは必ず隣接していないことと[[同値]]である。したがって、あるグラフの補グラフを作成するには、そのグラフの存在しない辺を全て描き、既存の辺を全て消去すればよい。グラフの[[差集合]]とは異なり、辺だけが相補的である。

== 形式的構築 ==
頂点群 <math>V_G</math> と辺群 <math>E_G</math> のグラフ <math>G(V_G, E_G)</math> があるとき、その'''補グラフ''' <math>H(V_H, E_H)</math> は以下のように構築される。
* <math>V_H = V_G</math> である。
* <math>n = |V_G|</math> 個の頂点の[[クリーク (グラフ理論)|クリーク]] <math>K^n(V_K, E_K)</math> について、<math>E_H = E_K \setminus E_G</math> とする。

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

== 関連項目 ==
* [[独立集合]]

{{DEFAULTSORT:ほくらふ}}

[[Category:グラフ理論]]
[[Category:数学に関する記事]]