Trabajo

Aplicación de la coloración de grafos a la telefonía móvil
Nils Murrugarra Llerena
Universidad Nacional de Trujillo
Escuela académico profesional de informática
2006
Resumen: En el presente paper tratare del problema de coloración de grafos
y como se puede aplicar a la telefonía celular. En la parte de la introducción
se da un ejemplo que se puede modelar mediante grafos. En la parte deDesarrollo del tema la he dividido en fundamente Teórico, Enunciado del
problema tratado y Aplicación en la telefonía móvil. En lo referente al
Fundamento Teórico he tenido en cuenta Algoritmos voraces y problemas
NP. Luego en lo referente al enunciado del problema tratado he tenido su
definición, su modelado mediante un algoritmo voraz y su algoritmo voraz.
Y con lo referente a la Aplicaciónen la telefonía móvil ahí se trata como el
problema de coloración de grafos es aplicable a esa área. Y para finalizar
presento mis conclusiones y referencias.
1. Introducción
Quien no ha escucha del algoritmo de dijkstra para encontrar la ruta más corta desde
un origen a un destino, bueno para comentarles una de las formas de modelarlo es
mediante un algoritmo voraz, que conforme se recorrael grafo se vaya seleccionando
la arista de menor longitud. Como este problema hay otros que también demuestran
ser aplicables en nuestra realidad, muchos de los cuales son extraídos de la
informática teórica. En el presente paper tratare el problema de coloración de grafos
y hablaré de la aplicación que tiene a la telefonía móvil.
2. Desarrollo del tema
2.1.Fundamento teórico
a. AlgoritmosVoraces(greedy)
a.1. Definición
El enfoque que aplican es “miope”, y toman decisiones con la
información que tienen disponibles de modo inmediato, sin tener en
cuenta los efectos que pueden tener en el futuro.
Estos algoritmos se denominan voraces, ya que seleccionan el mejor
bocado que pueden tomar sin preocuparse del futuro, nunca cambian de
opinión, una vez que un candidato haya sidoseleccionado, queda allí
siempre.
a.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.

1

d. Funciónes 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).
a.3. Proceso
Los algoritmos voraces avanzanpaso 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.
b. Problemas NP
b.1.Introducción
En la vida real existen muchos problemasprácticos para los cuáles no se
conoce, ningún algoritmo eficiente, pero cuya dificultad intrínseca no ha
conseguido demostrar nadie.
Entre estos se encuentran problemas tan conocidos como el agente
viajero, el coloreado óptimo de un grafo, los ciclos hamiltonianos, la
programación entero, la búsqueda del camino simple más largo de un
grafo, etc.
b.2.Definición
Antes de definir que es una clase detipo NP, definiremos que es una
clase del tipo P, en está están todos los algoritmos eficientes y que su
tiempo de ejecución es un tiempo polinómico.
Por otro lado los problemas de la clase NP, en primer lugar NP no
significa “no polinómico”, mas bien lo que quiere decir es de “tiempo
polinómico no determinista”. Además los problemas NP se basan en
problemas de decisión, para los cuales...