El algoritmo de Kruskal: la construcción del esqueleto óptimo

A principios del siglo XIX, el geómetra de Berlín, Jacob Steinerestablecer la tarea de cómo conectar las tres aldeas para que su longitud sea la más corta. Más tarde, se resume el problema: es necesario encontrar un punto en un plano, la distancia desde ella a n otros puntos fueron los más bajos. En el siglo XX, el trabajo sobre este tema continuó. Se decidió tomar varios puntos y conectarlos de tal forma que la distancia entre ellos fuera la más corta. Este es todo un caso especial del problema bajo estudio.

Algoritmos codiciosos

El algoritmo de Kruskal se refiere a algoritmos "codiciosos"(también se les llama gradiente). La esencia de aquellos: la mayor victoria en cada paso. Los algoritmos no siempre "codiciosos" brindan la mejor solución para la tarea. Existe una teoría que muestra que cuando se aplican a problemas específicos, proporcionan la solución óptima. Esta es la teoría de los matroids. El algoritmo de Kruskal se relaciona con tales problemas.

Encontrar el esqueleto del peso mínimo

El algoritmo bajo consideración construye un óptimoel esqueleto de la gráfica. El problema al respecto es el siguiente. Se proporciona un gráfico no dirigido sin múltiples aristas y bucles, y en su conjunto de aristas se le asigna una función de ponderación w que asigna a cada arista un número - el peso del filo - w (e). El peso de cada subconjunto del conjunto de bordes está determinado por la suma de los pesos de sus bordes. Se requiere encontrar el esqueleto del peso más pequeño.

Descripción

El algoritmo de Kruskal funciona así. Primero, todos los bordes del gráfico original están ordenados para aumentar el peso. Inicialmente, el marco no contiene ningún borde, pero incluye todos los vértices del gráfico. Después del siguiente paso del algoritmo, se agrega un borde a la parte ya construida del marco, que es un bosque que se extiende. No se elige arbitrariamente. Todos los bordes del gráfico que no pertenecen al esqueleto se pueden llamar rojo y verde. Los vértices de cada costilla roja están en un componente de la conectividad del bosque que se está construyendo, y los vértices del verde están en diferentes componentes. Por lo tanto, si agrega un borde rojo allí, aparece un ciclo, y si es verde: en el paso del bosque resultante, el componente de conectividad será menos uno. Por lo tanto, no se puede agregar borde rojo a la construcción resultante, pero se puede agregar cualquier borde verde para obtener el bosque. Y se agrega una costilla verde con un peso mínimo. Como resultado, se obtiene el esqueleto del menor peso.

Implementación

Denota el bosque actual F. Divide el conjunto de vértices del gráfico en dominios conectados (su unión forma F, y no se cruzan en pares). Los bordes rojos tienen ambos vértices en una parte. La parte (x) es una función que devuelve el nombre de la parte a la que pertenece x para cada vértice x. Unite (x, y) es un procedimiento que construye una nueva partición que consiste en la unión de las partes xey, y todas las demás partes. Deje n ser el número de bordes del gráfico. Todos estos conceptos están incluidos en el algoritmo de Kruskal. Implementación:

Organice todos los bordes del gráfico desde la 1 a la enésima pesas ascendentes. (ai, bi son los vértices del borde con índice i).
para i = 1 a n hacer.
x: = Parte (ai).
y: = Parte (bi).
Si x no es igual a y luego Unite (x, y), incluya el borde con el número i en F.

Corrección

Deje que T sea el esqueleto del gráfico original construido usando el algoritmo de Kruskal, y que S sea su esqueleto arbitrario. Es necesario demostrar que w (T) no excede w (S).

Deje que M sea el conjunto de bordes de S, P el conjunto de bordesT. Si S no es igual a T, entonces hay un borde et del esqueleto T que no pertenece a S. Unimos et a S. Formamos un ciclo, lo llamamos C. Eliminamos de C cualquier borde que pertenezca a S. Se obtiene un nuevo esqueleto, y hay tantos vértices en él. Su peso no excede w (S), ya que w (et) no es mayor que w (es) por el algoritmo de Kruskal. Esta operación (el reemplazo de los bordes de S por los bordes de T) se repetirá hasta que obtengamos T. El peso de cada esqueleto sucesivo resultante no es mayor que el peso del anterior, de lo cual se deduce que w (T) es como máximo w (S).

Además, la precisión del algoritmo de Kruskal se desprende del teorema de Rado-Edmonds en matroids.

Ejemplos de la aplicación del algoritmo de Kruskal

Dado un gráfico con vértices a, b, c, d, ey bordes (a,b), (a, e), (b, c), (b, e), (c, d), (c, e), (d, e). Los pesos de los bordes se muestran en la tabla y en la figura. Inicialmente, la construcción del bosque F contiene todos los vértices del gráfico y no contiene un solo borde. Algoritmo de Kruskal primero añadir costilla (a, e), ya que el peso tenía el más bajo, y los vértices A y E son en diferentes componentes de conectividad madera F (costilla (a, e) es de color verde), entonces el nervio (c, d), porque que al menos este peso borde de los bordes del gráfico, que no pertenecen a F, y es de color verde, a continuación, por las mismas razones se acumulan borde (a, b). Pero se pasa el borde (B, E), a pesar de que él y el peso mínimo de los bordes restantes, ya que es de color rojo: los vértices B y E pertenecen a la misma componente de conectividad bosque F, es decir, si añadimos a F el borde (B, E), está formada ciclo. Luego se agrega el borde verde (b, c), se salta el borde rojo (c, e) y luego d, e. Por lo tanto, los bordes (a, e), (c, d), (a, b), (b, c) se agregan en secuencia. De ella, el esqueleto óptimo del gráfico original consiste. Así es como funciona el algoritmo en este caso Me teñí Un ejemplo muestra esto.

La figura muestra un gráfico que consta de dos componentes de conectividad. Las líneas en negrita muestran los bordes del marco óptimo (verde), construido con el algoritmo de Kruskal.

La figura superior muestra el gráfico original, y en la inferior, el esqueleto del peso mínimo, construido para él con la ayuda del algoritmo considerado.

La secuencia de las nervaduras añadidas (1,6); (0,3), (2,6) o (2,6), (0,3) - no es importante; (3,4); (0,1), (1,6) o (1,6), (0,1), también cuidar (5,6).

El algoritmo de Kruskal encuentra una aplicación práctica, por ejemplo, para optimizar las plataformas de comunicación, las carreteras en nuevos barrios en las localidades de cada país y también en otros casos.