「パーフェクトグラフ」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: '【ぱーふぇくとぐらふ (perfect graph)】 グラフの頂点彩色を考えたときにクリークの各頂点は異なる色で塗らなければならない. すな...') |
|||
| 1行目: | 1行目: | ||
【ぱーふぇくとぐらふ (perfect graph)】 | 【ぱーふぇくとぐらふ (perfect graph)】 | ||
| − | グラフの頂点彩色を考えたときにクリークの各頂点は異なる色で塗らなければならない. すなわち, 任意のグラフに対して彩色数はクリーク数以上となる. 与えられたグラフ | + | グラフの頂点彩色を考えたときにクリークの各頂点は異なる色で塗らなければならない. すなわち, 任意のグラフに対して彩色数はクリーク数以上となる. 与えられたグラフ <math>G\,</math> のすべての頂点誘導部分グラフに対して, その彩色数とクリーク数が等しいとき, <math>G\,</math> をパーフェクトグラフと呼ぶ. パーフェクトグラフの補グラフもパーフェクトグラフとなることが知られている. |
2007年7月13日 (金) 03:42時点における版
【ぱーふぇくとぐらふ (perfect graph)】
グラフの頂点彩色を考えたときにクリークの各頂点は異なる色で塗らなければならない. すなわち, 任意のグラフに対して彩色数はクリーク数以上となる. 与えられたグラフ のすべての頂点誘導部分グラフに対して, その彩色数とクリーク数が等しいとき, をパーフェクトグラフと呼ぶ. パーフェクトグラフの補グラフもパーフェクトグラフとなることが知られている.
