3-Colorear un gráfico utilizando fórmulas proposicionales

Question

Hola a todos, estoy estudiando para un examen en la lógica y computabilidad, estoy tratando de abordar un problema específico, por lo que cualquier ayuda sería muy apreciada:

Deje $G = (V,E)$ ser un grafo no dirigido con conjunto de vértices $V$ y el conjunto de borde $E$. 3-coloración de $G$ es un mapa de $\chi:V\to \{R,G,Y\}$ que si $\{x,y\}\in E$ entonces $\chi(x)\neq \chi(y)$. (Deje $R,G,Y$ soporte para: rojo, azul y amarillo, respectivamente).

Supongamos $n > 1$ y deje $V_n = \{0,1,\cdots,n-1\}$ y deje $G_n = (V_n,E_n)$ ser un grafo no dirigido con conjunto de vértices $V_n$. Para cada $i$, $0 \leq i < n$ deje $R_i,B_i,Y_i$ ser variables proposicionales. Podemos pensar de $i$ ser un nodo para $R_i$ dice nodo $i$ tiene un color de rojo.

Dar una fórmula proposicional $A_n$ utilizando las variables $\{R_i,B_i,Y_i | 0 \leq i < n\}$ tal que $A_n$ es válido iff $G_n$ 3 para colorear. Hacer esto de tal manera que $A_n$ puede ser calculada de manera eficiente de $G_n$ (por ejemplo, no definen $A_n$ a $R_1$ si $G_n$ tiene tres y coloración ($R_1 \wedge \neg R_1$) de lo contrario).

Mi inclinación por una pregunta como esta es establecer algún tipo de CNF fórmula, que es venir con un conjunto de cláusulas que establecen cuidar de diferentes propiedades. Por ejemplo, yo creo que para que algo como esto necesito una cláusula en la que se aborda el caso de que cada nodo tiene un color, tal vez uno que se ocupa de cada nodo puede tener más de un color, y en el que cada nodo no puede ser del mismo color que un nodo adyacente? No estoy realmente seguro de cómo ilustrar que la última o si hay casos que me estoy perdiendo. Gracias por la ayuda!

$\textbf{NOTE}$ I poner esto bajo la etiqueta de la tarea, ya que es la tarea en el sentido de que necesito aprender para mi examen pero no va a ser marcado.

Answer 1

La fórmula puede ser algo como $$\bigwedge_{i} \Big( (R_i\vee G_i\vee Y_i) \wedge (\neg R_i\v \neg G_i) \wedge (\neg R_i\v \neg Y_i) \wedge (\neg G_i\v \neg Y_i)\Big) \wedge \\ \bigwedge_{(i,j)\in E} \Big( (\neg R_i\v \neg R_j) \wedge (\neg G_i\v \neg G_j) \wedge (\neg Y_i\v \neg Y_j) \Big)$$ La primera parte establece que cada vértice tiene un color, pero sólo uno. La segunda parte dice que el vecino vértices tienen diferentes colores.