グラフ3-指定された関数を使用して着色する色

Question

私は出力を与える関数three_colorability(n,E)を持っていますtrue（これらのエッジと頂点を持つグラフを3色で着色できる場合）またはfalse（そうでない場合）。(!すでに何が着色されているかを知るためのパラメータはありません） この関数は線形時間の複雑さで動作すると仮定します。

多項式時間で動作する指定された関数を使用して、指定された無向グラフGの3色付けアルゴリズムを作成する必要があります。

私はこれに対する解決策に来ることができません。

Answer 1

という名前の3つの新しいノードを追加します C1, C2 と C3 彼らが表す色によって。新しいノード間にエッジを追加する (C1,C2), (C2,C3) と (C1,C3).もし three_colorability(V,E) が真であるよりも three_colorability(V+{C1,C2,C3},E+{(C1,C2),(C2,C3),(C1,C3)}) も真である。

各（元の）頂点について v, three_colorability() の2つのエッジが追加されたグラフの少なくとも1つに対してtrueを返します {(v,C1), (v,C2), (v,C3)}.例：もし three_colorability() エッジが追加されたグラフに対してtrueを返します {(v,C2), (v,C3)}, 、それはことを意味します v 色1で着色することができます。

すべての頂点の色を見つけるには、頂点の色を段階的に見つけて、これらの2つのエッジをグラフに追加します。