analisis de entorno

Grafos y Colores

¿Qué es un grafo?
En matemáticas y ciencias de la computación, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, quepermiten representar relaciones binarias entre elementos de un conjunto.
Ejemplo:

A= aristas
V=vértices
V={A,B,C,D,E}
A={{E,B},{E,A},{D,C}}

Coloración de Grafos
 De manera simple, es lacoloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color.
El número de colores con que se colorea un grafo es denominado número cromático, que es el menor valorque puede tomar k, donde k es el número de colores con que se puede colorear el grafo.
Ejemplo:













Teorema de los cuatro colores
Este teorema establece que dado un grafocualquiera, este puede ser coloreado a lo más, con 4 colores, de manera que no queden nodos adyacentes con el mismo color.
En 1852 Francis Guthrie, observando mapas, tuvo la intuición de que era posiblecolorearlos con cuatro colores de forma que zonas con frontera común tuvieran colores diferentes. Francis Guthrie era un estudiante de Augustus De Morgan y formuló esa conjetura, que no pudo serprobada por Guthrie, ni por su hermano Frederick, que había sido también estudiante de De Morgan, ni por Sir William Rowan Hamilton, a quien De Morgan le escribió formulando la conjetura. En 1878 ArthurCayley presento formalmente este reto a la London Mathematical Society, quedando así el problema abietto a la consideración de todos.  En 1890, Percy John Heawood encontró un error en la demostraciónde Kempe. Heawood no pudo demostrar que la conjetura no era válida, pero siguió trabajando en el coloreo de mapas, pudiendo probar que con cinco colores se podía colorear cualquier mapa. En 1976 laconjetura tuvo demostración, gracias a Kenneth Appel y Wolfgang Haken, que utilizaron una computadora para la demostración, lo cual generó múltiples controversias en el ambiente matemático....