Download algoritmos de kruskal y prim

ALGORITMOS DE KRUSKAL Y PRIM
JULIÁN RICARDO CÁRDENAS PALACIOS
FERNANDO PEREZ TORRES
ELKIN YAMITH BARRERA
INGENIERO LEONARDO BERNAL ZAMORA
UNIVERSIDAD DE BOYACÁ
FACULTAD DE CIENCIAS E INGENIERÍA
INGENIERÍA DE SISTEMAS
TUNJA
2010
TABLA DE CONTENIDO
Introducción
1. Objetivos
2. Grafos
3. Árboles De Expansión Mínimos
4. Algoritmo de Prim
4.1. Robert Prim
5. Algoritmo de Kruskal
5.1. Joseph Kruskal
6. Web grafía
INTRODUCCIÓN
Los algoritmos devoradores son algoritmos que toman decisiones, partiendo de los
datos que tienen disponibles, ignorando las consecuencias quo tales decisiones
pueda tener. Esta característica los hace sencillos de diseñar e implementar.
Poseen los siguientes elementos característicos:




Conjunto de candidatos: Son los posibles elementos que pueden ser
considerados. Algunos de ellos serán seleccionados mientras que otros
rechazados.
Función de solución: Verifica si con los elementos seleccionados ya se ha
completado la solución.
Función de factibilidad: verifica si hay posibilidad de completar la solución
apoyándose en los elementos seleccionados.
Función de selección: permite elegir el candidato más prometedor.
Generalmente existe una relación directa con la función objetivo relacionada
con la función objetivo.
Los Algoritmos Voraces, se emplean en problemas de optimización en los cuales
se pretende maximizar o minimizar algún valor. La codificación de un algoritmo
voraz se caracteriza por tener un bucle, denominado bucle voraz.
Algunos algoritmos voraces:


El algoritmo de Kruskal.
El algoritmo de Prim.
1. OBJETIVOS
1.1 GENERAL

Realizar un estudio sobre los algoritmos de Kruskal y Prim
1.2 ESPECÍFICOS



Estudiar y analizar el algoritmo de Prim
Estudiar y analizar el algoritmo de Kruskal
Explorar la ruta o camino óptimo con estos algoritmos para la solución del
problema
2. GRAFOS
Un grafo es un conjunto de puntos (vértices) en el espacio, que están conectados
por un conjunto de líneas (aristas). Otros conceptos básicos son:
2.1 Terminología de Grafos
 Una arista se representa por los vértices que conecta. La arista 3 conecta
los vértices b y d, y se representa por A(b,d).
 Algunos vértices pueden conectar un nodo consigo mismo; por ejemplo, el
vértice d tiene el formato V(d,d). Estas aristas se denominan bucles
 Al número de vértices que tiene un grafo se le llama orden del grafo
 Un grafo nulo es un grafo de orden 0
 Dos vértices son adyacentes si hay un arco que los une.
 Un camino es una secuencia de uno o más arcos que conectan 2 nodos.
 Un grafo es dirigido cuando los arcos tienen dirección.
 Un grafo es no-dirigido cuando los arcos no tienen dirección.
 La longitud de un camino es el nº de arcos que comprende.
 Un camino simple es, si todos los vértices usados son distintos excepto
el1ero y el último que se permite sean idénticos.
Tipos de Grafos
Existen dos tipos de grafos los no dirigidos y los dirigidos.
• No dirigidos: son aquellos en los cuales los lados no están orientados (No son
flechas). Cada lado se representa entre paréntesis, separando sus vértices por
comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).
• Dirigidos: son aquellos en los cuales los lados están orientados (flechas). Cada
lado se representa entre ángulos, separando sus vértices por comas y teniendo en
cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es
el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino,
se conoce como cabeza del lado.
3. ÁRBOLES DE EXPANSIÓN MÍNIMOS
Árbol de máximo alcance cuyo valor es mínimo, es decir, la suma de sus aristas
es mínima.
Árbol es un grafo en el que existe un único nodo desde el que se puede acceder a
todos los demás y cada nodo tiene un único predecesor, excepto el primero, que
no tiene ninguno.
También podemos definir un árbol como:


