Portada
Favoritos| Portada |
Favoritos |
|||||
| Lista Articulos: [0-C] [C-I] [I-P] [P-Z] | Todas las categorías | Página aleatoria | Lo que enlaza aquí | ||||||
Objetivo: colorear un mapa usando únicamente cuatro colores, de modo que no existan dos zonas en contacto que usen el mismo color.
1º.- Primero vamos a demostrar que con tres o menos colores no podemos colorear cualquier mapa:
Dado el siguiente mapa trate de colorearlo usando 3 colores:
Puede intentarlo cuanto lo desee pues las 4 zonas que se pueden colorear están en contacto las unas con las otras y verá que si en cualquier par de ellas pinta el mismo color, estarán en contacto, como muestro en la siguiente figura:
Ahora lo pinto usando cuatro colores:
Cualquier figura podrá ser coloreada con sólo 4 colores como en el siguiente ejemplo:
Cualquiera podría indicarme que el dibujo está preparado y por eso me ha sido posible pintarlo con sólo 4 colores, pero intente usted mismo construir una figura que no pueda colorear con 4 colores.
2º.- La demostración matemática de esto es bien sencilla, para ello generaré un isomorfismo entre los mapas y los grafos, de modo que a través de este llegaremos a la conclusión de que 4 colores son suficientes para colorear cualquier mapa.
Lo primero es ver el isomorfismo: para ello definiré cada nodo del grafo como una zona con color y cada arista como una conexión existente entre dos zona que están en contacto. En los siguientes ejemplos se pueden ver con claridad los isomorfismos (a la izquierda el mapa y a la derecha el grafo):
Viendo esto es trivial pensar que cada nodo del grafo deberá tener un color distinto de los nodos adyacentes a este y que no podrán existir lazos (aristas con mismo origen y destino).
3º.- En este punto podemos orientar nuestra búsqueda a encontrar un mapa con cinco zonas que no pueda ser coloreado usando cuatro colores (es decir que necesite 5 colores como mínimo).
Para ello debemos fijarnos en un último detalle: ninguna arista puede ser cruzada por otra. Este es el punto más importante de toda la demostración, y la razón es que si esto ocurriese una de las aristas estaría separando las zonas (nodos) que conecta la otra arista.
a) En la siguiente figura vemos un grafo que representa a un mapa que ha podido ser coloreado usando sólo 4 colores:
b) Imaginemos que quisiésemos generar un grafo que usase 5 colores y que además todas sus zonas estuviesen en contacto entre sí como el que sigue:
c) Reorientando las conexiones quedaría la siguiente figura, en la que la línea azul y roja representan a la misma conexión y que muestran que para conectar el nodo morado con el verde debería de cruzar al menos una arista que une a otros dos nodos (bien la arista roja o la azul serían las que cortasen a otra).
Si tratamos de generar un mapa que represente a este grafo, cualquier intento de conectar al nodo verde con el morado sería inútil pues estaríamos separando a otros dos nodos ya conectados.
En la figura de 4 nodos vista anteriormente, el grafo resultante era el siguiente, por lo que sí permitía ser coloreado con 4 colores:
Como vemos en el tercer desarrollo, no se cruzaban las aristas del grafo, y esto permitía generar un mapa que nos obligase a colorearlo con 4 colores como mínimo.
Algebraicamente, los mínimos requisitos que se deben cumplir para encontrar un grafo que nos obligue a usar n-colores y que pueda ser representado en un plano son:
4º.- Demostración final:
No existe un grafo completo y plano mayor que K4.
Y según el isomorfismo dado, esto significa que es imposible construir un mapa que contenga 5 o más zonas diferenciadas que estén en contacto entre sí. Lo que demuestra estrictamente que un mapa puede ser coloreado sólo con 4 colores.
Documento realizado por: Juan Miguel Taboada Godoy (9 de junio de 2001) http://www.fibranet.org
El documento original se encuentra en: http://www.fibranet.org/contenidos/apuntes/buscador.php?tipo=documento&id=76
