グラフ彩色問題

提供: ORWiki
2007年7月12日 (木) 00:20時点における122.17.2.240 (トーク)による版 (新しいページ: ''''【ぐらふさいしょくもんだい (graph coloring problem)】''' 与えられたグラフに対して, 隣接する頂点同士が異なる色になるような彩色...')
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

【ぐらふさいしょくもんだい (graph coloring problem)】

与えられたグラフに対して, 隣接する頂点同士が異なる色になるような彩色の仕方を頂点彩色(vertex coloring)あるいは単に彩色(coloring)と呼ぶ. 必要となる色数が最小の頂点彩色を求める問題を頂点彩色問題と呼び, このときの色数を彩色数(coloring number)と呼ぶ. この他にグラフ彩色問題には, 頂点を共有する辺同士を異なる色になるように最小の色数で辺を彩色する辺彩色問題などのバリエーションがある.