algorithm - resueltos - Diferencias entre el árbol de expansión mínimo y el árbol de ruta más corta
problema del arbol de minima expansion ejercicios (4)
Aquí hay un impuesto especial:
Prueba lo siguiente o da un contraejemplo:
(a) ¿Es la ruta entre un par de vértices en un árbol de expansión mínimo de un gráfico no dirigido necesariamente la ruta más corta (peso mínimo)?
(b) Suponga que el árbol de expansión mínimo de la gráfica es único. ¿Es la ruta entre un par de vértices en un árbol de expansión mínimo de un gráfico no dirigido necesariamente la ruta más corta (peso mínimo)?
Mi respuesta es
(una)
No, por ejemplo, para el gráfico 0, 1, 2, 0-1 es 4, 1-2 es 2, 2-0 es 5, entonces la ruta más corta verdadera de 0-2 es 5, pero el mst es 0-1-2 , en mst, 0-2 es 6
(segundo)
Mi problema entra en esto (b).
No entiendo cómo whether the MST is unique puede afectar el camino más corto.
Primero, mi entendimiento es que cuando los pesos de los bordes no son distintos, pueden existir múltiples MST al mismo tiempo, ¿verdad?
Segundo, incluso si MST es único, la respuesta de (a) aún se aplica para (b), ¿verdad?
AD a)
Una visualización muy simple sería:
MSP en una gráfica:
El camino más corto entre A y C:
AD b)
Supongo que la singularidad de MSP significa que solo hay 1 MSP MSP en un gráfico. Entonces: Primero) Sí, si los pesos de los bordes no son distintos, pueden existir múltiples MST al mismo tiempo. En el caso de nuestro gráfico, otro MSP posible incluiría arco DC en lugar de AB (como ejemplo). Segundo) La unicidad de MST no influye en la respuesta para a). Como ejemplo:
¿No está relacionado el MST con el nodo de inicio?
Entonces él está tratando de obtener la ruta más corta desde el nodo de inicio MST. Por lo tanto, sí, la ruta más corta la da el MST a partir de A !
Así que echemos un vistazo a un gráfico muy simple:
(A)---2----(B)----2---(C)
/ /
---------3----------
El árbol de expansión mínimo para este gráfico consiste en los dos bordes AB y BC . Ningún otro conjunto de bordes forma un árbol de expansión mínimo.
Pero, por supuesto, el camino más corto de A a C es AC , que no existe en el MST.
EDITAR
Entonces, para responder a la parte (b), la respuesta es no, porque existe una ruta más corta que no está en el MST.
Con respecto a (a), estoy de acuerdo.
Con respecto a (b), para algunos gráficos, puede haber más árboles de expansión mínima con el mismo peso. Considere un círculo C3 con vértices a, b, c; pesos a-> b = 1, b-> c = 2, a-> c = 2. Esta gráfica tiene dos MST, {abc} y {cab}.
Sin embargo, su contraejemplo todavía se mantiene, porque el MST es único allí.