El gráfico tiene dos / tres diferentes árboles de expansión mínima?

15

Estoy tratando de encontrar un método eficiente para detectar si un determinado gráfico G tiene dos árboles de expansión mínima diferentes. También estoy tratando de encontrar un método para verificar si tiene 3 árboles de expansión mínima diferentes. La solución ingenua que he pensado es ejecutar el algoritmo de Kruskal una vez y encontrar el peso total del árbol de expansión mínimo. Más tarde, eliminando un borde del gráfico y ejecutando el algoritmo de Kruskal nuevamente y verificando si el peso del nuevo árbol es el peso del árbol de expansión mínimo original, y así para cada borde en el gráfico. El tiempo de ejecución es O (| V || E | log | V |), que no es bueno en absoluto, y creo que hay una mejor manera de hacerlo.

Cualquier sugerencia sería útil, gracias de antemano

Itamar
fuente
Sería bueno que se awared de dicho algoritmo, pero no va a resolver este problema actual
itamar
2
El gráfico tendrá un árbol de expansión mínimo único si y solo si (1) para cualquier partición de V ( G ) en dos subconjuntos, el borde de peso mínimo con un punto final en cada subconjunto es único y (2) el peso máximo La ventaja en cualquier ciclo de G es única. GV(G)G
Juho
¿Estas preguntas uno y dos ya responden a su pregunta?
Juho
Vea el problema 23-1 en CLRS para saber cómo encontrar el segundo mejor MST en . O(n2)
Kaveh

Respuestas:

7

Kapoor & Ramesh ( versión adecuada de SIAM J. Comput. , Versión gratuita (?) Del sitio web personal ) ofrecen un algoritmo para enumerar todos los árboles de expansión mínima en gráficos ponderados y no ponderados.

Entiendo que la idea básica es que comiences con un MST, luego intercambies los bordes que se encuentran a lo largo de los ciclos en el gráfico (de modo que mientras los pesos estén bien, estás reemplazando un borde con otro que sabes que volverá a conectar el árbol) .

Para el caso ponderado, dan un tiempo de ejecución para enumerar todos los árboles de expansión mínimos de donde N es el número de tales árboles de expansión. Los enumera en orden de aumento de peso, y mi comprensión actual (superficial) sugiere que es perfectamente factible terminar el algoritmo después de que haya generado un número determinado de árboles (ya que solo comienza con el MST y los produce secuencialmente).O(N|V|)N

Luke Mathieson
fuente
En esta situación aquí, nos gustaría abortar el algoritmo temprano una vez que sepamos que hay más de soluciones. ¿El algoritmo lo permite? k
Raphael
1
@Raphael, no he tenido tiempo de entenderlo realmente (marcación de asignación), pero desde mi comprensión, debería ser posible: comienza con un poco de MST, luego genera otros uno por uno.
Luke Mathieson
1
@SaeedAmiri: "El número de tales árboles de expansión" significa "el número de árboles de expansión mínima ", no "el número de árboles de expansión". Si todos los árboles de expansión son árboles de expansión mínima, entonces el gráfico de entrada está completo y todos los bordes tienen el mismo peso. nn2
JeffE
1
El documento considera tanto los gráficos ponderados como los no ponderados, por lo que ambos tienen razón;). También creo que el algoritmo permite la posibilidad de detenerse después de que haya generado la cantidad de árboles que desea, por lo que para OP esto lo reduce a . Nuevamente, necesito algo de tiempo libre para ver mejor. O(|V|)
Luke Mathieson
1
Después de una lectura rápida, el algoritmo ponderado genera los árboles en orden de peso creciente (a partir de un MST obviamente). Entonces debería ser para los propósitos del OP.
Luke Mathieson
2

Uno puede demostrar que el algoritmo de Kruskal puede encontrar cada árbol de expansión mínimo; mira aquí .

Por lo tanto, puede ejecutar Kruskal y siempre que tenga múltiples aristas para elegir, bifurcar. Una vez que se ha ramificado veces, sabe que hay al menos k diferentes árboles de expansión mínima. kkDesafortunadamente, varias ramas pueden dar como resultado el mismo árbol al agregar bordes del mismo peso en diferentes órdenes, por lo que esto no ayuda mucho sin más trabajo / conocimiento.

Rafael
fuente
55
No. Si tiene que elegir entre bordes en un solo paso, puede ser que esos k bordes estén en todos los árboles de expansión. Tomemos, por ejemplo, solo una estrella K 1 , 5 con todos los bordes de peso 1. Primer paso, es necesario elegir entre los 5 bordes, etc. Pero obviamente solo hay un árbol de expansión. ¿Quizás contar el número de bordes con el mismo peso en un borde incluido en el árbol de expansión que quedan fuera ayuda? Pregunta interesante ...kkK1,5
vonbrand
@vonbrand Buen punto. Podemos continuar para terminar todas las ramas del cálculo, por supuesto, pero luego el tiempo de ejecución está determinado por el número de árboles que se extienden, que pueden ser exponenciales.
Raphael
1

Para ver si hay más de un MST, considere, por ejemplo, el algoritmo de Kruskal. La única forma en que podría construir diferentes MST es omitiendo bordes eligiendo otro cuando haya varios con el mismo peso. Pero esos bordes del mismo peso podrían haberse descartado porque formaron un ciclo con bordes más claros ...

Por lo tanto, debe ejecutar el algoritmo de Kruskal, y cuando haya varios bordes con el mismo peso a considerar, agregue todos los que se puedan agregar sin crear ciclos. Si queda un borde de este peso, y no cierra un ciclo con ninguno de los bordes con pesos más bajos (que se agregaron antes), hay más de un MST. Comprobar si hay exactamente 2 o 3 o más, etc. parece mucho más difícil ...

vonbrand
fuente
0

Modificación del algoritmo de Kruskal: al ordenar los bordes, agrupe los bordes con el mismo peso. Ahora, en el punto donde procesa los bordes en orden, cada vez que alcanza un nuevo clúster, primero verifique todos los bordes por separado y elimine del clúster los que cerrarían un ciclo, dado lo que se construyó antes del clúster. Luego, ejecute todos los bordes restantes en el clúster ahora tratando de agregarlos al MST. Si alguno de ellos cierra un ciclo, eso fue necesariamente debido a otros bordes del mismo clúster insertado anteriormente, lo que significa que tiene más de un MST.

Esa solución conserva la complejidad del algoritmo de Kruskal, solo que aumenta el tiempo para cada borde procesado.

Carlos A. Prolo
fuente
Parece que está afirmando que puede procesar un clúster completo en tiempo constante, pero no veo ningún límite constante obvio en el tamaño de un clúster. ¿Podría dar más detalles sobre cómo se realiza esa etapa?
David Richerby