Colorario de grafos

El Problema de Coloración de Grafos
PROGRACION DE COMPUTADORAS I

En el presente trataremos sobre el problema del coloreado de grafos y sus diversas aplicaciones en el entorno laboral, en la parte del desarrollo del tema lo hemos dividido en fundamente Teórico, Enunciado del problema tratado y Aplicación .En lo referente al Fundamento Teórico tomamos en cuenta Algoritmos voraces y problemasNP. Luego en lo referente al enunciado del problema veremos su definición, su modelado mediante un algoritmo voraz y con lo referente a la Aplicación en diferentes medios ahí se trata como el problema de coloración de grafos es aplicable a diversas áreas. Y para finalizar presentamos nuestras conclusiones y referencias.

2010

Universidad Nacional Mayor de San Marcos
02/08/2010

ELPROBLEMA DE COLORACION DE GRAFOS
PROGRAMADO EN NETBEANS
Contenido
1. INTRODUCCION 2
2. FUNDAMENTO TEORICO 2
2.1. Algoritmo voraz 2
2.1.1. Definición 2
2.1.2. Características 2
2.1.3. Proceso 4
Ejemplo 1 5
Ejemplo 2 6
1.2. Problemas NP 7
1.2.1 Definición 7
1.3. Numero cromático 8
1.3.1. Definición 8
3. EXPLICACION DEL PROBLEMA 9
3.1. Enunciado del problema tratado9
3.1.1. Enunciado del Problema 9
3.1.2. Modelado del problema de coloración mediante un algoritmo voraz 9
3.1.3. Algoritmo 9
4. DEMOSTRACION DEL ALGORITMO 10
5. APLICACIONES 11
4.1. Asignación de Vuelos 11
4.2 Agrupando Peces 11
4.3 Asignación de Frecuencias 11
6. CONCLUCION 12
7. BIBLIOGRAFIA 13

*

1. INTRODUCCION
Vamos a poner algo de color en el mundode los grafos, en el problema de coloración nos enfocamos tanto desde la parte demostrativa, algorítmica y aplicativa.
El lenguaje de los grafos y de los colores que presentaremos se mostrará bien útil y práctico,
Pues permite, por ejemplo, diseñar horarios eficientes o contar listas con restricciones, aplicada a asignación de frecuencias, evitar cruce de horarios, etc.
El documento estáorganizado de la siguiente manera: Explicaci´on del problema, Demostracion NP, algoritmo-Voraz, aplicaciones, conclusiones, bibliograf´ıa.

2. FUNDAMENTO TEORICO
3.1. Algoritmo voraz
3.2.1. Definición
Estos algoritmos se denominan voraces, ya que seleccionan la mejor alternativa que pueden tomar sin preocuparse del futuro, nunca cambian de opinión, una vez que un candidato hayasido seleccionado, queda allí siempre.

3.2.2. Características
a. Lista de Candidatos: Es el conjunto o lista de elementos que disponemos.

b. 2 conjuntos: Se definen 2 conjuntos: uno de los seleccionados y considerados y otro el de seleccionados pero rechazados.

c. Función es solución: Esta función es la encargada si ya se llego o no a una solución con el conjunto de candidatos.d. Función es Factible: Esta función es la encargada de determinar si es posible o no encontrar una solución a nuestro problema al añadir algún candidato.

e. seleccionar Candidato: Elige el candidato más adecuado para poder llegar a la solución.

f. Función Objetivo: Función que expresa el valor de la solución que se desea optimizar (minimizar o maximizar).

3.2.3. Proceso
Losalgoritmos voraces avanzan paso a paso, y en cada uno de sus pasos se considera añadir el mejor candidato a la posible solución. Si el conjunto de de candidatos seleccionados ya no fuera factible, rechazamos al candidato seleccionado, por el contrario si el conjunto aumentado sigue siendo factible, entonces añadimos al candidato actual.

Coloración mediante el algoritmo austero
Damos unprocedimiento para colorear los vertices de un grafo siguiendo un orden impuesto a los vertices, usando la menor cantidad de colores posibles. Supongamos que
C = {c1, c2, . . . } es el conjunto de colores; procedemos a describir el algoritmo que denominamos algoritmo austero y consta de los siguientes pasos:

* Paso inicial. Ordenamos los vertices del grafo. Es importante notar que la...