Proyecto 5 "Algoritmo de Kruskal"

Primero hay que empezar con algunas definiciones:

Á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:
o Un grafo conexo y sin ciclos.
o 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 (en el ejemplo, el grado de v1 es 2 y de v2 1). 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.
Árbol de mínima expansión: Árbol de máximo alcance cuyo valor es mínimo, es decir, la suma de sus aristas es mínima.
______________________________________________________

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.



Algoritmo de Kruskal:

El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). El algoritmo de Kruskal es un ejemplo de algoritmo voraz.

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.

Complejidad del algoritmo

m el número de aristas del grafo y n el número de vértices, el algoritmo de Kruskal muestra una complejidad O(m log m) o, equivalentemente, O(m log n), cuando se ejecuta sobre estructuras de datos simples. Los tiempos de ejecución son equivalentes porque:

-m es a lo sumo n2 y log n2 = 2logn es O(log n).
-ignorando los vértices aislados, los cuales forman su propia componente del árbol de expansión mínimo, n ≤ 2m, así que log n es O(log m).

Aplicaciones:

La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa con diferentes oficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica le ofrece esta interconexión, pero ofrece tarifas diferentes o costes por conectar cada par de oficinas. Cómo conectar entonces las oficinas al mínimo coste total.

Otra aplicación menos obvia es que el árbol de coste total mínimo puede ser usado como solución aproximada al problema del viajante de comercio (traveling salesman problem), recuerde que encontrar la solución óptima a este problema es NP-completo. La manera formal de definir este problema es encontrar la trayectoria más corta para visitar cada punto al menos una vez. Nótese que si se visitan todos los puntos exactamente una vez, lo que se tiene es un tipo especial de árbol.
Pseudocodigo:

Entrada: Un grafo ponderado conexo con todos sus pesos diferentes.

i : = 1;

N := tamaño del grafo de Entrada en número de vértices;



mientras (i < style="font-weight: bold;">Ejemplo:





Este es el grafo original. Los números de las aristas indican su peso. Ninguna de las aristas está resaltada.








AD y CE son las aristas más cortas, con peso 5, y AD se ha elegido arbitrariamente, por tanto se resalta.









Sin embargo, ahora es CE la arista más pequeña que no forma ciclos, con peso 5, por lo que se resalta como segunda arista.








La siguiente arista, DF con peso 6, ha sido resaltada utilizando el mismo método.









La siguientes aristas más pequeñas son AB y BE, ambas con peso 7. AB se elige arbitrariamente, y se resalta. La arista BD se resalta en rojo, porque formaría un ciclo ABD si se hubiera elegido.







El proceso continúa marcando las aristas, BE con peso 7. Muchas otras aristas se marcan en rojo en este paso: BC (formaría el ciclo BCE), DE (formaría el ciclo DEBA), y FE (formaría el ciclo FEBAD).








Finalmente, el proceso termina con la arista EG de peso 9, y se ha encontrado el árbol expandido mínimo.





Como se puede apreciar, este algoritmo es de optimizacion, ya que saca un coste minimo vistando a todos los nodos. Puede usarse para el problema del viajante.

Algoritmo de Kruskal

ejemplo del algoritmo en la web
para probarlo click AQUI

Para descargar la diapositiva de la clase click AQUI

_____________________________________________________
Autoevaluacion:
Pues este tema me gusto desde el principio, puesto que en proyecto 2 habia hecho el problema del transbordo con costos, y se parece.
De este algoritmo hay mucha informacion en la web, pero creo que pude redactarla en un modo mas entendible.
Creo que si me esforce en cumplir el cometido del blog, ya seran ustedes los que juzguen...
______________________________________________________
Bibliografia:
http://es.wikipedia.org/wiki/Joseph_Kruskal
http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal
http://lear.inforg.uniovi.es/ioperativa/TutorialGrafos/minimaexp/kruskal/appletKruskal.htm
(programa del algoritmo de kruskal en la web)
'http://www.dma.fi.upm.es/gregorio/grafos/primkruskal/kruskal/kruskal.html
http://www.monkers.net/examenes/EDA/practica2.pdf
______________________________________________________
bueno espero que les haya gustado el tema, si tienen algunas preguntas o simplemente comentar algo, no duden en hacerlo.