NPC-Problem Mindestsumme der Vertex-Färbung

Question

für eine Grafik G und eine rechtliche Scheitelpunktfarbe ψ: v (g) → n von g,

sei Σψ (g) die Summe von ψ (v),

und eingestellt σ (g):= min Σψ (g),

wenn das Minimum über alle gültigen Scheitelpunktfarben von G.

reicht

beweisen, dass {(g, k): σ (g) ≤ k} ∈ Npc.

Ich dachte an die Reduktion von der Subset-Summe, aber mein Problem ist mit der Minute und nicht mit der Summe, ich verstehe nicht, wie man die Mindestunterbrechung durchführen kann. Ich bekam einen Tipp, um eine Reduktion von 3-nae-sat zu machen, aber ich verstehe nicht, wie. würde etwas helfen.Sogar eine Quelle, die ich über dieses Problem lesen kann, wenn Sie etwas über etwas wissen.

Answer 1

Wir reduzieren von 3 ° C, was folgendes Problem ist: Angesichts eines Graphen ist es 3-farbbar?

Angesichts eines Diagramms $ g= (V, E) $ , wir erstellen eine neue Grafik $ g '$ < / span> auf $ v \ times \ {1,2,3} $ , deren Kanten sind $$ \ {((i, a), (j, a)) \ Mid (i, j) \ in E, a \ in [3] \} \ cup \ {((i, a), (i, b) ) \ Mid i \ in v, 1 \ leq a In Worten nehmen wir drei Kopien von $ g $ und verbinden alle Kopien desselben Scheitelpunkts.

Wenn $ g $ 3-farbbar ist, dann $ g '$ kann 3-farbig sein: Angesichts einer 3-Färbung $ \ chi $ von $ V $ , farbe $ (i, a) $ mit der Farbe $ \ chi (i) + a \ bmod 3 $ . Die Summe der Farben ist $ 6 | V | $ .

Umgekehrt nehme an, dass $ g '$ eine Färbung $ \ chi' $ wessen Summe ist In den meisten $ 6 | v | $ . Beachten Sie, dass die drei Kopien jedes Scheitelpunkts $ (i, 1), (i, 2), (i, 3) $ verschiedene Farben zugewiesen werden müssen, die Summe an Zumindest $ 6 $ . Daher $ \ Sigma \ chi '\ GEQ 6 | V | $ für beliebig coloring $ \ Chi '$ und $ \ Sigma \ chi'= 6 | V | $ iff $ \ chi ' $ ist eine 3-Färbung. In Anbetracht eines der Kopien von $ g $ sehen wir, dass $ G $ 3-farbbar ist. < / p>