Réduire le problème de 3 colorants aux représentants du trio

Question

Un groupe d'étudiants est divisé en trios - groupes de 3 membres.Chaque étudiant peut être affecté à plus de Trio.Nous voulons assigner leurs représentants en choisissant exactement un membre de chaque trio.Est une telle affectation possible?

Mon objectif est d'utiliser des réductions de temps polynomial pour transformer la 3-coloration d'un graphique dans ce problème.Cependant, je suis coincé sur la bonne représentation.

• Si chaque sommet est un élève et des bords différents représentent être dans le même trio, comment séparer les trios?

• Si chaque nœud représente un trio, quelle pourrait être une signification sensible des bords?

Je soupçonne que, étant donné qu'une clé 4 est adéquate 3-coloration (ce qui pourrait également signifier que 4 trios avec les mêmes trois membres n'ont pas d'affectation représentative possible), cette dernière option pourrait être plus sensible, mais je ne suis passûr sur la façon de procéder à cette preuve de réduction.

Answer 1

let $ g= (v, e) $ est une instance de 3 $ coloriage. Construire une instance $ \ phi $ de 3-SAT comme suit.

• pour chaque sommet $ v \ in v $ créer $ 3 $ variables $ v_a, v_b, v_c $ représentant la $ 3 $ méthodes possibles de la couleur de $ V $ .
• pour chaque sommet $ v \ in v $ créer les clauses $ (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}) $ . Cela code le fait que $ v $ doit être coloré par exactement une couleur.
• pour chaque bord $ (u, v) \ in e $ créer les clauses $ (\ overline {v_a} \ VEE \ Overline {u_a}) \ wedge (\ overline {v_b} \ vee \ overline {u_b}) \ wedge (\ overline {v_c} \ vee \ overline {u_c}) $ . Cela garantit que u $ u $ et $ v $ ne peut pas être donné la même couleur.

Il est clair que la réduction ci-dessus peut être effectuée dans le temps poylnomial et garantit qu'il existe une affectation satisfaisante à $ \ Phi $ iff il y a un 3-Coloring pour < Span Classe="Math-Conteneur"> $ G $ .

transformez maintenant l'instance $ \ phi $ de 3-sat dans un équivalent d'instance $ \ phi '$ < / SPAN> de 1-in-3 SAT (voir ici pour la définition de 1-en-3 SAT et de la réduction de 3-SAT).

Nous avons donc montré que 3-colorants est réductible en polynôme réductible à 1-en-3 SAT. Il s'avère que 1-in-3 SAT est exactement votre problème: l'ensemble des étudiants est l'ensemble de variables et, pour chaque clause $ \ {x_i, x_j, x_k \} $ $ Vous créez un groupe contenant des étudiants $ x_i $ , $ x_j $ et ="Conteneur mathématique"> $ x_k $ . La définition d'une variable pour true correspond à la sélection de l'étudiant correspondant en tant que chef de file.