martes, 18 de mayo de 2010

Proyecto 5

Coloreo de Grafos.

Coloreo de Grafos es la coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color.

Similarmente, una arista coloración asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes.

El primer resultado acerca de la coloración de grafos trataba exclusivamente sobre grafos planos y la coloración de mapas. Mientras intentaba colorear un mapa de Inglaterra, Francis Guthrie postulo la teoría 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.



Las etiquetas como rojo o azul son solamente utilizadas cuando el número de colores es pequeño, y normalmente los colores están representados por los enteros {1, 2, 3, …}.

Una coloración que usa a lo más k colores se llama k-coloración (propia). El menor número de colores necesarios para colorear un grafo G se denota número cromático . Un grafo que puede ser asignada una k-coloración (propia) es k-coloreable y es k-cromático si su número cromático es exactamente k. Un subconjunto de vértices asignados con el mismo color se llama una clase de color. Cada clase forma un conjunto independiente. Esto es, una k-coloración es lo mismo que una partición del conjunto de vértices en k conjuntos independientes, y los términos k-partito y k-coloreable tienen el mismo significado.

El polinomio cromático cuenta el número de maneras en las cuales puede ser coloreado un grafo usando no más que un número de colores dado

Un algoritmo simple para colorear gráfico es fácil de describir, pero potencialmente muy costosa.
En términos de complejidad computacional - NP-completo Lo que eso significa que no existe algoritmo conocido para colorear gráfica óptima que no es exponencial, y que, además, si hubiera un algoritmo no-exponencial para ella, no sería una solución no-exponencial de todos problemas.

Una solución general a la búsqueda de una coloración gráfica óptimo es la búsqueda exhaustiva: empezar con un nodo, dale un color, asignar colores que no sean contradictorias con sus vecinos, y así sucesivamente. Prueba con dos colores, si no se obtiene ningún resultado, a continuación, intente con tres, y así sucesivamente.



Ejemplos de coloreo de grafos:


Grafo de Petersen con 3 colores; comúnmente dibujado como un pentágono con una estrella de cinco puntas adentro:




---------





----------


Bibliografia.


http://es.wikipedia.org/wiki/Coloraci%C3%B3n_de_grafos


http://scienceblogs.com/goodmath/2007/06/graph_coloring_algorithms_1.php

http://www.google.com.mx/images?hl=es&gbv=2&tbs=isch%3A1&sa=1&q=coloreo+de+grafos&aq=f&aqi=&aql=&oq=&gs_rfai=

7 comentarios:

dora nelly dijo...

hola

cuando estuve buscando infomacion para mi proyecto me encontre con un juego de coloracion para grafos.

Buen proyecto

te dejo el link que encontre

http://www.algovidea.cl/index.php?option=com_content&view=article&id=100&Itemid=105

dora nelly dijo...

se me olvide poner mi blog para que la profe nos peuda identificar

http://doranellygonzalez.blogspot.com/

Gerardo Ossio dijo...

Hola Rocio tu tema me parecio muy interesante y entretenido. Estuve observando tu blog y logre comprender como colorear los grafos. Lo que te iba a preguntar era si tenia alguna aplicacion en lo cotidiano?
Por otra parte me parecio muy original y entretenida tu actividad ya que el primero si me salio pero el segundo me quede atorado.
Saludos amiga !

Gerardo Ossio dijo...

Este es mi blog http://algoritmosuanl.blogspot.com/

Cualquier cosa me avisas.

klaudialozano dijo...

hola rocio me parecio muy bien tu tema es un tema que hace que tu mente trabaje pensando en que no repitamos colores o que usemos los colores minimos posibles, me gusto mucho como isite que participaramos coloreando :D muy buena informacion en el blog

dejo el link de mi blog para cualquier comentario =)
http://klaudialozanoo.blogspot.com/

Elisa dijo...

Nada más faltó el comentario de autoevaluación.

ChioSoCo dijo...

[b]Gerardo Ossio[/b]:

Para tu pregunta: ¿Existe alguna aplicación en lo cotidiano?

Bueno no encontré mucho, pero lo más relevante, es para la reducción del número de frecuencias en el diseño de una red, esto es para la telefonía celular.