NPC問題頂点着色の最小合計

Question

グラフGと法的な頂点着色ν：v（g）→g、

σν（g）の合計（v）、

とセットσ（g）：= minσν（g）、

ここで、最小範囲はGのすべての有効な頂点配色の範囲で範囲を算出します。

それを証明する{（g、k）：σ（g）≦k}∈NPC

サブセット合計からの削減を考えたが、問題は最小になり、合計ではなく、最小値を確認する方法を理解していない。 私は3-Nae-Satからの削減をするためにヒントを得ましたが、私はどのように理解していません。 いくつかの助けに感謝します。あなたが何かについて知っていれば、私はこの問題について読むことができます。

Answer 1

3COLから減少します。これは次の問題です。グラフを考えると、それは3着色可能ですか？

グラフ $ g=（v、e）$ 、新しいグラフを構築します。 $ g '$ < / span> $ v \ times {1,2,3 \} $ 、そのエッジが $$ \ {（i、a）、（j、a））\ mid（i、j）\ in [3] \ \} \ cup \ {（（i、a）、（i、b） ）\ mid i \ in v、1 \ leq a つまり、 $ G $ の3コピーを取り、同じ頂点のすべてのコピーを接続します。

$ g $ の場合 $ g '$ は3色になることができます。 $ v $ の3色 $ \ chi（i）+ a \ bmod 3 $ のコンテナ "> $（i、a）$ 。色の合計は $ 6 | $ 。

逆に、 $ g '$ に $ \ chi' $ があるとします。 $ 6 | $ 。各頂点 $（i,1）、（i,2）、（i,3）、（i,3）、（i,3）、（i,3）、（i,3）、（i,3）、（i,3）、（i,3）、（i,3）、（i,3）、その合計を割り当てる必要があります。少なくとも $ 6 $ 。したがって、 $ \ sigma \ chi '\ geq 6 | v | の$ coloring $ \ CHI '$ 、および $ \ sigma \ chi'= 6 | $ iff $ \ chi ' $ は3色付けです。 $ g $ のコピーの1つを考えると、 $ g $ は3着色です。< / P>