「補グラフ」の版間の差分

削除された内容追加された内容

インライン

2024年5月24日 (金) 19:13時点における最新版

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

@@ 1行目: / 1行目: @@
+{{Expand English|Complement graph|date=2024年5月}}
-[[ファイル:Complement_graph_sample.gif|frame|right|[[ピーターセングラフ]]（左）とその補グラフ（右）]]
+[[ファイル:Complement_graph_sample.png|frame|right|[[ピーターセングラフ]]（左）とその補グラフ（右）]]
-'''補グラフ'''（[[英語|英]]: complement graph）とは、[[グラフ理論]]の用語。グラフ <math>H</math> にとっての補グラフとは、<math>H</math> において隣接している頂点が補グラフでは必ず隣接していないことと[[同値]]である。したがって、あるグラフの補グラフを作成するには、そのグラフの存在しない辺を全て描き、既存の辺を全て消去すればよい。グラフの[[差集合]]とは異なり、辺だけが相補的である。
+'''補グラフ'''（ほグラフ、{{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> とする。
+* <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:グラフ理論]]
-[[en:Complement graph]]
+[[Category:数学に関する記事]]
-[[es:Grafo complemento]]
-[[fr:Graphe complémentaire]]
-[[he:גרף משלים]]
-[[hu:Komplementer gráf]]
-[[pl:Dopełnienie grafu]]
-[[sk:Komplement grafu]]
-[[sr:Комплемент графа]]