「グラフ彩色問題」の版間の差分
ナビゲーションに移動
検索に移動
細 ("グラフ彩色問題" を保護しました。 [edit=sysop:move=sysop]) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
与えられたグラフに対して, 隣接する頂点同士が異なる色になるような彩色の仕方を頂点彩色(vertex coloring)あるいは単に彩色(coloring)と呼ぶ. 必要となる色数が最小の頂点彩色を求める問題を頂点彩色問題と呼び, このときの色数を彩色数(coloring number)と呼ぶ. この他にグラフ彩色問題には, 頂点を共有する辺同士を異なる色になるように最小の色数で辺を彩色する辺彩色問題などのバリエーションがある. | 与えられたグラフに対して, 隣接する頂点同士が異なる色になるような彩色の仕方を頂点彩色(vertex coloring)あるいは単に彩色(coloring)と呼ぶ. 必要となる色数が最小の頂点彩色を求める問題を頂点彩色問題と呼び, このときの色数を彩色数(coloring number)と呼ぶ. この他にグラフ彩色問題には, 頂点を共有する辺同士を異なる色になるように最小の色数で辺を彩色する辺彩色問題などのバリエーションがある. | ||
| + | |||
| + | [[Category:組合せ最適化|ぐらふさいしょくもんだい]] | ||
2008年11月8日 (土) 20:03時点における最新版
【ぐらふさいしょくもんだい (graph coloring problem)】
与えられたグラフに対して, 隣接する頂点同士が異なる色になるような彩色の仕方を頂点彩色(vertex coloring)あるいは単に彩色(coloring)と呼ぶ. 必要となる色数が最小の頂点彩色を求める問題を頂点彩色問題と呼び, このときの色数を彩色数(coloring number)と呼ぶ. この他にグラフ彩色問題には, 頂点を共有する辺同士を異なる色になるように最小の色数で辺を彩色する辺彩色問題などのバリエーションがある.