Creo que esto es cierto, pero tampoco he podido obtener una prueba formal. ¿Pero es cierto que cualquier árbol de expansión mínimo es accesible mediante la aplicación del algoritmo de Kruskal? Del mismo modo, ¿es esto cierto para el algoritmo de Prim?
EDITAR: Para ser más precisos, quiero saber si se le da un MST para un gráfico ponderado conectado, no dirigido, se garantiza que haya una secuencia de pasos usando Kruskal o Prim que genere este MST. Por ejemplo, hay diferentes opciones para Kruskal cuando hay varias aristas con el mismo peso. De manera similar para Prim.
algorithms
graphs
minimum-spanning-tree
domoremath
fuente
fuente
Respuestas:
Según lo indicado por el comentario de Rafael y el comentario de j_random_hacker , la respuesta es positiva. De hecho, cualquier MST es accesible por cualquier algoritmo MST con algunas excepciones menores.
Para un gráfico , dos funciones de peso en todos los bordes (a números reales) se definen como (débilmente) compatibles con la comparación (entre sí) si podemos extender el orden débil estricto en los bordes inducido por cualquiera de las funciones de peso al mismo estricto orden total. Es decir, podemos diseñar reglas de desempate consistentes con cada función de peso para que el resultado de la comparación de cualquiera de los dos bordes por una función de peso y sus reglas de desempate sea el mismo que el resultado de la otra función de peso y su empate. rompiendo las reglas.sol
La prueba del lema 1 se deja como un ejercicio fácil.
(Sugerencia para) Prueba: Un enfoque es verificar la condición 5 del lema 1. Otro enfoque es verificar la condición 2 del lema 1 mostrando que en cualquier conjunto de bordes, un borde más claro por también es un borde más claro por w 1 ,w2 w1
Un algoritmo basado en la comparación en un gráfico se define como compatible con la comparación si para cualquiera de las dos funciones de peso (débilmente) compatibles con la comparación en todos los bordes, podemos ejecutar el algoritmo con una función de peso de una manera que se pueda repetir sin ningún cambio con la otra función de peso. En particular, esas dos ejecuciones del algoritmo tendrán la misma salida.sol
Tenga en cuenta que la mayoría, si no todos, los algoritmos MST se pueden establecer en dos tipos. El primer sabor supone que los bordes distintos de tienen pesos distintos, que se utiliza cuando la principal preocupación es encontrar un MST (que de hecho es también el MST único). El segundo sabor permite que distintos bordes de G tengan los mismos pesos. Por supuesto, en esta respuesta, donde la principal preocupación es encontrar todos los MST, solo nos interesarán los algoritmos de MST en el segundo sabor.sol sol
Un algoritmo MST compatible con la comparación puede encontrar todos los MST.
Para probar la proposición anterior, solo necesitamos adaptar ligeramente la sección "Kruskal puede encontrar cada MST" en el cálculo del número de MST . Para cualquier MST de G con función de peso w 1 , elija un peso positivo que sea más ligero que la diferencia absoluta entre cualquier par de pesos de borde desiguales. Si restamos ese peso del peso de cada borde en m sin cambiar los pesos de otros bordes, obtenemos una nueva función de peso, digamos, w 2 . Si el borde e 1 es más claro que e 2 por w 1 , e 1 debe ser más claro quemetro sol w1 metro w2 mi1 mi2 w1 mi1 por w 2 también. Por el Lema 2, w 1 y w 2 son compatibles comparación. Tenga en cuenta que m es el MST único con w 2 . (Una forma de mostrar esta singularidad es demostrar que cada vez que se reduce el peso de un borde MST, cualquier MST con la nueva función de peso debe contener ese borde). Por lo tanto, cualquier ejecución del algoritmo en w 2 encontrará m . Debido a que el algoritmo es compatible con la comparación, podemos ejecutar el algoritmo de la misma manera con w 1 o con w 2 . Dado que esa ejecución encontrará el MST único, m conmi2 w2 w1 w2 metro w2 w2 metro w1 w2 metro , encontrará m también con w 1 .w2 metro w1
Cada algoritmo MST es compatible con la comparación
La proposición anterior suena demasiado amplia. Bueno, por cada algoritmo MST, me refiero a cualquier algoritmo MST general basado en la comparación que he visto, excluyendo aquellos aparentemente patológicos como incorrectos o que tienen pasos innecesarios. Dado que un algoritmo MST compatible con la comparación puede encontrar todos los MST, cada algoritmo MST puede encontrar todos los MST. En particular, cada uno de los cuatro algoritmos clásicos de MST , a saber, los algoritmos de Borůvka, Prim, Kruskal y de eliminación inversa pueden encontrar todos los MST.
Aquí hay tres algoritmos MST más compatibles con la comparación.
El siguiente algoritmo MST no es compatible con la comparación.
Tenga en cuenta que los ocho algoritmos MST mencionados anteriormente se basan en la comparación.
¿Cómo mostrar un algoritmo es compatible con la comparación?
Usaré el algoritmo de Kruskal como ejemplo. Aquí está la descripción del algoritmo de Kruskal (en el segundo sabor) en un gráfico no dirigido conectado ponderado .sol
Un algoritmo es compatible con la comparación si, en términos generales, se puede describir en tres tipos de pasos.
Esta condición suficiente cubre los algoritmos Borůvka, Prim, Kruskal, reverse-delete, delete-heavy-edge y add-non-heavy-edge. Tenga en cuenta que para cumplir con esta condición suficiente, es posible que tengamos que cambiar ciertas descripciones de un algoritmo sin afectar el conjunto de MST alcanzables. Debido a la excepción de que el algoritmo de Kruskal con sesgo de grado es compatible con la comparación, permítanme enfatizar que esta condición suficiente se describe en términos sueltos
fuente