「補グラフ」の版間の差分
提供: miniwiki
ja>CommonsDelinker 細 ("Complement_graph_sample.gif" を "Complement_graph_sample.png" に差し替え(GifTaggerによる。理由:Replacing GIF by exact PNG duplicate.)) |
細 (1版 をインポートしました) |
(相違点なし)
|
2018/8/19/ (日) 17:31時点における最新版
補グラフ(ほグラフ、英: 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完全問題であることの証明にも使われる。