Un grafo conexo y sin ciclos.
Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices.
Grado de un nodo en un árbol es el número de subárboles de aquel nodo.
Denominamos hojas en un árbol a los nodos finales (v3, v5 y v6).
Un árbol de máximo alcance es aquel que obtenemos en un grafo conexo y sin
ciclos.
Un grafo ponderado o grafo con pesos es un grafo G(V, E), en el que a cada
arista se le asigna un valor real no negativo o peso. Sobre el conjunto de aristas
se introduce una función peso
. El peso de un subgrafo de un grafo
ponderado es la suma de los pesos de todas sus aristas.
Dado el grafo con pesos:
El peso total del grafo es
El peso del subgrafo H formado por los vértices a, b, c, d seria
W(H)=8+2+12+6=28.
3.1 ARBOL GENERADOR
Supongamos que a cada arista se le asocia un número positivo (su peso).
Un árbol generador se dice de peso mínimo si la suma de los pesos de las
aristas que lo componen es lo menor posible
• Para calcular el árbol de peso mínimo existen 2 algoritmos:
– Kruskal: Se van escogiendo las aristas de menor peso hasta
conseguir un árbol de peso mínimo
– Prim: Consiste en ir borrando las aristas de mayor peso posible y
que no sean aristas de separación.
Puede haber más de un árbol generador de peso mínimo, pero todos deben tener
el mismo peso.
•
4. ALGORITMO DE PRIM
4 .1 ROBERT PRIM
Nació en 1921, Sweetwater, (Estados Unidos) es un matemático e ingeniero
informático.
Robert Prim en 1957 descubrió un algoritmo para la resolución del problema
del Árbol de coste total mínimo (minimum spanning tree - MST). Este
problema es un problema típico de optimización combinatoria, que fue
considerado originalmente por Otakar Boruvka en 1926 mientras estudiaba la
necesidad de electrificación rural en el sur de Moravia en Checoslovaquia. Este
problema también fue resuelto por Joseph B. Kruskal en 1956.
En los años 60 estos científicos del Math Center (Bell Labs) fueron los pioneros de
la moderna teoría de secuenciación, particularmente en el análisis de algoritmos
de aproximación y en secuenciación multiprocesador (Ed Coffman, Ron Graham,
David Johnson y Mike Garey). En las siguientes tres décadas, se añadieron
multitud de contribuciones que mejoraron la teoría general.
El algoritmo de Prim encuentra un árbol de peso total mínimo conectando nodos o
vértices con arcos de peso mínimo del grafo sin formar ciclos.
Al igual que el algoritmo de Kruskal, el de Prim también ha sido aplicado para
hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de
redes de telecomunicaciones - TV por cable, sistemas distribuidos, interpretación
de datos climatológicos, visión artificial - análisis de imágenes - extracción de
rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de
quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros).
También se ha utilizado para encontrar soluciones aproximadas a problemas NPHard como el del 'viajante de comercio'.
El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un
vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a
los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar
son aquellas que inciden en vértices que ya pertenecen al árbol.
El árbol recubridor mínimo está completamente construido cuando no quedan más
vértices por agregar.
Objetivo de Algoritmo prim

Encontrar el árbol recubridor más corto
Requisitos

— Ser un grafo conexo

— Ser un grafo sin ciclos

