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