Teorema de los cinco colores

Los mapas planos requieren como máximo cinco colores.

Un mapa de cinco colores

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

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

Esquema de la prueba por contradicción

En primer lugar, se asocia un gráfico plano simple al mapa dado, es decir, se coloca un vértice en cada región del mapa, luego se conectan dos vértices con una arista si y sólo si las regiones correspondientes comparten un borde común. Luego, el problema se traduce en un problema de coloración de gráficos: hay que pintar los vértices del gráfico de modo que ningún borde 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 mostrar (usando la característica de Euler de la 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 los cinco colores en la demostración. Si se usa esta técnica para demostrar el teorema de los cuatro colores, fallará en este paso. De hecho, una gráfica icosaédrica tiene 5 regulares 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 retírelo de . El gráfico obtenido de esta manera tiene un vértice menos que , por lo que podemos suponer por inducción que se puede colorear con solo cinco colores. Si el coloreado no usó los cinco colores en los cinco vértices vecinos de , se puede colorear con un color que no usen los vecinos. Ahora mire esos cinco vértices , , , , que eran adyacentes en orden cíclico (que depende de cómo escribimos G). Entonces 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 que consta de los vértices que están coloreados únicamente con los colores 1 y 3 y los bordes que los conectan. Para ser claros, cada borde conecta un vértice de color 1 con un vértice de color 3 (esto se llama cadena de Kempe ). Si y se encuentran en diferentes componentes conectados 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 conectado de , podemos encontrar un camino para unirlos que consta solo de color 1 y 3 vértices. ${\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 pase al subgrafo que consta de los vértices que están coloreados solo con los colores 2 y 4 y los bordes que los conectan, y aplique los mismos argumentos que antes. Luego, podemos invertir la coloración 2-4 en el subgrafo que contiene y pintar el color 2, o podemos conectarnos con un camino que consta solo del color 2 y 4 vértices. Tal camino cruzaría el camino de 1 a 3 colores que construimos antes, ya que estaban en orden cíclico. Esto es claramente absurdo ya que contradice la planaridad del gráfico. ${\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 suposició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 gráficos planos de cinco colores. El algoritmo de Lipton y Miller tomó tiempo , ^[1] pero investigadores posteriores redujeron el tiempo limitado a . ^{[2] [3] [4] [5] [6]} La siguiente versión es de un artículo de 1996 de Robertson, Sanders, Seymour y Thomas, que la describe brevemente en relación con un algoritmo de tiempo más lento para cuatro colores. ^[7] El algoritmo descrito 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.

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

En concepto, el algoritmo es recursivo, reduce el gráfico a un gráfico más pequeño con un vértice menos, colorea cinco veces ese gráfico y luego usa esa coloración para determinar una coloración 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 los vértices del gráfico a medida que avanzamos, los agregaremos a una pila y luego los colorearemos a medida que los sacamos de la pila al final. Mantendremos tres pilas:

• S ₄ : Contiene todos los vértices restantes con grado como máximo cuatro 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 únicos, para que el gráfico sea simple. A continuación, iteramos sobre los vértices del gráfico, empujando cualquier vértice que coincida con las condiciones para S ₄ o S ₅ en la pila adecuada.
2. A continuación, siempre que S ₄ no esté vacío, sacamos v de S ₄ y eliminamos v del gráfico, empujándolo a S _d , junto con una lista de sus vecinos en este momento. Verificamos cada antiguo vecino de v , empujándolo hacia S ₄ o S ₅ si ahora cumple con las condiciones necesarias.
3. Cuando S ₄ queda vacío, sabemos que nuestra gráfica tiene un mínimo de grado cinco. Si el gráfico está vacío, vamos al último paso 5 a continuación. De lo contrario, el teorema de Wernicke nos dice que S ₅ no está vacío. Retire v de S ₅ , elimínelo del gráfico y deje que v ₁ , v ₂ , v ₃ , v ₄ , v ₅ sean los antiguos vecinos de v en orden plano en el sentido de las agujas del reloj, donde v ₁ es el vecino de grado como máximo 6. Comprobamos si v ₁ es adyacente a v ₃ (lo cual 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 solo vértice. Para hacer esto, eliminamos v de ambas listas de adyacencia circular y luego unimos las dos listas en una lista en el punto donde se encontró anteriormente v . Siempre que v mantenga una referencia a su posición en cada lista, esto se puede hacer en tiempo constante. Es posible que esto cree caras delimitadas por dos bordes en los dos puntos donde se unen las listas; eliminamos un borde de dichas caras. Después de hacer esto, empujamos v ₃ hacia 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 delineada 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 ₃ anteriores.
4. Vaya al paso 2.
5. En este punto S ₄ , S ₅ y la gráfica están vacías. Sacamos los 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 habrá sido coloreado y le asignaremos 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 al momento de su eliminación ya habrán sido coloreados, y simplemente podremos asignarle un color que ninguno de sus vecinos esté usando.

Prueba alternativa

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

Ver también

• Teorema de los cuatro colores

Referencias

1. Lipton, Richard J.; Miller, Raymond E. (1978), "Un método por lotes para colorear gráficos planos", 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 lineal de cinco colores para gráficos planos", Journal of Algorithms , 2 (4): 317–327, doi :10.1016/0196-6774(81)90031-6, MR  0640516
3. Matula, David; Siloé, Yosi; Tarjan, Robert (noviembre de 1980), Dos algoritmos de tiempo lineal para colorear un gráfico plano con cinco colores (PDF) , Tech. Informe STAN-CS-80-830, Universidad de Stanford
4. Frederickson, Greg N. (1984), "Sobre algoritmos de tiempo lineal para gráficos planos de cinco colores", Information Processing Letters , 19 (5): 219–224, CiteSeerX 10.1.1.158.5812 , doi :10.1016/0020- 0190(84)90056-5, SEÑOR  0777802 
5. Williams, MH (1985), "Un algoritmo lineal para colorear gráficos planos 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), "5 colores paralelos óptimos de gráficos planos", SIAM Journal on Computing , 18 (2): 288–300, doi :10.1137/0218020, MR  0986668
7. Robertson, Neil ; Lijadoras, Daniel P .; Seymour, Pablo ; Thomas, Robin (1996), "Gráficos planos de cuatro colores de manera eficiente" (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 Sociedad Matemática Estadounidense . 45 (3): 450–452. doi :10.2307/2039977.

Otras lecturas

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