辺彩色のアルゴリズム

質問

グラフ理論についての質問です。

平面グラフを辺彩色するのに必要な色の最小の数を求めるアルゴリズムがあるとききました。
しかし、調べてみましたがどのようなものかわかりません。
知っている方いましたら教えてください。

回答No.2

azt82280

定理により
辺彩色に必要な色は次数に依存し，
辺彩色に必要な色数は最大次数以上で最大次数＋1以下の範囲ですべて彩色できます．
大概は最大次数と同じ色で彩色でき，
完全グラフの場合の時に最大次数＋1必要となります，

回答No.1

sgwjn

組合せ最適化問題の辺彩色のことですよね？

であるなら、必ず『必要な色の最小の数を求める』アルゴリズムは、総当りの列挙法しかないと思います。
理論上は、この方法で必ず最適解を求めることができます。
ただ、グラフの規模が大きくなると現実的な時間で解を求められなくなります。
ですので、組合せ最適化問題では、最適解の近似解を求める近似解法を使用するのが現実的です。
現在は、研究も近似解法についての研究が一般的なはずです。
組合せ最適化問題に対するこの辺のくだりはご存知ですよね？

この手のNP困難な問題に対する解法の研究は世界中で行われています。
最も高性能な近似解法をご希望であれば、それこそ国際学会で発表されるような研究者の論文を読むしかありません。
このような場所でポンっと最適な解法を挙げることができるような問題ならば、世界中で研究はされていないと思います。

以下に挙げる書籍で、辺彩色についてのアルゴリズムが紹介されているようです。
購入されて、ご自分でアルゴリズムを考えてみてはいかがでしょうか？

離散構造とアルゴリズム１
藤重 悟 編
徳山 豪／室田 一雄／加藤 直樹／西関 隆夫／中野 眞一／上野 修一　著
1992年7月15日 初版発行, ISBN4-7649-0194-3, 近代科学社