「補グラフ」の版間の差分
表示
削除された内容 追加された内容
en:Complement graph(2009年3月5日 3:00:45(UTC))の翻訳 |
編集の要約なし |
||
(12人の利用者による、間の13版が非表示) | |||
1行目: | 1行目: | ||
{{Expand English|Complement graph|date=2024年5月}} |
|||
[[ファイル:Complement_graph_sample. |
[[ファイル: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_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>V_H = V_G</math> である。 |
||
* <math>n = |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完全問題]]であることの証明にも使われる。 |
補グラフは、[[ラムゼー理論]]などのグラフ理論で使われ、[[NP完全問題]]であることの証明にも使われる。 |
||
== 関連項目 == |
|||
* [[独立集合]] |
|||
{{DEFAULTSORT:ほくらふ}} |
{{DEFAULTSORT:ほくらふ}} |
||
⚫ | |||
⚫ | |||
[[en:Complement graph]] |
|||
[[Category:数学に関する記事]] |
|||
[[es:Grafo complemento]] |
|||
[[fr:Graphe complémentaire]] |
|||
[[he:גרף משלים]] |
|||
[[hu:Komplementer gráf]] |
|||
[[pl:Dopełnienie grafu]] |
|||
[[sk:Komplement grafu]] |
|||
[[sr:Комплемент графа]] |
2024年5月24日 (金) 19:13時点における最新版
![]() | この記事は英語版の対応するページを翻訳することにより充実させることができます。(2024年5月) 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
![](http://upload.wikimedia.org/wikipedia/commons/d/d0/Complement_graph_sample.png)
補グラフ(ほグラフ、英: complement graph)は、グラフ理論の用語。グラフ にとっての補グラフとは、 において隣接している頂点が補グラフでは必ず隣接していないことと同値である。したがって、あるグラフの補グラフを作成するには、そのグラフの存在しない辺を全て描き、既存の辺を全て消去すればよい。グラフの差集合とは異なり、辺だけが相補的である。
形式的構築
[編集]頂点群 と辺群 のグラフ があるとき、その補グラフ は以下のように構築される。
- である。
- 個の頂点のクリーク について、 とする。
補グラフは、ラムゼー理論などのグラフ理論で使われ、NP完全問題であることの証明にも使われる。