「パーフェクトグラフ」の版間の差分
ナビゲーションに移動
検索に移動
細 ("パーフェクトグラフ" を保護しました。 [edit=sysop:move=sysop]) |
|||
| 2行目: | 2行目: | ||
グラフの頂点彩色を考えたときにクリークの各頂点は異なる色で塗らなければならない. すなわち, 任意のグラフに対して彩色数はクリーク数以上となる. 与えられたグラフ <math>G\,</math> のすべての頂点誘導部分グラフに対して, その彩色数とクリーク数が等しいとき, <math>G\,</math> をパーフェクトグラフと呼ぶ. パーフェクトグラフの補グラフもパーフェクトグラフとなることが知られている. | グラフの頂点彩色を考えたときにクリークの各頂点は異なる色で塗らなければならない. すなわち, 任意のグラフに対して彩色数はクリーク数以上となる. 与えられたグラフ <math>G\,</math> のすべての頂点誘導部分グラフに対して, その彩色数とクリーク数が等しいとき, <math>G\,</math> をパーフェクトグラフと呼ぶ. パーフェクトグラフの補グラフもパーフェクトグラフとなることが知られている. | ||
| + | |||
| + | 詳しくは[[《パーフェクトグラフ》|基礎編：パーフェクトグラフ]]を参照. | ||
2007年8月8日 (水) 20:42時点における版
【ぱーふぇくとぐらふ (perfect graph)】
グラフの頂点彩色を考えたときにクリークの各頂点は異なる色で塗らなければならない. すなわち, 任意のグラフに対して彩色数はクリーク数以上となる. 与えられたグラフ のすべての頂点誘導部分グラフに対して, その彩色数とクリーク数が等しいとき, をパーフェクトグラフと呼ぶ. パーフェクトグラフの補グラフもパーフェクトグラフとなることが知られている.
詳しくは基礎編：パーフェクトグラフを参照.