teorema de cuatro y cinco colores

TEOREMAS:LOS CUATRO Y

CINCO COLORES

Rosa E. Padilla TorresPresentación para la clase Teorías de

GrafosMATE 6200

Dr. Álvaro Lecompte Montes28 de junio de 2011

Historia

• El problema de los cuatro colores se remonta al 1852 cuando Francis Guthrie plantea el mismo a su hermano Frederick y luego llega a manos de Augustus de Morgan.

• En 1879, Sir Alfred Bray Kempe publica una demostración del mismo. En esta demostración, Percy Heawood descubre un error.

• Desde ese momento en adelante, a lo largo de los años se siguen las demostraciones, ya que ninguna es del todo aprobada.

• No fue hasta el 1996 que N. Robertson, D.P. Sanders, P. Seymour, y R. Thomas que mejoran la demostración con la ayuda de una computadora con sólo 633 configuraciones.

Grafos Integrables

• Un grafo se dice que es integrable cuando se puede dibujar a partir de los vértices de otro grafo.

• Si dos grafos están integrados y todos los vértices integran uno a uno, los grafos son isomorfos.

Grafo Plano

• Cuando el grafo es integrable, se le dice “grafo plano”.

• Un grafo plano es aquel cuyas aristas no se intersecan.

• No pueden dividirse en sub grafos.

Teorema de los cinco colores

• En todo grafo plano, sus vértices se pueden colorear con cinco colores.

• Este teorema se demuestra por contradicción. Se asume que existe un grafo crítico de 6 vértices que no puede ser coloreado con 5 colores.

• Otra forma en la que probaron este teorema es por inducción.

Demostración con cinco colores

• Este es el caso más crítico de un grafo plano de grado 5.

• El teorema establece que un vértice de un color no puede estar unido por una arista a otro vértice del mismo color.

Demostración

• Este grafo se puede colorear con aún menos de 5 colores.

Conjetura de los cuatro colores

• Del teorema de los cinco colores surge “La conjetura de los cuatro colores” en la cual se establece que en todo grafo plano, sus vértices se pueden colorear con sólo cuatro colores.

• Esta conjetura ha tomado más de cien años para poder resolverse.

Conjetura de los cuatro colores

• Dice que bastan 4 colores para colorear un mapa geográfico plano, de modo que dos países que con frontera en común tengan diferente color.

• Dos regiones no pueden tocarse sólo en un punto, y así se pueden ignorar regiones con una única frontera.

El Problema de los Cuatro Colores

• Establece que un grafo plano de k lados se puede colorear con cuatro colores de forma tan que dos lados vecinos no tengan el mismo color.

Teorema 9.11 • Las siguientes aseveraciones son

equivalentes:i. En todo grafo plano se pueden

colorear sus vértices con 4 colores.ii. En todo grafo plano, se pueden

colorear sus “ caras” con 4 colores.iii. Todo grafo plano de dos bordes

conectados con un grafo regular de grado 3 se puede colorear con 3 colores.

Regiones

En un problema topológico, no importa la forma de las regiones, sino cómo están colocadas unas respecto a otras.

Mapa esférico

• Para poder colorear un mapa esférico, sólo basta con proyectarlo sobre un plano.

Mapa Mundi

Mapa Puerto Rico

El problema de los cuatro colores se puede utilizar para colorear cualquier región de

un dibujo

Teorema Fundamental de Euler

• La proyección estereográfica, permite pasar de poliedros a mapas: en efecto, se infla el poliedro sobre una esfera, se proyecta estereográficamente y se obtiene entonces una imagen plana del poliedro original.

• Así la fórmula de Euler para mapas se deduce de la correspondiente fórmulas para poliedros, es decir:– Núm(regiones) – núm(líneas frontera) +

núm(puntos de encuentro) =2

Bibliografía

• J. A. Bondy, U. S. R. Murty; Graph Teory with Applications; 1976; páginas 156 – 160.

• J. A. Bondy, U. S. R. Murty; Graph Teory; 2008; páginas 287 – 295; 357-413.

Sitios de referencia

• http://mimosa.pntic.mec.es/jgomez53/matema/proteo/cuatro_colores.htm

• http://www.cidse.itcr.ac.cr/revistamate/MundoMatematicas/Vol5n1Jun2004/node8.html

• http://divulgamat.ehu.es/weborriak/TestuakOnLine/04-05/PG-04-05-macho.pdf

• 17 de mayo de 2011, http://es.wikipedia.org/wiki/Teorema_de_los_cuatro_colores

GRACIAS POR SU ATENCIÓN

http://rosaepadilla.blogspot.com