Coloracion de grafos

...

[pic 15]

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

Polinomio cromático

Se le conoce a las n maneras en las que se puede colorear un grafo, pues no existe una sola manera, esto va muy de la mano con la cantidad de colores con los que se cuenta, pues puedes combinar y cambiar colores tras colores, un ejemplo podría ser con el siguiente grafo.

[pic 16]

[pic 17]

Ejercicio en clase:

[pic 18][pic 19][pic 20][pic 21][pic 22]

[pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30]

---------------------------------------------------------------

[pic 31][pic 32][pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39][pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47][pic 48][pic 49][pic 50][pic 51][pic 52][pic 53][pic 54][pic 55][pic 56][pic 57][pic 58][pic 59][pic 60][pic 61][pic 62][pic 63][pic 64][pic 65][pic 66][pic 67][pic 68][pic 69][pic 70][pic 71][pic 72][pic 73][pic 74][pic 75][pic 76][pic 77][pic 78][pic 79]

MARCO CONCEPTUAL

¿Qué es?

Es un sistema de etiquetas, estas etiquetas son asignadas por colores de manera simple con el fin de que ninguna de los vértices adyacentes comparta el mismo color.

[pic 80] ¿Cómo es?

El tema de usar una coloración surge en Inglaterra, en 1852, cuando por primera vez se habló de una teoría que utiliza colores.

Se podía utilizar colores para marcar los pueblos de forma que ningún pueblo adyacente compartiera el mismo color.

Desde entonces nace la conjetura de los 4 colores, utilizando esta teoría se pueden colorear el grafo de tal forma que se llegue a etiquetar cada vértice, arista e incluso cada cara o región.

¿Para qué sirve?

La teoría es utilizada en varias ramas, un ejemplo puede ser en las representaciones matemáticas y computaciones, donde se utilizan enteros no negativos como colores. Actualmente la coloración de grafos solo se utiliza como sistema de etiquetas en donde se debe usar el mínimo de colores posibles para su representación.

---------------------------------------------------------------

CONCLUSIÓN

Para concluir la coloración de grafos es importante en la actualidad en la que puede ser aplicada en el estudio de las redes sociales, cuya importancia radica en el adecuado almacenamiento de datos, puesto que el costo del tiempo de búsqueda de la información de cada miembro que pertenece a esta red puede tornarse demasiado alto debido al número de usuarios.

Entre estos, la teoría de grafos es un marco matemático que permite describir una red en forma de una gráfica, que consiste en una colección de los nodos y los bordes. Esta teoría aporta mucho a la resolución de problemas.

BIBLIOGRAFÍA

Brassard, G., & Bratley, P. (1997). Fundamentos de algoritmia (1ª ed., Vol. 1). Madrid, España: Prentice Hall.

Johnsonbaugh, R. (1999). Matemáticas discretas (1ª ed., Vol. 1). Ciudad de México, México: Grupo Editorial Iberoamérica.

Coloración de grafos. (2015, 9 de febrero). Consultado el 15 de Noviembre de 2016, de https://es.wikipedia.org/wiki/Coloración_de_grafos

Murga Diaz, M. R. (2012). Repositorio Unican. Obtenido de https://repositorio.unican.es/xmlui/bitstream/handle/10902/3099/Maria%20Rosa%20Murga%20Diaz.pdf?sequence=4