Teorema de los cinco colores

Los mapas planares requieren como máximo cinco colores

Un mapa de cinco colores

El teorema de los cinco colores es un resultado de la teoría de grafos que establece que, dado un plano separado en regiones, como un mapa político de los países del mundo, las regiones pueden colorearse utilizando no más de cinco colores, de tal manera que ninguna de las dos regiones adyacentes reciba el mismo color.

El teorema de los cinco colores está implícito en el teorema de los cuatro colores , que es más fuerte, pero es considerablemente más fácil de demostrar . Se basó en un intento fallido de prueba de los cuatro colores por parte de Alfred Kempe en 1879. Percy John Heawood encontró un error 11 años después y demostró el teorema de los cinco colores basándose en el trabajo de Kempe.

Esquema de la prueba por contradicción

En primer lugar, se asocia un grafo plano simple al mapa dado, es decir, se coloca un vértice en cada región del mapa y luego se conectan dos vértices con una arista si y solo si las regiones correspondientes comparten una frontera común. El problema se traduce entonces en un problema de coloración de grafos: hay que pintar los vértices del grafo de modo que ninguna arista tenga extremos del mismo color. ${\displaystyle G}$

Debido a que es un plano simple , es decir, puede estar incrustado en el plano sin aristas que se intersequen, y no tiene dos vértices que compartan más de una arista, y no tiene bucles, entonces se puede demostrar (usando la característica de Euler del plano) que debe tener un vértice compartido por como máximo cinco aristas. (Nota: Este es el único lugar donde se usa la condición de cinco colores en la prueba. Si se usa esta técnica para probar el teorema de los cuatro colores, fallará en este paso. De hecho, un grafo icosaédrico es 5-regular y plano, y por lo tanto no tiene un vértice compartido por como máximo cuatro aristas). Encuentre dicho vértice y llámelo . ${\displaystyle G}$ ${\displaystyle v}$

Ahora eliminemos de . El grafo obtenido de esta manera tiene un vértice menos que , por lo que podemos suponer por inducción que puede colorearse con solo cinco colores. Si la coloración no utilizó los cinco colores en los cinco vértices vecinos de , puede colorearse con un color no utilizado por los vecinos. Así que ahora observemos esos cinco vértices , , , , que eran adyacentes a en orden cíclico (lo que depende de cómo escribimos G). Así que podemos suponer que , , , , están coloreados con los colores 1, 2, 3, 4, 5 respectivamente. ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle G'}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{3}}$ ${\displaystyle v_{4}}$ ${\displaystyle v_{5}}$ ${\displaystyle v}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{3}}$ ${\displaystyle v_{4}}$ ${\displaystyle v_{5}}$

Ahora considere el subgrafo de que consiste en los vértices que están coloreados con los colores 1 y 3 solamente y las aristas que los conectan. Para ser claros, cada arista conecta un vértice de color 1 a un vértice de color 3 (esto se llama una cadena de Kempe ). Si y se encuentran en diferentes componentes conexos de , podemos intercambiar los colores 1 y 3 en el componente que contiene sin afectar la coloración del resto de . Esto libera el color 1 para completar la tarea. Si por el contrario y se encuentran en el mismo componente conexo de , podemos encontrar un camino para unirlos que consiste solo en vértices de color 1 y 3. ${\displaystyle G_{1,3}}$ ${\displaystyle G'}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{3}}$ ${\displaystyle G_{1,3}}$ ${\displaystyle v_{1}}$ ${\displaystyle G'}$ ${\displaystyle v}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{3}}$ ${\displaystyle G_{1,3}}$ ${\displaystyle G_{1,3}}$

