Hace poco me reuní con una profesora para discutir este problema y no tenía una respuesta sobre cómo hacer el cálculo. Lo que sí aprendí es que el conteo en sí se considera NP-Duro y está en una clase conocida como #P. Actualmente estoy ejecutando un eficiente 4-coloración en un mapa de los EE.UU. (contiguo 48) y tenía la esperanza de ser capaz de comparar el recuento de la fuerza bruta con un valor conocido.
Se agradece cualquier ayuda.
¿Está usted familiarizado con el polinomio cromático para un gráfico?
La idea es la siguiente: Que $\chi(G)$ sea el número de 4 coloraciones del gráfico $G$ .
Considere estos tres gráficos:
A. 
B. 
C. 
(Donde los dos óvalos son iguales en cada caso, y podrían estar conectados por otras aristas no mostradas).
Afirmo que $\chi(A) = \chi(B) + \chi(C)$ . Porque en cualquier coloración de $A$ Los dos vértices indicados pueden ser del mismo color o de colores diferentes. Pero cualquier coloración en la que los dos vértices tengan el mismo color puede convertirse en una coloración de $B$ Y cualquier coloración en la que los dos vértices tengan colores diferentes puede convertirse en una coloración de $C$ y viceversa, por lo que estos también son equinuméricos. Así que el número de coloraciones de $A$ es igual al número de coloraciones de $B$ más el número de coloraciones de $C$ .
Invirtiendo esta relación, tenemos $$\chi(C) = \chi(A) - \chi(B)\tag{$\star$}$$ lo cual es útil porque ambos $A$ y $B$ son estrictamente más simples que $C$ : $A$ tiene una arista menos que $C$ y $B$ tiene una arista y un vértice menos. Así que podemos calcular $\chi(C)$ en términos de gráficos más simples.
Utilizando estas relaciones podemos calcular, para cualquier gráfico $G$ el número de $4$ -colores de $G$ .
Por ejemplo, empecemos por observar que $\chi(\bullet) = 4$ y $\chi(\bullet\bullet) = 16$ . Ahora bien, por relación $(\star)$ tenemos $\chi($
$) = \chi(\bullet\bullet)-\chi(\bullet) = 16-4 = 12.$
Ahora vamos a calcular $\chi($ 
$)$ . Esto es igual a $\chi($
$)-\chi($$)$ de la que podemos sacar el factor $\chi($$)$ plazo, obteniendo $\chi($$)\cdot(\chi(\bullet)-1)$ . Sabemos que el término de la izquierda es 12 por el cálculo anterior, y el de la derecha es 3, por lo que el total es $12\cdot 3=36$ .
La dificultad aquí (y debe haber una, porque el problema es #P-completo) es que cada recursión tiende a duplicar el número de evaluaciones de $\chi$ que se requiere. Por lo tanto, una evaluación ingenua en el gráfico de la frontera de los Estados Unidos requerirá $2^{48}$ pasos, lo que resulta prohibitivo.
Pero el gráfico de Estados Unidos es de un tipo muy especial. Es plano y está formado casi exclusivamente por triángulos. (Sólo contiene dos ciclos primitivos de 4, y ningún ciclo primitivo de más de 4 vértices). Así que uno podría esperar que, eligiendo el orden de recursión correcto, uno podría reducir el gráfico de 48 vértices rápidamente a un gráfico estrictamente más pequeño y más simple.
Por ejemplo, supongamos que $G$ es un gráfico que tiene un triángulo colgante que no está conectado de otra manera al gráfico, como ocurre en el caso de Washington, que sólo limita con Idaho y Oregón, que limitan entre sí. En este caso se puede demostrar fácilmente, utilizando las reglas anteriores, que $\chi(G)=2\chi(G')$ , donde $G'$ se obtiene de $G$ eliminando a Washington. La reducción $G'$ tiene sólo 47 vértices, y podría tener otro triángulo similar que podría ser eliminado de forma similar.
Creo que esto podría funcionar para este ejemplo en particular.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
