algoritmo de kruskal
DESCRIPTION
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.TRANSCRIPT
ALGORITMO DE KRUSKALEl algoritmo de Kruskal es un algoritmo de la teora de grafos para encontrar un rbol de expansin mnimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un rbol, incluyen todos los vrtices y no hay ciclos y donde el valor total de todas las aristas del rbol es el mnimo, a esto se le llama rbol de expansin mnimo. El algoritmo de Kruskal es un ejemplo de algoritmo voraz. Esta definicin en trminos simples es como encontrar el rbol de expansin pero que el peso total de las aristas sea el menor posible.El objetivo del algoritmo de Kruskal es construir un rbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mnimo peso a partir de un grafo con pesos en los arcos.El algoritmo de Kruskal permite hallar el rbol mnimo de cualquier grafo valorado (con capacidades). Para desarrollar este algoritmo se debe seguir los siguientes pasos: Se marca la arista con menor valor. Si hay ms de una, se elige cualquiera de ellas. De las aristas restantes, se marca la que tenga menor valor, si hay ms de una, se elige cualquiera de ellas. Repetir el paso 2 siempre que la arista elegida no forme un ciclo con las ya marcadas.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 nmero de nodos del grafo.
Figura 1. Diseo del Algoritmos de Kruskal.Ejemplo 01:Apliquemos el algoritmo de Kruskal sobre el grafo del ejemplo anterior. Usamos m para indicar las aristas elegidas y k para el nmero de componentes conexas que hay en cada paso (cada componente conexa de distinto color):
Determinar el rbol de mnima expansin para el siguiente grafo.Siguiendo el algoritmo de Kruskal, tenemos:
Figura 2. Grafo de EjemploSolucin:Elegimos, por ejemplo, la arista (5, 6) = 1 (menor valor) y la marcamos.
Elegimos la siguiente arista con menor valor (1, 3) = 1 y la marcamos.
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 estn en alguna de las aristas, o tambin ya que tenemos marcadas 6 aristas (n-1). Por tanto el rbol de mnima expansin resultante sera:
Figura 4. Grafo resultante usando el Algoritmo de Kruskal
Ejemplo 02:A)Este es el grafo original, losnmerosde las aristas indican su peso ninguna de las aristas esta enlazada.
B)AD-CE son las aristas ms cortas, con peso de 5 y AD se ha elegido arbitrariamente, por tanto se resalta.
C)Sin embargo ahora es CE la arista ms pequea que no forma ciclos, con peso de 5, por lo que se resalta como segunda arista.
D)La siguiente arista, DF con peso de 6, ha sido resaltada bajo el mismo mtodo.
E)Las siguientes aristas ms pequeas son AB-BE ambas con peso de 7, AB seeligearbitrariamente y se resalta. La arista BD se resalta en rojo,porqueformara un ciclo ABD si se hubiera elegido.
F)El proceso continua marcando las aristas, BE con peso 7. Muchas otras aristas se marcan en rojo en este paso: BC pues formara el ciclo BCE, DE formara el ciclo DEBA y FE formara el ciclo FEBAD.
E)Finalmente, el proceso termina con la arista EG de peso 9, y se ha encontrado elrboldeexpansinmnimo.
CONLUSIONES: Mediante el algoritmo de Kruskal, encontrar el rbol de expansin mnimo. La formulacin del rbol de expansin mnimo tambin ha sido aplicada para hallar soluciones en diversas reas (diseo de redes de transporte, diseo de redes de telecomunicaciones - TV por cable, sistemas distribuidos, interpretacin de datos climatolgicos, anlisis de clusters y bsqueda de superestructuras de quasar, plegamiento de protenas, reconocimiento de clulas cancerosas, y otros).
REFERENCIAS:http://abdarrayan.blogspot.com/2009/04/oracle-10-vs-sql-server-2008_14.htmlhttp://www.mitecnologico.com/Main/TiposDeGrafoshttp://personales.upv.es/arodrigu/grafos/Prim.htmhttp://www.matediscreta.8k.com/grafos.htmwww.ganimides.ucm.cl/haraya/doc/GRAFOS.ppthttp://eisc.univalle.edu.co/materias/Matematicas_Discretas_2/pdf/cobertor_arbol_03.pdfhttp://www.matap.uma.es/profesor/magalan/MatDis/material/ArbolesTema6_2_MatDiscreta.pdfhttp://www.inf.ucv.cl/~rsoto/cursos/INF245/Cap2_Parte3_2ppt_INF245.pdfhttp://www.ma.uva.es/~antonio/Industriales/Clase_07-08/LabM/Alg_Kruskal_C.pdfhttp://www.dma.fi.upm.es/gregorio/grafos/PrimKruskal/kruskal/kruskal.htmlhttp://algoritmodekruskal.blogspot.com/1
2
3
4
5
7
6
3
8
1
7
9
2
6
1
4
5
1
2
3
4
5
7
6
3
8
1
7
9
2
6
1
4
5
1
2
3
4
5
7
6
3
8
1
7
9
2
6
1
4
5
1
2
3
4
5
7
6
3
8
1
7
9
2
6
1
4
5
1
2
3
4
5
7
6
3
8
1
7
9
2
6
1
4
5
1
2
3
4
5
7
6
3
1
2
6
1
5
1
2
3
4
5
7
6
3
8
1
7
9
2
6
1
4
5
1
2
3
4
5
7
6
3
8
1
7
9
2
6
1
4
5