Dentro del estudio de algoritmos, y más concretamente en la asignatura que imparto en los dos grados de informática de la universidad de Extremadura en Cáceres, denominada «Análisis y Diseño de Algoritmos» (AyDA), los grafos juegan un papel importante.
Los grafos son estructuras de datos que vienen determinados por un conjunto de puntos (llamados vértices o nodos) y un conjuto de aristas o líneas que unen dichos pares de vértices. Leonhard Euler (1707-1783) por su reflexión sobre los puentes de Königsberg se le considera el pionero en la teoría de grafos (ciclos eulerianos).
Los grafos tienen multitud de aplicaciones a la vida real: GPS, mapas, organigramas, planificación de costes, Internet, química, arquitectura, urbanismo, juegos, redes sociales, etc.
Bien, dentro de los grafos, los que se llaman PLANOS han adquirido una especial importancia. Un grafo plano es aquel en que sus aristas no se cruzan, salvo en sus vértices. Un ejemplo bastante ilustrativo es el de los cables de un circuito electrónico, que si se cruzan a la hora de unir distintos componentes, se puede producir un cortocircuito.
Las dos figuras siguientes a modo de ejemplo pueden parecer que NO representan un grafo plano …
Pero podrían representarse respectivamente de otra forma, y así si serían grafos planos 🙂
Hay un problema famoso de 3 familias enemigas y tres pozos que ayuda a ilustrar la problemática que estamos tratando de plantear y que es conocido a nivel mundial en el desarrollo de la teoría de grafos. Se trata de 3 familias enemistadas entre sí (F1, F2 y F3) y en frente hay 3 pozos, de los cuales siempre hay 1 lleno y 2 vacíos (P1, P2 y P3). Las familias desean acceder desde su casa a cualquiera de los 3 pozos, pero sin cruzarse nunca con ninguno de los miembros de las otras dos familias. Se trata efectivamente de buscar un grafo plano que nos permita ver si esto tiene solución … (los dos grafos de la parte superior son el mismo).
La respuesta es negativa, no puede ser 🙁 podríamos llegar a pintar los dos siguientes grafos, pero al tratar de «dibujar» una última arista, nuestro grafo deja de ser plano (los dos grafos de la parte inferior).
Una vez introducidos los grafos planos, históricamente la pregunta clave es en la línea argumental planteada es ¿cuántos colores son suficientes para pintar un mapa, donde los países ADYACENTES no pueden tener el mismo color? ¿Cuál es la mínima cantidad de colores necesaria para colorear el grafo de forma que zonas forntera común tengan colores diferentes? (se entiende que la frontera no debe reducirse a un único punto) [Ejemplo gráfico: zonas de Liechtenstein con únicamente 4 colores].
Los grafos coloreables con 2 ó 3 colores, están perfectamente estudiados y con su correspondiente demostración matemática. Por ejemplo un caso muy conocido es el de trazar líneas rectas al azar sobre un plano y se puede demostrar que con dos colores son más que suficientes, como ocurre con un tablero de ajedrez (blanco y negro).
En la siguiente figura se pueden grafos planos simples, donde cada número representa un color:
En 1852 Francis Guhrie observando mapas, tuvo la intuición de que era posible colorearlos con 4 colores de forma que zonas con frontera común tuvieran colores diferentes. Aquí empezó la aventura … Nadie lo pudo demostrar matemáticamente desde un punto de vista formal. A partir de 1950 ya se pudo ver que mapas con menos de 36 países se podían colorear con 4 colores. En 1970 y 1976 los matemáticos Kenneth Appel y Wolfgang Haken de la Unviersidad de Illinois en Urbana-Champaign lograron, con la ayuda de un ordenador y distinguiendo miles de casos, dar la buena nueva: «cuatro colores son suficientes».
Esta inclusión de las CIENCIAS DE LA COMPUTACIÓN en las demostraciones matemáticas (más allá de los colores) ha abierto una nueva forma de trabajar en el mundo de las demostraciones de la matemática clásica. Prueba de la importancia de este hecho es el SELLO del servicio postal de los Estados Unidos con la frase «Cuatro colores son suficientes» (FOUR COLORS SUFFICE):
Sin embargo, sigue pendiente una demostración clásica (enero de 2013).
FUENTE: Libro de Claudi Alsina: «Mapas del metro y redes neuronales», editorial El mundo es Matemático, 2010.
(vía la puerta de mi amigo Antonio Gordillo 🙂
¡Muy buen artículo! De veras, he estado leyendo tu weblog y creo que compartes un buen contenido de calidad. Me sorprende que no tengas más comentarios, buen trabajo.
Muy bien explicado! gracias por la info