Coloracion De Grafos
Páginas: 11 (2623 palabras)
Publicado: 20 de junio de 2012
República Bolivariana De Venezuela
Ministerio Del Poder Popular Para La Defensa.
Universidad Nacional Experimental De La FANB.
Núcleo Falcón – Sede Coro
IS5D-A
Teoría de los Grafos:
“Coloración de Grafos”
Teoría de los Grafos:
“Coloración de Grafos”
Integrantes:
Santa Ana De Coro; mayo De 2012
Índice
Introducción………………………………………………….………………….…. | 03 |Grafos………………………………………………………….…………………….. | 04 |
Coloración de Grafos……………………………………….…………………….. | 04 |
Propiedades……………………………………………….………………………… | 04 |
Grafos Coloreables……………………………………………………………….. | 05 |
Grafos Notables…………………………………………………………………….. | 06 |
Número Cromático……………………………………………………………….. | 06 |
Coloración de Vértices…………………………………………………………… | 07 |
Coloración de Regiones…………………………………………………………. | 08 |Propiedades…………………………………………………………………………. | 08 |
Polinomio Cromático……………………………………………………………… | 09 |
Anexos………………………………………………………………………………. | 10 |
Conclusiones………………………………………………………………………. | 12 |
Bibliografía………………………………………………………………………….. | 15 |
Introducción
Un grafo es una representación gráfica de algún tema, clase o problema con el cual se procede a realizar diferentes tareas con diferentes fines. En la presente investigación seprocede a complementar dichas tareas utilizando y profundizando las diferentes propiedades que poseen los grafos, en este caso, la coloración.
La coloración de un grafo no es algo más que la asignación de etiquetas (llamadas colores) a elementos del grafo y con el cual se visualiza mejor el manejo de este. Más adelante conseguirá mayor información de manera más completa de la cual se espera le seentendible y útil.
1.- Grafos:
Un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas. También podría decirse que es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas que pueden ser orientados o no.Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas)
2.- 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 aristasadyacentes 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.
3.- Propiedades:
* Cotas del númerocromá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értices requiere 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 declique:
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. .
* Cotas del índice cromático
La arista coloración es un vértice coloración de sugrafo 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
4.- Grafos Coloreables:
Las coloraciones siempre existen,...
Ministerio Del Poder Popular Para La Defensa.
Universidad Nacional Experimental De La FANB.
Núcleo Falcón – Sede Coro
IS5D-A
Teoría de los Grafos:
“Coloración de Grafos”
Teoría de los Grafos:
“Coloración de Grafos”
Integrantes:
Santa Ana De Coro; mayo De 2012
Índice
Introducción………………………………………………….………………….…. | 03 |Grafos………………………………………………………….…………………….. | 04 |
Coloración de Grafos……………………………………….…………………….. | 04 |
Propiedades……………………………………………….………………………… | 04 |
Grafos Coloreables……………………………………………………………….. | 05 |
Grafos Notables…………………………………………………………………….. | 06 |
Número Cromático……………………………………………………………….. | 06 |
Coloración de Vértices…………………………………………………………… | 07 |
Coloración de Regiones…………………………………………………………. | 08 |Propiedades…………………………………………………………………………. | 08 |
Polinomio Cromático……………………………………………………………… | 09 |
Anexos………………………………………………………………………………. | 10 |
Conclusiones………………………………………………………………………. | 12 |
Bibliografía………………………………………………………………………….. | 15 |
Introducción
Un grafo es una representación gráfica de algún tema, clase o problema con el cual se procede a realizar diferentes tareas con diferentes fines. En la presente investigación seprocede a complementar dichas tareas utilizando y profundizando las diferentes propiedades que poseen los grafos, en este caso, la coloración.
La coloración de un grafo no es algo más que la asignación de etiquetas (llamadas colores) a elementos del grafo y con el cual se visualiza mejor el manejo de este. Más adelante conseguirá mayor información de manera más completa de la cual se espera le seentendible y útil.
1.- Grafos:
Un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas. También podría decirse que es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas que pueden ser orientados o no.Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas)
2.- 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 aristasadyacentes 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.
3.- Propiedades:
* Cotas del númerocromá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értices requiere 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 declique:
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. .
* Cotas del índice cromático
La arista coloración es un vértice coloración de sugrafo 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
4.- Grafos Coloreables:
Las coloraciones siempre existen,...
Leer documento completo
Regístrate para leer el documento completo.