— Tener todos los arcos etiquetados.
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para
encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas
aristas están etiquetadas.
En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un
árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es
el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el
árbol recubridor mínimo para uno de los componentes conexos que forman dicho
grafo no conexo.
La idea básica consiste en añadir, en cada paso, una arista de peso mínimo a un
árbol previamente construido. Más explícitamente:
Paso 1. Se elige un vértice u de G y se considera el árbol S={u}
Paso 2. Se considera la arista e de mínimo peso que une un vértice de S y un
vértice que no es de S, y se hace S=S+e
Paso 3. Si el nº de aristas de T es n-1 el algoritmo termina. En caso contrario se
vuelve
al
paso
2
5. ALGORITMO DE KRUSKAL
5.1 Joseph KRUSKAL
Joseph B. Kruskal investigador del Math Center (Bell-Labs), que en 1956
descubrió su algoritmo para la resolución del problema del Árbol de coste total
mínimo (minimum spanning tree - MST) también llamado árbol recubridor euclídeo
mínimo. Este problema es un problema típico de optimización combinatoria, que
fue considerado originalmente por Otakar Boruvka(1926) mientras estudiaba la
necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.
El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos)
formado por arcos sucesivamente seleccionados de mínimo peso a partir de un
grafo con pesos en los arcos.
El Algoritmo de Kruskal que resuelve la misma clase de problema que el de Prim,
salvo que en esta ocasión no partimos desde ningún nodo elegido al azar. Para
resolver el mismo problema lo que hacemos es pasarle a la función una lista con
las aristas ordenada de menor a mayor, e iremos tomando una para formar el
ARM. En un principio cada nodo está en un digamos grupo distinto, al elegir una
arista de la lista miraremos si no están los nodos conectados ya en el mismo
grupo, de no estarlo fusionamos ambos grupos y comprobamos si hemos
encontrado ya la solución, para devolver el resultado.
Sea G un grafo con m nodos y e aristas, donde cada arista tiene un peso W(e)
asignado.
Para todo grafo conectado G es posible asociar un árbol que contenga todos los
vértices del grafo, denominado árbol de cobertura.
Todo árbol de cobertura que a su vez tiene la sumatoria mínima de los valores de
las aristas se denomina árbol de cobertura mínima.
El algoritmo de Kruskal nos permite encontrar el árbol de cobertura mínima, para
un grafo cuyas aristas han sido ordenadas de la forma:
/*aacm = aristas árbol de cobertura mínima*/
/*ag = aristas grafo*/
/*aciclico() = función booleana que determina si aacm forma un
ciclo con ag[j]*/
For (j=1; j<=n; j++){
if(aciclico(aacm,ag[j])){
aacm[i] = ag[j];
i++;
}
}
El algoritmo de Kruskal permite hallar el árbol minimal de cualquier grafo
valorado (con capacidades). Hay que seguir los siguientes pasos:
1. Se marca la arista con menor valor. Si hay más de una, se elige
cualquiera de ellas.
2. De las aristas restantes, se marca la que tenga menor valor, si hay
más de una, se elige cualquiera de ellas.
3. Repetir el paso 2 siempre que la arista elegida no forme un ciclo con
las ya marcadas.
4. El proceso termina cuando tenemos todos los nodos del grafo en
alguna de las aristas marcadas, es decir, cuando tenemos marcados
n-1 arcos, siendo n el número de nodos del grafo.
Ejemplo
Determinar el árbol de mínima expansión para el siguiente grafo:

Siguiendo el algoritmo de Kruskal, tenemos:
o Elegimos, por ejemplo, la arista (5, 6) = 1 (menor valor) y la
marcamos.
o Elegimos la siguiente arista con menor valor (1, 3) = 1 y la
marcamos.
o
o
o
o
o
o
o
Elegimos la siguiente arista con menor valor (5, 7) = 2 y la
marcamos, ya que no forma ciclos con ninguna arista de las
marcadas anteriormente.
Elegimos la siguiente arista con menor valor (1, 2) = 3 y la
marcamos, ya que no forma ciclos con ninguna arista de las
marcadas anteriormente.
Elegimos la siguiente arista con menor valor (6, 7) = 4 y la
desechamos, ya que forma ciclos con las aristas (5, 7) y (5, 6)
marcadas anteriormente.
Elegimos la siguiente arista con menor valor (2, 5) = 5 y la
marcamos, ya que no forma ciclos con ninguna arista de las
marcadas anteriormente.
Elegimos la siguiente arista con menor valor (4, 5) = 6 y la
marcamos, ya que no forma ciclos con ninguna arista de las
marcadas anteriormente.
FIN. Finalizamos dado que los 7 nodos del grafo están en alguna de
las aristas, o también ya que tenemos marcadas 6 aristas (n-1).
Por tanto el árbol de mínima expansión resultante sería:
6. WEBGRAFÍA
http://www.mitecnologico.com/Main/TiposDeGrafos
http://personales.upv.es/arodrigu/grafos/Prim.htm
http://www.matediscreta.8k.com/grafos.htm
www.ganimides.ucm.cl/haraya/doc/GRAFOS.ppt
http://eisc.univalle.edu.co/materias/Matematicas_Discretas_2/pdf/cobertor_arbol_0
3.pdf
http://www.matap.uma.es/profesor/magalan/MatDis/material/ArbolesTema6_2_Mat
Discreta.pdf
http://www.inf.ucv.cl/~rsoto/cursos/INF245/Cap2_Parte3_2ppt_INF245.pdf
http://lear.inforg.uniovi.es/ioperativa/TutorialGrafos/minimaexp/minimaexp.htm