私はフォーラムでこの質問を見ました：http：//www.geeksforgeeks.org/archives/19042
無向グラフと数mが与えられた場合、グラフの2つの隣接する頂点が同じ色で着色されないように、グラフを最大m色で着色できるかどうかを判断します。
特定の解を見つけるのではなく、頂点の数をmの数と比較できるかどうか疑問に思っています。
私は何が欠けていますか？
質問する
263 次
1 に答える
2
頂点の数（|V|）が。よりも多い場合でも、色が付く可能性がありmます。
たとえば、2部グラフm>=2では、頂点の数に関係なく、任意のに色が付けられます。
ただし、クリークでは、実行可能な唯一の着色が必要ですm >= |V|
それで：
特定の解を見つけるのではなく、頂点の数をmの数と比較できるかどうか疑問に思っています。
もしm > = |V|-解決策があれば、しかし-もしm < |V|-私たちは何も導き出すことができません。とにかく答えがあるかもしれません。
ボーナス：一般的な場合のグラフ彩色は、古典的なNP完全問題の1つです。つまり、既知の多項式の解はなく、見つかった場合は、次のように導き出すことができます。P = NP
于 2012-05-10T11:37:25.223 に答える