El algoritmo de Kruskal es un algoritmo de la teoría de grafos que encuentra un árbol de expansión mínima de una conexión grafo ponderado . Esto significa que se encuentra un subconjunto de los bordes que forma un árbol que incluye todos los vértices , donde se minimiza el peso total de todas las aristas en el árbol. Si el gráfico no está conectado, entonces se encuentra un bosque de expansión mínima (un árbol de expansión mínimo para cada componente conectado). El algoritmo de Kruskal es un ejemplo de un algoritmo voraz .
Este algoritmo apareció por primera vez en Actas de la Sociedad Americana de Matemáticas , pp 48-50 en 1956, y fue escrito por Joseph Kruskal .
Otros algoritmos para este problema incluyen el algoritmo de Prim , el algoritmo inverso-Delete , y el algoritmo de Borůvka .
crear un bosque F (un conjunto de árboles), donde cada vértice de la gráfica es una separada de árboles[ editar ]
[ editar ]Rendimiento
Donde E es el número de aristas en el grafo y V es el número de vértices, el algoritmo de Kruskal se puede demostrar que se ejecutan en O ( E log E ) tiempo, o equivalente, O ( E log V del tiempo), todos ellos con estructuras de datos simples . Estos tiempos de funcionamiento son equivalentes porque:
- E está más en V 2 y log V 2 = 2log V
es O (log V ).
- Si dejamos de lado los vértices aislados, que cada uno sea su propio componente de la selva de expansión mínimo, V ≤ E 1, por lo que log V es O (log E ).
Podemos alcanzar esta cota de la siguiente manera: primero ordenar los bordes en peso con un tipo de comparación en O ( E log E ) el tiempo, lo que permite el paso de "quitar un borde con un peso mínimo de S "para operar en tiempo constante. A continuación, se utiliza una estructura de datos inconexos-set (Unión y Buscar) para mantener un seguimiento de los vértices están en los componentes. Tenemos que realizar O ( E ) de operaciones, dos de "encontrar" las operaciones y, posiblemente, un sindicato por cada lado. Incluso un simple disjuntos conjunto de estructuras de datos tales como los bosques conjunto disjuntos, con unión por rango puede realizar O ( E ) en las operaciones de O ( E log V ) tiempo. Por lo tanto el tiempo total es O ( E log E ) = O ( E log V ).
Siempre y cuando los bordes están ya ordenados, o se pueden ordenar en el tiempo lineal (por ejemplo con el conteo de clase o clase base ), el algoritmo se puede utilizar más sofisticados disjuntos conjunto de la estructura de datos para ejecutar en O ( E α ( V )) tiempo, donde α es la inversa con extrema lentitud de crecimiento de la de un solo valor la función de Ackermann .
| |
Imagen |
Descripti indicar su peso.Ninguno de los arcos se resaltan. |
 |
AD y CE son el menor arcos, con una longitud de 5, y el año ha sido arbitrariamente elegido, por lo que se pone de relieve. |
 |
CE es ahora el menor arco que no se forma un ciclo, con una longitud de 5, por lo que se destaca como el segundo de arco. |
 |
El siguiente arco, DF con una longitud de 6, se destaca con mucho el mismo método. |
 |
El menor de próxima arcos AB y BE , ambos con una longitud de 7. AB se elige arbitrariamente, y se resalta. El arco BD ha sido resaltada en rojo, porque ya existe una ruta (en verde) entre B y D , por lo que se forma un ciclo ( ABD ), si fueron elegidos. |
 |
El proceso continúa para resaltar el siguiente arco más pequeño, SE con una longitud de 7. Muchos arcos más se destacan en rojo en esta etapa: antes de Cristo , ya que se forma el bucle BCE , DE , ya que se forma el bucle de DEBA , y FE , ya que formaría FEBAD . |
 |
Finalmente, el proceso termina con el arco EG de longitud 9, y el árbol de expansión mínimo se encuentra. |
[ editar ]La prueba de la corrección
La prueba consta de dos partes. En primer lugar, se demuestra que el algoritmo produce un árbol de expansión. En segundo lugar, se comprueba que el árbol construido de expansión es de un peso mínimo.
[ editar ]árbol de expansión
Deje que P sea un grafo conexo, ponderado y dejar Y el subgrafo de P producido por el algoritmo. Y no se puede tener un ciclo, desde el borde último añadido para que el ciclo se han mantenido dentro de subárbol uno y no entre dos árboles diferentes. Y no se puede ser desconectado, ya que el borde encontró por primera vez que se une a dos componentes de Y se han añadido por el algoritmo. Por lo tanto, Y es un árbol de expansión de P .
[ editar ]Minimalidad
Se demuestra que la siguiente proposición P es verdadera por inducción : Si F es el conjunto de aristas elegidas en cualquier etapa del algoritmo, entonces hay algún árbol de expansión mínima que contiene F .
- Es evidente que P es cierto al principio, cuando F está vacío: ningún árbol de expansión mínima va a hacer, y no existe una causa un grafo conexo ponderado siempre tiene un árbol de expansión mínimo.
- Supongamos ahora que P es cierto para algunos borde sin límite fijada F y dejar que T es un árbol de expansión mínima que contiene F . Si el próximo elegido borde e también está en T , entoncesP es cierto para F + e . De lo contrario, T + e tiene un ciclo de C y no hay otra arista f que está en C , pero no F . (Si no existiera tal límite f , entonces e no podría haber sido añadido a la F , ya que al hacerlo se ha creado el ciclo C ). A continuación, T - f + e es un árbol, y tiene el mismo peso que la T , ya que T tiene un peso mínimo y el peso de f no puede ser menor que el peso delcorreo , de lo contrario el algoritmo se ha elegido f en lugar de correo . Por lo tanto T - f + e es un árbol de expansión mínimo que contiene F + e y otra vez P mantiene.
- Por lo tanto, por el principio de inducción, P mantiene cuando F se ha convertido en un árbol de expansión, que sólo es posible si F es un árbol de expansión mínimo sí mismo.
