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=

sábado, 8 de mayo de 2010

Problema -Puntos Extra-

Máquina de Turing

Siendo la representación binaria del número 37; ejecutaremos la Máquina de Turing, siguiendo la función de transición dada.

37: 100101





Bien, iniciemos nuestra máquina...

Vemos que la máquina empieza en un estado S.


Enseguida asigna un 0 al inicio, y avanza un espacio a la derecha.



Al pasar a la siguiente posición, se encuentra un 1, y escribe un 1, y avanza un espacio a la derecha.

Al estar un 0 en las siguientes dos posiciones, en cada una de ellas escribe un cero y avanza un espacio a la derecha.


En la siguiente posición hay un 1, escribe un 1 y avanza un espacio a la derecha.


Ahora vemos un 0, escribe 0, y avanza un espacio a la derecha.


Le sigue un 1, y al igual que las demás posiciones escribe un 1, y avanza un lugar a la derecha.


En este momento se encuentra con un espacio vacío.


Entonces la máquina escribe un cero.

Y avanza un espacio, ahora hacia la izquierda, volviendose en un estado T, y al estar en un 1, escribe 1, y avanza un espacio a la izquierda.


Al encontrar el primer cero escribe un 1, imprime SI, y termina.



Entonces nos queda el siguiente número binario: 01001110

que es el número 78.