x
1

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 de la suma 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). Este algoritmo toma su nombre de Joseph Kruskal, quien lo publicó por primera vez en 1956.[1][2]​ . Otros algoritmos que sirven para hallar el árbol de expansión mínima o árbol recubridor mínimo son el algoritmo de Prim, el algoritmo del borrador inverso y el algoritmo de Boruvka.

El algoritmo de Kruskal es un ejemplo de algoritmo voraz que funciona de la siguiente manera:

Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.

En un árbol de expansión mínimo se cumple:

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:

Se puede conseguir esta complejidad de la siguiente manera: primero se ordenan las aristas por su peso usando una ordenación por comparación (comparison sort) con una complejidad del orden de O(m log m); esto permite que el paso "eliminar una arista de peso mínimo de C" se ejecute en tiempo constante. Lo siguiente es usar una estructura de datos para conjuntos disjuntos (disjoint-set data structure) para controlar qué vértices están en qué componentes. Es necesario hacer orden de O(m) operaciones ya que por cada arista hay dos operaciones de búsqueda y posiblemente una unión de conjuntos. Incluso una estructura de datos sobre conjuntos disjuntos simple con uniones por rangos puede ejecutar las operaciones mencionadas en O(m log n). Por tanto, la complejidad total es del orden de O(m log m) = O(m log n).

Con la condición de que las aristas estén ordenadas o puedan ser ordenadas en un tiempo lineal (por ejemplo, mediante el ordenamiento por cuentas o con el ordenamiento Radix), el algoritmo puede usar estructuras de datos de conjuntos disjuntos más complejas para ejecutarse en tiempos del orden de O(m α(n)), donde α es la inversa (tiene un crecimiento extremadamente lento) de la función de Ackermann.

Sea T=[X,A] la gráfica generada por el algoritmo de Kruskal. Por construcción T es acíclica y tiene n-1 aristas; por lo tanto, T es un árbol expandido de G. Ahora se demostrará que T es de costo mínimo.

Sea S=[X,A'] un árbol de costo mínimo de G y supóngase T es distinto de S. Basta probar que S y T tienen el mismo costo para que el algoritmo quede justificado. Para ello se procederá de la siguiente manera:

A partir de los árboles T y S se construirá otro árbol, S1=[X,A´´], de costo mínimo de G con la característica que es más "parecido" a T que S; esto es, si T y S tienen k aristas en común, T y S1 tendrán k+1 aristas en común. Luego si T diferente de S1, a partir de estos dos árboles se construirá otro árbol de costo mínimo, S2, que tendrá k+2 aristas en común con T. Como la cantidad de aristas es finita, el procedimiento propuesto es finito, llegará un momento en que se construirá un árbol Sk de costo mínimo de G que tendrá n-1 aristas en común con T; es decir, se tendrá Sk = T y se podrá concluir que T es un árbol de costo mínimo de G.

Para la construcción del árbol Sr (r=1,2,3, ... ,k), considérese lo siguiente: si T diferente de Sr-1 (So = S) difieren, al menos, en una arista. Sea u1 la arista de menor costo que está en T pero no en Sr-1; es decir C(u1) = min{C(a)}, para toda arista a que pertenece a T tal que a no pertenece a Sr-1. Obsérvese que u1 es la primera arista examinada, durante el algoritmo de Kruskal, que pertenece a T pero no a Sr-1. Por otro lado, como Sr-1 es árbol, existe en él una cadena que une los extremos de u1. Esta cadena contiene una arista u2, que no pertenece a T, puesto que si estuviera toda la cadena se formaría un ciclo con u1 en T. Agréguese u1 a Sr-1 y elíminese u2 de Sr-1. Sea Sr la gráfica resultante y nótese que Sr es un árbol de G.

Ahora solo falta probar que Sr es de costo mínimo. Esto se hará por inducción. Para k=O, se tiene que So = S es un árbol de costo mínimo de G. Supóngase válida la afirmación para k=r-1; esto es, supóngase que Sr-1 es un árbol de costo mínimo de G. Esto implica que: C(Sr-1) <= C(Sr). Y como Sr-1 y Sr difieren sólo en una arista se tiene: C(u2) <= C(u1) ... (I). Basta probar que C(u1) <= (Cu2) para poder conluir que C(Sr-1)=C(Sr). Para esto, supóngase que C(u1) > C(u2) ; nótese que esta suposición implica que la arista u2 fue examinada antes que la arista u1 durante el algoritmo de Kruskal que generó T. Por otro lado, como u2 no fue incluida en T, esta arista forma ciclo con las aristas examinadas antes que ella y que fueron incluidas en T. Sean éstas b1,b2 , ..., bj. Debe observarse que C(bi) <= C(u2) < C(u1) , para i=1,...j; luego, dada la definición de u1, se concluye que b1,b2, ... ,bj pertenecen a Sr-1. Esto es una contradicción, puesto que b1, b2 ,...,bi y u2 formarían ciclo en Sr-1 . Por lo tanto se concluye : C(u1) <= C(u2) ... (II). Y utilizando la expresión (I) y (II) se tiene que: C(u1)=C(u2); por lo tanto, C(Sr-1)=C(Sr), es decir, Sr es un árbol de costo mínimo de G. Nótese que T y Sr contienen ambos a la arista u1 (que no estaba contenida en Sr-1); luego, si T y Sr-1 tienen k aristas en común, T y Sr tienen k+1 aristas en común. Si T = Sr entonces T es de costo mínimo; en caso contrario, constrúyase Sr+1 , del mismo modo que como se construyó Sr a partir de T y Sr . Este procedimiento es finito puesto que el número de aristas de T es finito.

Otros algoritmos para este problema son el algoritmo de Prim y el algoritmo de Boruvka.



Escribe un comentario o lo que quieras sobre Algoritmo de Kruskal (directo, no tienes que registrarte)


Comentarios
(de más nuevos a más antiguos)


Aún no hay comentarios, ¡deja el primero!