Teoria De Grafos

Coloración de grafos:

Es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, los vértices de un grafo no deben compartir el mismo color con ningún vértice adyacente. 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 vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformados a una versión con vértices.

Propiedades de la coloración de grafos:

1. Cotas del número cromático:

Asignando distintos colores a distintos vértices siempre obtendremos una coloración propia, entonces. El único grafo que es 1-coloreable es el grafo sin aristas, y el grafo completo de n vérticesrequiere colores.

Si G contiene un clique de orden k, entonces a lo menos son necesarios k colores para colorear el clique; en otras palabras, el número cromático es a los menos el número de clique:

Los grafos 2-coloreables son exactamente grafos bipartitos, incluidos árboles y bosques. Por el teorema de los cuatro colores, todo grafo plano es 4-coloreable. Una coloración a través de un algoritmo voraz muestra que cada grafo puede ser coloreado con un color más que el grado del vértice máximo. .

2. Cotas del índice cromático

La arista coloración es un vértice coloración de su grafo lineal, y viceversa. Esto es,.

Existe una fuerte relación entre la arista coloración y el grado máximo del grafo. Como todas las aristas incidentes a algún vértice necesitan colores distintos, tenemos .Más aún, el Teorema de König dicta que: Si es bipartito entonces

Numero cromático:

El número cromático es la menor cantidad de colores necesarios para colorear los vértices sin que dos o más vértices unidos por una arista tengan el mismo color.

Es fácil ver que si coloreamos todos los vértices de colores distintos, entonces se puede satisfacer que la gráfica tiene una coloración propia, es decir, sin que dos vértices unidos por una arista tengan el mismo color (ver anexos). Pero evidentemente, esto generalmente no nos da el número cromático, pues puede ser posible colorear las gráficas con muchos menos colores, como en el ejemplo que se encuentra en los anexos.

Coloración de regiones y propiedades:

Una coloración de un grafo G es equivalente a una lista con ciertas restricciones. Supongamos que V(G)={v1, v2,...,vn}, entonces una coloración usando los k colores C={a1, a2, . . . , ak} es una lista (nupla) con repetición (ai1,ai2 , . . . ,ain) tal que si vs y vt son adyacentes entonces ais҂ait.

Dada una coloración χV(G) → C definimos la relación entre los vértices de G de la siguiente manera: uRv si χ(u)=χ(v), es decir, dos vértices están relacionados si tienen el mismo color. Esta es una relación de equivalencia.

Propiedades de la coloración de Regiones:

Las propiedades de la coloración de regiones se basan en el teorema de los cuatro colores que dice que dado cualquier mapa geográfico con regiones continuas, éste puede ser coloreado con cuatro colores diferentes, de forma que no queden regiones adyacentes (es decir, regiones que compartan no sólo un punto, sino todo un segmento de borde en común) con el mismo color.

Para el funcionamiento del algoritmo de coloración de un grafo es necesario indicar el grado de cada vértice o nodo, es decir conocer el número de nodos adyacentes. El teorema de cuatro colores, dispone de cuatro colores enumerado. Ejemplo: 1 amarillo, 2 rojo, 3 azul, 4 verde (teniendo en cuenta el orden de elección).

Se debe comenzar con el nodo con mayor grado, y se podría pintar con el color 1, para luego pasar al segundo nodo con mayor grado y se pinta con el color 2 y asi sucesivamente. En el caso de existir varios nodos

...