Grafos

El problema.
Titulo descriptivo del problema.
Actualmente, la coloración de grafos es cada vez más compleja y se caracteriza por la de asignar colores a determinados vértices.

El problema que se plantea en este proyecto es la de aplicar el teorema de los cuatro colores en este caso al mapa de Venezuela y al del estado bolívar lo cual nos permitirá visualizar la conexión de estos mediante lautilización de grafos.

Formulación del problema.

Encontrar la manera de caracterizar el mapa de Venezuela y del estado bolívar mediante coloreo de grafos permitiéndonos visualizar la adyacencia de los estados y municipios, entonces podremos definirlo de la siguiente manera:
Sea G: Venezuela y F: Bolívar grafos dirigidos. Deseamos colorear los vértices de G y F de tal manera que no hayados vértices o nodos adyacentes del mismo color. Los vértices en este caso serán los estados y municipios la cual se tienen que usar los siguientes métodos:
* Los estados o municipios que se encuentran adyacentes no deben compartir un color.
* Usar la menor cantidad de colores posibles.
Objetivos de la investigación.
Objetivo general.
Conocer las características de la conexión delos vértices (estados o municipios) siempre y cuando exista adyacencia. Esto con la finalidad de comprender de una manera clara y precisa las conexiones que se presentan, en síntesis el coloreo de grafos tiene como finalidad asignarle un color a cada vértice del grafo de manera tal que los vértices adyacentes (vecinos) unidos por aristas no compartan color, y el numero cromático se representaracomo el número mínimo de colores que se requieran para su coloración.

Justificación.

Utilizar la coloración de grafos como herramienta de comunicación de los estados y municipios, determinando el menor número de colores que permite pintar un Mapa geográfico de tal manera que dos regiones con una frontera común tengan colores diferentes.

Al mapa se le puede asociar vértices que formaran ungrafo cuyos vértices son cada una de las regiones del mapa y habrá una arista entre dos vértices si las regiones correspondientes tienen una frontera común. Una coloración de los vértices es equivalente a una coloración de las regiones el problema se reduce a determinar el numero cromático del grafo asociado al mapa.

Limitaciones.

En este apartado se limitaran las funciones del coloreo delos mapas en lo que se describen:
* Cada estado es un nodo.
* Máximo usar cuatro colores.
* Estados vecinos o nodos vecinos son los que comparten fronteras.
* Por lo tanto, vecinos no deben compartir color.

Marco de referencia

Fundamentos teóricos.

* Historia
Primero empezaremos con un poco de historia en donde detallaremos el trabajo de Leonhard Euler, en 1736,sobre el problema de los puentes de Konigsberg es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y la topología. (Figura 1: Los puentes de Königsberg).

Posteriormente en 1845 Gustav Kirchhoff publico sus leyesde los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos.

En 1852 Francis Guthrie planteo el problema de los cuatro colores que plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color.

Este problema, que no fue resuelto hasta un siglo después por Kenneth Appely Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los Matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.

* Definiciones

Teoría de grafos: en matemáticas y en ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos.

Un grafo: es una pareja de conjuntos G = (V, A),...