グラフ3-指定された関数を使用して着色する色
-
20-12-2019 - |
質問
私は出力を与える関数three_colorability(n,E)を持っていますtrue(これらのエッジと頂点を持つグラフを3色で着色できる場合)またはfalse(そうでない場合)。(!すでに何が着色されているかを知るためのパラメータはありません) この関数は線形時間の複雑さで動作すると仮定します。
多項式時間で動作する指定された関数を使用して、指定された無向グラフGの3色付けアルゴリズムを作成する必要があります。
私はこれに対する解決策に来ることができません。
解決
という名前の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つのエッジをグラフに追加します。
所属していません StackOverflow