COLORACION DE GRAFOS

República Bolivariana de Venezuela
Ministerio del Poder Popular Para la Defensa
Universidad Nacional Experimental de las Fuerzas Armadas
U.N.E.F.A.
Núcleo Delta Amacuro

COLORACIÓN DE
GRAFOS
Facilitadora:

Bachilleres:

Luisa Rendayyo

Abreu Josè Luis
Ferman Lediannys
Marcano Arcelis
Monroy Guillyermis
TUCUPITA, MAYO DEL 2016

Índice
Introducción……………………………………………………………………………….3Grafos……………………………………………………………………………………...4
Historia sobre la Coloración de Grafo……………………………………...................4
Coloración de Grafos…………………………………………………………………….5
Grafos Coloreables……………………………………………………………………….5
Grafos Notables…………………………………………………………………………..5
Numero Cromático………………………………………………………………………..6
Coloración de Vértices…………………………………………………………………...6
Coloración de Aristas……………………………………………………………………..7
Coloración deRegiones………………………………………………………………….8
Propiedades de la Coloración de Regiones……………………………………………9
Coloración de Mapas……………………………………………………………………10
El Polinomio Cromático…………………………………………………………………10
Conclusión………………………………………………………………………………..11
Bibliografía………………………………………………………………………………..12

Introducción
La teoría de grafos, que nació como una rama de la Topología, se ha
convertido hoy en día en una herramienta matemática indispensable encampos tan
diversos como la investigación operativa, la lingüística, la química, la física, la
genética, la teoría de redes o la teoría de la decisión. Es por ello, que para casi
cualquier rama de la ciencia, se hace indispensable el conocimiento, a través de
conceptos globales, de las ideas básicas que sustentan a la denominada teoría de
grafos.
En numerosos problemas cuantificables, en lasorganizaciones, intervienen
una serie de elementos en los que se establecen unas relaciones: por ejemplo, los
problemas relacionados con posibilidades de comunicación, relaciones de orden
entre actividades o estructuras de producto complejas.
Los grafos son herramientas que permiten modelizar relaciones de esta
naturaleza, de modo que se puedan resolver problemas asociados a esas
circunstancias,frecuentemente de forma menos costosa que utilizando otras
técnicas como la programación lineal.
Una buena comprensión de la teoría de grafos pasa por dominar la
nomenclatura y conceptos asociados a estas representaciones de relaciones entre
elementos, así como sus diversas formas de representación.
Por ello en el siguiente trabajo estudiaremos una parte de la teoría de grafos
como lo es La Coloración deGrafos, la coloración de sus vértices, de sus aristas,
de regiones y de mapas.

TEORIA DE GRAFOS
 Grafos
Un grafo es una representación gráfica de diversos puntos que se conocen como
nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el
nombre de aristas. También podría decirse que es un conjunto, no vacío, de objetos
llamados vértices (o nodos) y una selección depares de vértices, llamados aristas
que pueden ser orientados o no.
Típicamente, un grafo se representa mediante una serie de puntos (los vértices)
conectados por líneas (las aristas).

 Historia sobre la coloración de grafos
Los primeros resultados sobre coloración de grafos trataban exclusivamente
sobre grafos planares en forma de coloración de mapas. Mientras intentaba colorear
un mapa deInglaterra, Francis Guthrie postuló la conjetura de los 4 colores, notando
que 4 colores son suficientes para colorear el mapa tal que regiones que comparten
un borde común no reciban el mismo color. El hermano de Guthrie pasa el problema
a su profesor de matemáticas Augustus de Morgan en la universidad, mencionado
en una carta a William Hamilton en 1852. Arthur Cayley envía el problema a la
LondonMathematical Society en 1879. Algunos años después, Alfred Kempe
publicó un paper que resolvía el problema y por una década el problema de los 4
colores se consideró resuelto. Por su contribución Kempe fue elegido Fellow de la
Royal Society y posteriormente presidente de la London Mathematical Society.
En 1890, Heawood descubrió que el argumento de Kempe...