Reduzieren Sie das 3-farbige Problem mit Vertretern von Trio

Question

Eine Gruppe von Studenten ist in Trios-Gruppen von 3 Mitgliedern unterteilt.Jeder Schüler kann mehr als mehr TRIO zugewiesen werden.Wir möchten ihre Vertreter, indem wir genau ein Mitglied jedes Trio-Mitglieds wählen.Ist eine solche Aufgabe möglich?

Mein Ziel ist es, Polynom-Zeit-Reduzierungen zu verwenden, um die 3-Färbung eines Graphen in dieses Problem umzusetzen.Ich stecke jedoch auf der richtigen Darstellung.

• Wenn jeder Scheitelpunkt ein anderer Student und die Kanten ist, repräsentieren Sie in demselben Trio, wie trennen Sie Trios TRIOS?

• Wenn jeder Knoten ein Trio darstellt, was könnte eine vernünftige Bedeutung der Kanten sein?

Ich vermute, dass, da ein 4-Clique keine angemessene 3-Färbung hat (was auch bedeuten könnte, dass 4 Trios mit den gleichen drei Mitgliedern keine mögliche repräsentative Zuordnung haben), kann die letztere Option sinnvoller sein, aber ich bin nichtsicher, wie Sie mit diesem Reduktionsnachweis fortfahren können.

Answer 1

let $ g= (v, e) $ Seien Sie ein Beispiel von $ 3 $ Färbung. Konstruieren Sie eine Instanz $ \ phi $ von 3-Sat wie folgt.

.
• für jeden Vertex $ v \ in V $ Erstellen $ 3 $ Variablen $ v_a, v_b, v_c $ Vertretung der $ 3 $ Mögliche Wege zur Farbe der $ V $ .
• Für jeden Scheitelpunkt $ v \ in V $ Erstellen Sie die Klauseln $ (v_a \ vee v_b \ vee v_c) \ wedge (\ overline {v_a} \ vee \ overline {v_b}) \ wedge (\ overline {v_b} \ vee \ overline {v_c}) \ wedge (\ overline {v_c} \ vee \ overline {v_a} \ vee \ overline {v_a}) $ . Dies kodiert die Tatsache, dass $ V $ von genau einer Farbe gefärbt sein muss.
• Für jede Kante $ (u, v) \ in E $ Erstellen Sie die Klauseln $ (\ Overline {v_a} \ vee \ overline {u_a}) \ wedge (\ overline {v_b} \ vee \ overline {u_b}) \ wedge (\ Overline {v_c} \ vee \ overline {u_c} \ vee \ overline {u_c}) $ . Dies stellt sicher, dass $ U $ und $ V $ nicht dieselbe Farbe gegeben werden kann.

Klar Die obige Reduktion kann in der Poylnomialzeit ausgeführt werden, und stellt sicher, dass es eine erfüllende Zuordnung zu $ \ phi $ iFF gibt, für < Span-Klasse="Math-Container"> $ g $ .

wandeln Sie nun die Instanz $ \ phi $ von 3-Sat in ein Äquivalent von Instanz $ \ phi '$ < / span> von 1-in-3 SAT (siehe hier für Die Definition von 1-in-3 saß und die Reduktion von 3 SAT).

Wir haben daher gezeigt, dass die 3-Färbung-Polynom-Zeit auf 1-in-3-SAT-SAT-SAT-SAT-SAT ist. Es stellt sich heraus, dass 1-in-3-Sat genau Ihr Problem ist: Der Satz von Studenten ist die Menge von Variablen und für jede Klausel $ \ {x_i, x_j, x_k \} $ Sie erstellen eine Gruppe mit Studenten $ x_i $ , $ x_j $ und $ x_k $ . Einstellen einer Variablen auf TRUE entspricht der Auswahl des entsprechenden Schülers als Anführer.