Dado un gráfico ponderado y no dirigido G: ¿Qué condiciones deben ser ciertas para que haya múltiples árboles de expansión mínima para G?
Sé que el MST es único cuando todos los pesos son distintos, pero no puede revertir esta afirmación. Si hay varias aristas con el mismo peso en el gráfico, puede haber múltiples MST pero también puede haber solo una:
En este ejemplo, el gráfico de la izquierda tiene un MST único, pero el de la derecha no.
Lo más cerca que pude llegar a encontrar condiciones para la no unicidad del MST fue esto:
Considere todos los ciclos sin acordes (ciclos que no contienen otros ciclos) en el gráfico G. Si en cualquiera de estos ciclos el borde ponderado máximo existe varias veces, entonces el gráfico no tiene un árbol de expansión mínimo único.
Mi idea era que para un ciclo como este
Con n vértices, puede omitir exactamente uno de los bordes y aún tener todos los vértices conectados. Por lo tanto, tiene varias opciones para eliminar el borde con el mayor peso para obtener un MST, por lo que el MST no es único.
Sin embargo, luego se me ocurrió este ejemplo:
Puede ver que este gráfico tiene un ciclo que se adapta a mi condición: (E, F, G, H) pero, por lo que puedo ver, el árbol de expansión mínimo es único:
Entonces parece que mi condición no es correcta (o tal vez simplemente no es completamente correcta). Agradecería cualquier ayuda para encontrar las condiciones necesarias y suficientes para la no unicidad del árbol de expansión mínima.
Respuestas:
en la primera imagen: el gráfico de la derecha tiene un MST único, al tomar bordes y ( F , G ) con un peso total de 2.( F, H) ( F, G ) Dado un grafo y dejar que M = ( V , F ) ser un árbol de expansión mínima (MST) en G .G = ( V, E) METRO= ( V, F) sol
Si existe un borde con un peso w ( e ) = m tal que sumar e a nuestro MST produce un ciclo C , y que m también sea el peso del borde más bajo de F ∩ C , entonces podemos crear un segundo MST intercambiando un borde de F ∩ C con peso de borde m con e . Por lo tanto, no tenemos singularidad.e = { v , w } ∈ E∖ F w ( e ) = m mi do metro F∩C F∩ C metro mi
fuente
Una respuesta anterior indica un algoritmo para determinar si hay múltiples MST, que, para cada borde no está en G , encuentra el ciclo creado al agregar e a un MST precalculado y verifica si e no es el borde más pesado único en ese ciclo. Es probable que ese algoritmo se ejecute en tiempo O ( | E | | V | ) .e G e e O(|E||V|)
Un algoritmo más simple para determinar si hay múltiples MST de G en complejidad de tiempoO(|E|log(|V|)) .
Una ejecución ordinaria del algoritmo de Kruskal toma tiempo . La selección adicional de aristas que no están en m se puede hacer en tiempo O ( | E | ) . Entonces el algoritmo logra O ( | E | log ( | V | ) ) tiempo-complejidad.O(|E|log(|V|)) m O(|E|) O(|E|log(|V|))
¿Por qué este algoritmo puede determinar si hay múltiples MST?
Supongamos que tenemos un MST que no es lo mismo que m . Es suficiente para mostrar que el algoritmo que se ejecuta en G no alcanzará el paso 3, ya que el borde que se encuentra al final del paso 2, que no está en my conectando dos árboles diferentes, se habría incluido en el MST resultante si hubiéramos ejecutado Kruskal's algoritmo hasta su finalización. Sea w el mayor peso tal que para cualquier borde que pese menos que w , esté en m si y solo si está en m ' . Debido a que m y m ' tienen el mismo número de aristas de peso w , existen bordes de pesom′ m G m w w m m′ m m′ w que están en m ' pero no en m . Si el algoritmo ha salido antes de procesar los bordes de esos bordes, hemos terminado. De lo contrario, suponga que el algoritmo va a procesar el primer borde e ' entre esos bordes ahora. Sea S el conjunto de todos los bordes que se han conservado hasta ahora para ser incluidos en el MST resultante. S ⊂ m . Dado que el algoritmo no ha terminado de procesar bordes de peso w no en m , como e ' , no debe haber comenzado a procesar bordes de peso w en m . Entonces bordes en Sw m′ m e′ S S⊂m w m e′ w m S pesar menos que . Eso significa S ⊂ m ′ . Recordemos que e ′ está en m ′ . Desde { e ' } ∪ S ⊂ m ' , donde m ' es un árbol, e ' debe conectar dos árboles diferentes en S y las salidas del algoritmo en este punto.w S⊂m′. e′ m′ {e′}∪S⊂m′ m′ e′ S
Nota sobre el desarrollo posterior El
paso 1 y el paso 2 se pueden intercalar para que podamos terminar el algoritmo lo antes posible sin procesar bordes de pesos mayores.
En caso de que desee calcular el número de MST, puede verificar una respuesta sobre cómo calcular el número de MST .
fuente
Sea un gráfico conectado no direccionado (finito simple) con al menos dos vértices. Deje ST significa árbol de expansión y MST significa árbol de expansión mínima. Permítanme definir primero algunos términos menos comunes.G
¿Cuándo hay más de un árbol de expansión mínimo?
Para responder la pregunta de OP, aquí hay cinco caracterizaciones de que tiene más de un MSTG .
La novedad de esta respuesta son principalmente las dos últimas caracterizaciones. La segunda de la última caracterización puede considerarse como el próximo paso del enfoque del PO . Las primeras tres caracterizaciones juntas pueden considerarse como una versión ligeramente mejorada de la respuesta de dtt .
Es más fácil pensar en el término opuesto, si tiene un MST único. La siguiente es la versión opuesta y equivalente de las caracterizaciones anteriores.G
¿Cuándo es único el árbol de expansión mínimo?
Teorema: las siguientes propiedades de son equivalentes.G
Aquí viene mi prueba.
"Uniqueness of MST" => "Sin MST adyacente": obvio.
"No hay MST adyacentes" => "Un MST aislado": obvio.
"One isolated MST" => "Un mínimo local ST": un MST aislado es más ligero que todos los ST adyacentes.
"Un mínimo local ST" => "Borde de ciclo extremo": Sea un ST que sea más ligero que todos los ST adyacentes.m
"Mínimo local ST" => "Borde de corte extremo": la prueba se deja como ejercicio.
"Extreme cut edge" => "Uniqueness of MST": Proof is left as an exercise.
The above chains of implications proves the theorem.
Once again, the novelty of this answers is mostly the "extreme cycle edge" property and the "extreme cut edge" property, which uses the concepts, non-cycle-heaviest and non-cut-lightest. I have not seen those concepts elsewhere, although they are quite natural.
Here are two related interesting observations.
Two sufficient but not necessary conditions for unique MST
the uniqueness of the heaviest edge in every cycle implies the "extreme cycle edge" property. So it is a sufficient condition. A counterexample to its being necessary condition is the graph with weightsab→1,bc→1,cd→1,da→2,ac→2 .
the uniqueness of the lightest edge in every cut-set implies the "extreme cut edge" property. So it is a sufficient. A counterexample to its being necessary condition is a triangle with weights1,1,2 .
fuente