Coloracion de grafos

[pic 4][pic 5][pic 6]

[pic 7]

PRESENTACIÓN

Universidad Veracruzana

FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

PROGRAMA EDUCATIVO:
LICENCIATURA EN SISTEMAS COMPUTACIONALES ADMINISTRATIVOS

EXPERIENCIA EDUCATIVA: 
MATEMÁTICAS DISCRETAS

TÍTULO: 
COLORACIÓN DE GRAFOS

SECCIÓN: 
303

INTEGRANTES Y PRESENTADORES:

GIL SEGUNDO JOAQUIN
RAMOS MATEOS KELLY ELIDETH
RODRIGUEZ DELFÍN MARCO ANTONIO
ZARATE HERNANDEZ XIMENA MONTSERRAT

XALAPA, VER; A 15 DE NOVIEMBRE DE 2016

INTRODUCCIÓN

En este trabajo hablaremos resumidamente la teoría de grafos, más específicamente coloración de grafos, se pretende que el lector identifique y adquiera habilidades para poder colorear un grafo, aprenda un poco de su historia y algunas tengan en cuenta definiciones y conceptos sobre este mismo.

En sus inicios la teoría de grafos se utilizaba principalmente como un pasatiempo y no era si quiera considerado en el ámbito matemático, no fue hasta el año 1852 que Francis Guthrie al intentar colorear un mapa de Inglaterra se dio cuenta que solo necesitaba de 4 colores para colorear este o cualquier otro mapa, cuando se dio cuenta de ello lo paso a su profesor de matemáticas quien a su vez lo mando a la London Mathematical Society en el año de 1879.

Tiempo después en el año de  1890, el matemático Headwood creyo haber encontrado un error y propuso un teorema de 5 colores, usando ideas de Kempe dijo que el número máximo de colores utilizables para poder colorear un grafo era 5 en lugar de los 4 propuestos anteriormente. Un siglo después, y luego de diversas teorías se volvió a reducir el número de colores a 4, hasta que finalmente el teorema de los 4 colores fue probado en el año de 1976 por Kenneth Appel y Wolfgang Haken.

MARCO CONTEXTUAL

Historia

Los primeros resultados sobre coloración de grafos trataban exclusivamente sobre grafos planos en forma de coloración de mapas. Mientras intentaba colorear un mapa de Inglaterra, 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.

[pic 9]
Francis Guthrie

 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 London Mathematical 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.

[pic 10]
Alfred Kempe

En 1890, Heawood descubrió que el argumento de Kempe contenía un error, en ese paper él probó el teorema de los 5 colores, diciendo que cada mapa plano puede ser coloreado con, a lo más 5 colores, usando ideas de Kempe. En el siguiente siglo, nuevas teorías fueron desarrolladas para reducir el número de colores a cuatro, hasta que el teorema de los 4 colores fue finalmente probado en 1976 por Kenneth Appel y Wolfgang Haken.

Coloración de grafos

Un coloreado de G es una asignación de colores a los nodos de G de tal manera que dos nodos cualesquiera que estén conectados por una arista sean siempre de diferentes colores. Si no utiliza más de k colores diferentes, entonces es un coloreado k. El menor k tal que existe un coloreado k del grafo se llama número cromático del grafo, y cualquier coloreado k de estos será un coloreado óptimo.

Un ejemplo de la coloración de grafos podría ser el siguiente:[pic 11]

Podemos observar que el nodo 1 es adyacente al nodo 2 entonces podríamos asignarle a 1 el color rojo y al 2 un color azul, ahora, recordemos que nuestro coloreado debe ser optimo, entonces debemos ocupar el menor número posible de colores, una vez recordado esto continuemos con el coloreado, el nodo 2 es adyacente con el 3 y el 4, por lo tanto el color de estos dos debe ser distinto al nodo 2, así que podríamos asignarle el color rojo a ambos, compartiendo el color que tiene el nodo 1, ahora por ultimo podemos observar que el nodo 5 es adyacente al nodo 3 y 4, por lo tanto podemos asignarle el color azul, como el nodo 2, quedando finalmente así:

[pic 12]

Por lo tanto, su número cromático es de 2-coloreado (rojo y azul).

Algoritmo Heurístico

La heurística voraz consiste en seleccionar un nodo inicial de manera aleatoria y asignarle un color (esto quiere decir que no existe un orden de coloración de nodos), y considerar después cada nodo por turnos.

Pongamos un ejemplo: [pic 13]

[pic 14]

Comencemos con el nodo 6 y asignémosle un color verde, ahora observemos que los nodos con los que tiene adyacencia no guardan relación entre ellos, entonces asignémosle un color amarillo, ahora, si nos vamos con el nodo 3 podemos observar que tiene adyacencia con el nodo 2, 6 y 8, sin embargo estos nodos no tienen relación alguna, por lo tanto se les asignaría el color del nodo 6, o sea verde, ahora solo nos queda el nodo 5, este tiene adyacencia con el 2, 4 y 6 por lo tanto no puede ser de color verde y no tiene relación con el 1, 3 y 7 por lo tanto podremos asignarles un color amarillo, finalmente nos queda el nodo 4, pero este tiene relación con el nodo 1, 5 y 7, así que podemos asignarle el color verde, esto quedaría así:

...