Teoria De Grafos

GRAFOS COLOREABLES














Prof. Integrantes:
Cátedra: Teoría de Grafos Jorge Rodriguez
Oscar Freitez
Robby OliverosToyo Eliezer
Sección: 5T1IS





Barquisimeto, 30 de Mayo del 2012
INTRODUCCION

Un grafo es “un conjunto de puntos en el espacio, que están conectados por un conjunto de líneas”. Partiendo de esta definición podemos decir un grafo nos permite estudiarlas interrelaciones entre unidades que interactúan unas con otras. Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales. Dentro de las técnicas que se utilizan a través de un grafo, encontramos la coloración de grafos, la cual consiste asignar colores a cada elemento de un grafo, de formade que cada uno reciba un color distinto, esta idea surge de la coloración de los países de un mapa, y hoy en día se aplica esta técnica a representaciones matemáticas y computacionales. Dentro de este tema de la coloración de grafos, se explicara la coloración de vértices, coloración de aristas, el número cromático, los grafos coloreables y otros, comenzando con una breve introducción a este temapresentando algunas definiciones básicas que ayudaran a la mejor compresión del mismo.






































DEFINICIONES BÁSICAS

Grafo
Un grafo es un conjunto de objetos llamados vértices o nodos, unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Para caracterizarun grafo G son suficientes únicamente el conjunto de todas sus aristas, comúnmente denotado con la letra E (del término en inglés edge), junto con el conjunto de sus vértices, denotado por V. Así, dicho grafo se puede representar como G(V,E), o bien G = (V,E).


Vértices o Nodos
Es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto devértices y un conjunto de aristas (pares no ordenados de vértices), mientras que un grafo dirigido está compuesto por un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices).

Aristas
Gráficamente las aristas se representan, para el caso de los grafos no dirigidos, como una línea que une a los dos vértices. Si el grafo es dirigido, entonces la arista se representa como unaflecha, que parte del nodo origen y apunta al nodo destino.


Tipos de Grafos

Grafo Dirigido
El orden en que están direccionadas las aristas o arcos es relevante. Cuando se escribe (a, b) se indica que la arista va desde el vértice (a) al vértice (b).


Grafo no Dirigido
El orden en que están direccionados las aristas o arcos no es relevante. Cuando se escribe (a, b) se indica que laarista va desde el vértice (a) al vértice (b) o viceversa.


Grado de un Vértice
El grado de un vértice en un grafo es el número de aristas adyacentes al vértice, Por ejemplo, en la figura se muestra el grado correspondiente a cada vértice o nodo del grafo.







Coloración de Grafos

Una coloración de un grafo simple consiste en asignarle un color a cada vértice del grafo de manera quea cada dos vértices adyacentes se les asignan colores distintos.
Una coloración de un grafo G=(V,A) es una asignación de colores a los vértices de G, a cada vértice un color, de forma que vértices adyacentes reciban colores distintos. Si en la coloración se usan k colores diremos que es una k-coloración.
La coloración de grafos es un caso especial de etiquetado de grafos; es una asignación...