Reduciendo el problema de 3 colores a los representantes de trío

Question

Un grupo de estudiantes se divide en tríos: grupos de 3 miembros.Cada estudiante puede ser asignado a más de trío más.Queremos asignar a sus representantes, seleccionando exactamente uno miembro de cada trío.¿Es posible tal asignación?

Mi objetivo es usar reducciones de tiempo polinomial para transformar 3 colorantes de un gráfico en este problema.Sin embargo, estoy atrapado en la representación correcta.

• Si cada vértice es un estudiante y los bordes diferentes representan estar en el mismo trío, ¿cómo me separé trios?

• Si cada nodo representa un trío, ¿qué podría ser un significado sensato de los bordes?

Sospecho que, dado que una camarilla de 4 camas no tiene 3 colores (que también podría significar que 4 tríos con los mismos tres miembros no tienen una asignación representativa posible), la última opción podría ser más sensible, pero no estoySeguro de cómo proceder con esta prueba de reducción.

Answer 1

Permitir $ g= (v, e) $ ser una instancia de $ 3 $ colorear. Construir una instancia $ \ phi $ de 3-SAT de la siguiente manera.

• para cada vértice $ v \ in v $ Crear $ 3 $ variables $ V_A, V_B, V_C $ que representa el $ 3 $ Formas posibles de color de $ v $ .
• para cada vértice $ v \ in v $ Crear las cláusulas $ (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}) $ . Esto codifica el hecho de que $ v $ debe estar coloreado por un color.
• para cada borde $ (u, v) \ in e $ Crear las cláusulas $ (\ overline {v_a} \ vee \ overline {u_a}) \ wedge (\ endinline {v_b} \ vee \ overline {u_b}) \ wedge (\ overline {v_c} \ vee \ overline {u_c}) $ . Esto asegura que $ u $ y $ v $ no se le puede dar el mismo color.

Claramente, la reducción anterior se puede realizar en el tiempo de poilnomial y garantiza que existe una asignación satisfactoria a $ \ phi $ IFF hay un color de 3 colores para < Span Class="Math-contenedor"> $ G $ .

Ahora transforma la instancia $ \ phi $ de 3-sat en un equivalente de instancia $ \ phi '$ < / span> de 1-IN-3 SAT (ver aquí para La definición de 1-IN-3 se sentó y la reducción de 3-SAT).

Tenemos, por lo tanto, se muestra que 3 colorantes es el tiempo de polinomio reducible a 1-IN-3 SAT. Resulta que 1-IN-3 SAT es exactamente su problema: el conjunto de estudiantes es el conjunto de variables y, para cada cláusula $ \ {x_i, x_j, x_k \} $ Usted crea un grupo que contiene estudiantes $ x_i $ , $ x_j $ y $ x_k $ . La configuración de una variable en verdadero corresponde a seleccionar el estudiante correspondiente como líder.