3 colores es NP completo

Prerrequisito: NP-Completo , coloreado de gráficos

Problema de coloración K de gráficos : un problema de coloración K para gráficos no dirigidos es una asignación de colores a los Nodes del gráfico de modo que no haya dos vértices adyacentes que tengan el mismo color, y como máximo se utilizan K colores para completar el color del gráfico. 

Declaración del problema : dado un gráfico G (V, E) y un número entero K = 3, la tarea es determinar si el gráfico se puede colorear usando como máximo 3 colores, de modo que no se den dos vértices adyacentes del mismo color.

Explicación :
una instancia del problema es una entrada especificada para el problema. Una instancia del problema de 3 colores es un gráfico no dirigido G (V, E) , y la tarea es verificar si existe una posible asignación de colores para cada uno de los vértices V usando solo 3 colores diferentes con cada vecino coloreado de manera diferente. Dado que un problema NP-Completo es un problema que está tanto en NP como en NP-difícil , la prueba de la afirmación de que un problema es NP-Completo consta de dos partes:

1. El problema en sí está en la clase NP .
2. Todos los demás problemas en la clase NP pueden ser reducibles en tiempo polinomial a eso. (B es reducible en tiempo polinomial a C se denota como B ≤ P ^C )

Si solo se cumple la segunda condición , el problema se llama NP-Hard .

Pero no es posible reducir cada problema NP a otro problema NP para mostrar su NP-Completitud todo el tiempo. Por lo tanto, para mostrar que un problema es NP-Completo, entonces prueba que el problema está en NP y cualquier problema NP-Completo es reducible a eso, es decir, si B es NP-Completo y B≤P ^C entonces para C en NP, entonces C es NP-Completo. Por lo tanto, se puede concluir que el problema de coloración del gráfico K es NP-Completo utilizando las siguientes dos proposiciones:

El problema de 3 colores está en NP:
si algún problema está en NP, entonces, se entrega un certificado, que es una solución al problema y una instancia del problema (un gráfico G(V, E) y una asignación de los colores { c ₁ , c ₂ , c ₃ } donde a cada vértice se le asigna un color de estos tres colores {c ₁ , c ₂ , c ₃ } ), entonces se puede verificar (Comprobar si la solución dada es correcta o no) que el certificado en tiempo polinomial. Esto se puede hacer de la siguiente manera:

Para cada borde {u, v} en el gráfico G verifique que el color c(u) != c(v)

Por lo tanto, se puede verificar la corrección de la asignación en el tiempo polinomial del gráfico con respecto a sus bordes O(V+E).  

El problema de 3 colores es NP-Difícil:
Para probar que el problema de 3 colores es NP-Difícil, realice una reducción de un problema NP-Difícil conocido a este problema. Realice una reducción a partir de la cual el problema de 3-SAT se pueda reducir al problema de 3 colores. Supongamos que el problema 3-SAT tiene una fórmula 3-SAT de m cláusulas en n variables denotadas por x ₁ , x ₂ , …, x _n . El gráfico se puede construir a partir de la fórmula de la siguiente manera:

1. Para cada variable x _i Construya un vértice v _i En el gráfico y un vértice v _i’ que denote la negación de la variable x _i .
2. Para cada cláusula c en m, agregue 5 vértices correspondientes a los valores c1, c1, …, c5.
3. Además, se agregan tres vértices de diferentes colores para indicar los valores Verdadero, Falso y Base (V, F, B) respectivamente.
4. Se agregan aristas entre estos tres vértices adicionales T, F, B para formar un triángulo.
5. Se añaden aristas entre los vértices vi _y v _i’ y la Base (B) para formar un triángulo .

Las siguientes restricciones son verdaderas para el gráfico G:  

1. Para cada uno de los pares de vértices vi y vi _‘ , a uno se le asigna un valor VERDADERO y al otro FALSO _.
2. Para cada cláusula c en m cláusulas, al menos uno de los literales debe tener un valor VERDADERO para que el valor sea verdadero.

Por lo tanto, se puede construir un pequeño gráfico OR-gadget para cada una de las cláusulas c = (u V v V w) en la fórmula mediante los Nodes de entrada u, v, w, y conectando el Node de salida del gadget a los Nodes especiales Falso y Base.

Consideremos la fórmula f = (u’ V v V w’) Y (u V v V w’)

Ahora la reducción puede ser probada por las siguientes dos proposiciones:
Supongamos que la fórmula 3-SAT tiene una asignación satisfactoria, entonces en cada cláusula, al menos uno de los literales x _i tiene que ser verdadero, por lo tanto, el correspondiente v _i puede asignarse a un color VERDADERO y v _i’ a FALSO. Ahora, extendiendo esto, para cada cláusula, el gráfico OR-gadget correspondiente puede ser de 3 colores. Por lo tanto, el gráfico puede ser de 3 colores.

Consideremos que el gráfico G es de 3 colores, por lo que si el vértice vi se asigna al color verdadero, en consecuencia, la variable x _i se asigna a verdadero. Esto formará una cesión de verdad jurídica. Además, para cualquier cláusula C _j = (x V y V z) , no puede ser que los tres literales x, y, z sean falsos. Porque en este caso, la salida del gráfico OR-gadget para C _j tiene que ser de color Falso. Esto es una contradicción porque la salida está conectada a Base y False. Por lo tanto, existe una asignación satisfactoria a la cláusula 3-SAT.

Conclusión : Por lo tanto, la 3-coloración es un problema NP-Completo .