Coloreando mapas y grafos
- Autor:
- Rafael Losada Liste
- Tema(s):
- Construcciones, Diagramas
Esta actividad pertenece al libro de GeoGebra Redes y Grafos.
Fue una pregunta de coloreado de mapas la que impulsa definitivamente el desarrollo del estudio de los grafos. Esta pregunta, formulada en 1852 por un matemático inglés cuando aún era estudiante es: ¿será posible colorear cualquier mapa plano de regiones utilizando solo cuatro colores, de modo que no haya dos regiones vecinas del mismo color?
La respuesta, afirmativa, se conoce como teorema de los cuatro colores, pero se tardó más de un siglo en poder demostrarlo. Por fin, en 1970 se obtiene la demostración. Aun así, si bien el resultado es aceptado por la comunidad matemática, la demostración invita a la polémica pues hace uso de un complejo programa de ordenador cuyos resultados no son verificables manualmente. ¿Surgirá algún día otro genio que consiga realizar una “elegante demostración más humana” de este teorema, al estilo de Euler?
La coloración de grafos permite visualizar y analizar diferentes relaciones entre vértices conectados de un grafo. Por ejemplo, imagina que en una fiesta coinciden seis personas. Cada par de personas (hay 15 parejas posibles), o bien ya se conocen o bien son mutuamente desconocidas. Pues bien, un resultado conocido como Teorema de amigos y extraños, muy fácil de demostrar coloreando grafos, dice: “En cualquier grupo de seis personas, hay tres de ellas mutuamente conocidas o mutuamente desconocidas.”
En la siguiente aplicación puedes intentar colorear pequeños mapas con el mínimo de colores posible (número cromático). Recuerda que dos regiones vecinas no pueden tener el mismo color. Esto equivale a colorear los vértices del grafo dual de modo que se diferencien los colores de cualquier par de vértices extremos de la misma arista.
Autor de la actividad y construcción GeoGebra: Rafael Losada.