Ahora, pasemos al subgrafo de que consta de los vértices que están coloreados con los colores 2 y 4 solamente y las aristas que los conectan, y apliquemos los mismos argumentos que antes. Entonces, o bien podemos invertir la coloración 2-4 en el subgrafo de que contiene y pinta el color 2, o podemos conectar y con un camino que consta solamente de los vértices de los colores 2 y 4. Un camino de este tipo intersectaría el camino de 1-3 colores que construimos antes, ya que a través de estaban en orden cíclico. Esto es claramente absurdo, ya que contradice la planaridad del grafo. ${\displaystyle G_{2,4}}$ ${\displaystyle G'}$ ${\displaystyle G_{2,4}}$ ${\displaystyle v_{2}}$ ${\displaystyle v}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{4}}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{5}}$

De hecho, puede ser de cinco colores, contrariamente a la presunción inicial. ${\displaystyle G}$

Algoritmo de cinco colores en tiempo lineal

Varios autores, comenzando con Lipton y Miller en 1978, han estudiado algoritmos eficientes para grafos planares de cinco colores. El algoritmo de Lipton y Miller tomó tiempo , ^[1] pero investigadores posteriores redujeron el límite de tiempo a . ^{[2] [3] [4] [5] [6]} La versión a continuación es de un artículo de 1996 de Robertson, Sanders, Seymour y Thomas, que lo describe brevemente en conexión con un algoritmo de tiempo más lento para cuatro colores. ^[7] El algoritmo como se describe aquí opera en multigrafos y se basa en la capacidad de tener múltiples copias de aristas entre un solo par de vértices. Se basa en el teorema de Wernicke , que establece lo siguiente: ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$

Teorema de Wernicke : supongamos que G es plano, no vacío, no tiene caras limitadas por dos aristas y tiene un grado mínimo de 5. Entonces G tiene un vértice de grado 5 que es adyacente a un vértice de grado como máximo 6.

Utilizaremos una representación del gráfico en la que cada vértice mantiene una lista enlazada circular de vértices adyacentes, en orden planar en el sentido de las agujas del reloj.

En teoría, el algoritmo es recursivo: reduce el gráfico a un gráfico más pequeño con un vértice menos, colorea ese gráfico con cinco colores y luego usa esos colores para determinar un color para el gráfico más grande en tiempo constante. En la práctica, en lugar de mantener una representación gráfica explícita para cada gráfico reducido, eliminaremos vértices del gráfico a medida que avanzamos, los agregaremos a una pila y luego los colorearemos a medida que los extraemos de la pila al final. Mantendremos tres pilas:

• S ₄ : Contiene todos los vértices restantes con grado cuatro como máximo, o grado cinco y como máximo cuatro vértices adyacentes distintos (debido a múltiples aristas).
• S ₅ : Contiene todos los vértices restantes que tienen grado cinco, cinco vértices adyacentes distintos y al menos un vértice adyacente con grado como máximo seis.
• S _d : Contiene todos los vértices eliminados del gráfico hasta el momento, en el orden en que fueron eliminados.

El algoritmo funciona de la siguiente manera:

1. En el primer paso, colapsamos todos los bordes múltiples en bordes simples, de modo que el gráfico sea simple. A continuación, iteramos sobre los vértices del gráfico, colocando cualquier vértice que coincida con las condiciones para S ₄ o S ₅ en la pila correspondiente.
2. A continuación, siempre que S ₄ no esté vacío, extraemos v de S ₄ y eliminamos v del grafo, empujándolo hacia S _d , junto con una lista de sus vecinos en este punto del tiempo. Comprobamos cada antiguo vecino de v , empujándolo hacia S ₄ o S ₅ si ahora cumple las condiciones necesarias.
3. Cuando S ₄ se vuelve vacío, sabemos que nuestro grafo tiene un grado mínimo de cinco. Si el grafo está vacío, pasamos al paso final 5 que se muestra a continuación. De lo contrario, el teorema de Wernicke nos dice que S ₅ no está vacío. Extraemos v de S ₅ , lo eliminamos del grafo y dejamos que v ₁ , v ₂ , v ₃ , v ₄ , v ₅ sean los antiguos vecinos de v en el orden planar en el sentido de las agujas del reloj, donde v ₁ es el vecino de grado 6 como máximo. Comprobamos si v ₁ es adyacente a v ₃ (lo que podemos hacer en tiempo constante debido al grado de v ₁ ). Hay dos casos:
   1. Si v ₁ no es adyacente a v ₃ , podemos fusionar estos dos vértices en un único vértice. Para ello, eliminamos v de ambas listas de adyacencia circulares y, a continuación, empalmamos las dos listas en una sola lista en el punto en el que se encontraba v anteriormente. Siempre que v mantenga una referencia a su posición en cada lista, esto se puede hacer en tiempo constante. Es posible que esto pueda crear caras delimitadas por dos aristas en los dos puntos en los que se empalman las listas; eliminamos una arista de dichas caras. Después de hacer esto, insertamos v ₃ en S _d , junto con una nota de que v ₁ es el vértice con el que se fusionó. Cualquier vértice afectado por la fusión se agrega o elimina de las pilas según corresponda.
   2. De lo contrario, v ₂ se encuentra dentro de la cara delimitada por v , v ₁ y v ₃ . En consecuencia, v ₂ no puede ser adyacente a v ₄ , que se encuentra fuera de esta cara. Fusionamos v ₂ y v ₄ de la misma manera que v ₁ y v ₃ anteriormente.
4. Vaya al paso 2.
5. En este punto, S ₄ , S ₅ y el gráfico están vacíos. Extraemos vértices de S _d . Si el vértice se fusionó con otro vértice en el paso 3, el vértice con el que se fusionó ya estará coloreado y le asignamos el mismo color. Esto es válido porque solo fusionamos vértices que no eran adyacentes en el gráfico original. Si lo hubiéramos eliminado en el paso 2 porque tenía como máximo 4 vértices adyacentes, todos sus vecinos en el momento de su eliminación ya estarán coloreados y simplemente podemos asignarle un color que ninguno de sus vecinos esté usando.

Prueba alternativa

Kainen (1974) ofrece una prueba simplificada del teorema de los cinco colores, basada en la no planaridad de K ₆ (el grafo completo con 6 vértices) y los menores del grafo . Esta prueba se generaliza a los grafos que se pueden hacer planos eliminando 2 aristas. ^[8]

Véase también

• Teorema de los cuatro colores

Referencias

1. Lipton, Richard J.; Miller, Raymond E. (1978), "Un método de procesamiento por lotes para colorear gráficos planares", Information Processing Letters , 7 (4): 185–188, doi :10.1016/0020-0190(78)90065-0, MR  0497394
2. Chiba, Norishige; Nishizeki, Takao; Saito, Nobuji (1981), "Un algoritmo de coloración lineal de 5 colores de gráficos planares", Journal of Algorithms , 2 (4): 317–327, doi :10.1016/0196-6774(81)90031-6, MR  0640516
3. Matula, David; Shiloach, Yossi; Tarjan, Robert (noviembre de 1980), Dos algoritmos de tiempo lineal para aplicar cinco colores a un gráfico plano (PDF) , Informe técnico STAN-CS-80-830, Universidad de Stanford
4. Frederickson, Greg N. (1984), "Sobre algoritmos de tiempo lineal para gráficos planares de cinco colores", Information Processing Letters , 19 (5): 219–224, CiteSeerX 10.1.1.158.5812 , doi :10.1016/0020-0190(84)90056-5, MR  0777802 
5. Williams, MH (1985), "Un algoritmo lineal para colorear gráficos planares con cinco colores", The Computer Journal , 28 (1): 78–81, doi : 10.1093/comjnl/28.1.78 , MR  0786929
6. Hagerup, Torben; Chrobak, Marek; Diks, Krzysztof (1989), "Coloración paralela óptima de 5 grafos planos", SIAM Journal on Computing , 18 (2): 288–300, doi :10.1137/0218020, MR  0986668
7. Robertson, Neil ; Sanders, Daniel P. ; Seymour, Paul ; Thomas, Robin (1996), "Cuatro colores eficientes de gráficos planares" (PDF) , Proc. 28.º Simposio ACM sobre teoría de la computación (STOC) , Nueva York: ACM Press.
8. Kainen, Paul C. (septiembre de 1974). "Una generalización del teorema de los cinco colores" (PDF) . Actas de la American Mathematical Society . 45 (3): 450–452. doi :10.2307/2039977. JSTOR  2039977.

Lectura adicional

• Heawood, PJ (1890), "Teoremas de colores de mapas", Quarterly Journal of Mathematics, Oxford , vol. 24, págs. 332–338