Problemas interesantes en los mapas

Don Knuth está trabajando en el 4to volumen del Arte de la Programación Informática. Uno de los capítulos es sobre los Diagramas de Decisiones Binarias y sus aplicaciones, un tema que me parece muy interesante. Knuth sabe que una gran variedad de problemas interesantes con los grafos pueden ser codificados como fórmulas Boolean, y el BDD derivado representa todas las soluciones posibles del problema. A menudo hay algún tipo de criterio de optimización y es muy fácil extraer la “mejor” solución del BDD mediante un simple algoritmo dinámico de programación.

Aquí te mostramos algunos ejemplos, usando el grafo representando los 48 estados limítrofes con un nodo para cada estado, y un borde entre dos estados si comparten una frontera. Para cada uno de los mapas, si haces clic en la imagen, llegarás al documento fuente en formato SVG. Aquí está el grafo, ubicando los nodos en las capitales de los estados:

Tour de Capitales

Supongamos que quieres visitar las capitales de los 48 estados con el requerimiento de solo pasar a través de cada estado una vez. (En otras palabras, tú quieres encontrar un Camino Hamiltoneano en el grafo). Como puedes ver en el mapa anterior, si sigues la ruta más directa entre las capitales de los estados, a menudo pasarás a través de otro estado, o en el caso de ir de Lansing, Michigan a Madison, Wisconsin, tú conducirás sobre el Lago de Michigan. En cambio, deberías tomar la ruta de manejo más corta que permanezca dentro de los dos estados por cada etapa del viaje. Llamemos tal ruta un Tour de Capitales. Aquí puede encontrar un diagrama de las rutas permitidas entre los estados:

Basado en un simple análisis, además de los esfuerzos de Knuth, podemos decir lo siguiente:

  • Todos los tours deben comenzar o terminar en Maine, ya que Maine solo tiene un solo vecino. Nosotros usaremos a Maine como el punto inicial.
  • Todos los tours deben terminar más allá de Nueva York, ya que es un punto de articulación.
  • Hay 68.656.026 diferentes tours de capitales.

Este es el tour de capital más corto, totalizando 11.698 millas:

Este es el tour capital más largo, totalizando 18.040 millas:

Coloración del grafo

Otra interesante clase de problema involucra el colorear el mapa. La regla es que dos estados adyacentes no pueden tener el mismo color. El famoso Teorema de los Cuatro Colores indica que cualquier grafo plano puede ser coloreado como máximo con cuatro colores.

Ya que un BDD codifica todas las posibles soluciones de una fórmula Boolean, nosotros podemos calcular fácilmente cuántas soluciones hay. En la coloración de grafos, nosotros podemos ajustar nuestros recuentos para eliminar simetrías debido a la asignación arbitraria de valores de colores (¡4! Casos simétricos para 4 colores).

Para colorear los 48 estados limítrofes, existen 533.816.322.048 posibles colores. (Esta es la mitad del número reportado por Knuth, ya que su mapa incluye a Washington, DC como el “estado” número 49, y puede ser asignado por cualquiera de los dos colores no utilizados para Maryland y Virginia). Estos son algunos ejemplos interesantes de coloraciones especiales:

  • Una coloración balanceada, en la cual cada color es utilizado exactamente en 12 estados. Hay 12.554.677.864 coloraciones, lo cual es un sorprendentemente alto 2.4% de todas las posibles coloraciones.

  • Una coloración desbalanceada, en la cual uno de los colores (verde) es usado tan poco como sea posible (2 estados). Hay solo 288 formas de colorear el mapa, así ese color es usado solo dos veces.

  • Una coloración desbalanceada, en la cual uno de los colores (amarillo) es usado tanto como sea posible (18 estados). Hay 71.002.368 formas de colorear el mapa, así ese color es usado 18 veces.

  • Colorear ambos. Colorear utilizando los colores 2, 13, 15 y 18 veces. Esta secuencia 1) de izquierda a derecha, utiliza cada color en sucesión por el menor número de veces posibles, y 2) de derecha a izquierda, utiliza cada color en sucesión por el mayor número de veces posibles. Existen 24 soluciones.

Desde la perspectiva de los programas de coloración de gráficas, el mapa de 48 estados de los Estados Unidos es muy simple. Para un mapa más desafiante, ve a la siguiente página web sobre el Grafo McGregor.