Las diferencias entre árbol de expansión mínima y la ruta más corta del árbol

He aquí un especial:Las diferencias entre árbol de expansión mínima y la ruta más corta del árbol

Cualquiera de demostrar el siguiente o dar un contraejemplo:

(a) ¿Es el camino entre un par de vértices en un mínimo Spanning Tree de un gráfico no dirigido necesariamente el camino más corto (peso mínimo)?

(b) Suponga que el árbol de expansión mínimo del gráfico 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

(a)

No, por ejemplo, para el gráfico de 0, 1, 2, 0-1 es 4, 1-2 es 2, 2-0 es 5 , entonces la verdadera trayectoria más corta de 0-2 es 5, pero el MST es 0-1-2, en mst, 0-2 es 6

(b)

Mi problema viene a este (b).

No entiendo cómo whether the MST is unique puede afectar la ruta más corta.

En primer lugar, tengo entendido que cuando los pesos de los bordes no son distintos, pueden existir múltiples MST al mismo tiempo, ¿no?

En segundo lugar, incluso si MST es único, la respuesta de (a) anterior todavía se aplica para (b), ¿verdad?

Fuente

2012-05-04 Jackson Tale

¿Cómo se define 'MST unique''? – Deestan

Pregunto porque si "único" significa simplemente "existe solo un posible MST", entonces la pregunta es trivial y extraña porque la respuesta para (a) se aplica a (b), como dijiste. – Deestan

http://www.me.utexas.edu/~jensen%20/ORMM/methods/unit/network/subunits/mst_spt/index.html – Goodwine

En relación con (a), estoy de acuerdo.

En cuanto 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. Este gráfico tiene dos MST, {a-b-c} y {c-a-b}.

Sin embargo, su contraejemplo aún se cumple, porque el MST es único allí.

Fuente

2012-05-04 12:16:31 voidengine

Así que vamos a echar 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 se compone de los dos bordes A-B y B-C. Ningún otro conjunto de bordes forma un árbol de expansión mínimo. Por supuesto, la ruta más corta desde A hasta C es A-C, que no existe en el MST.

EDITAR

Así que para responder a la parte (b) la respuesta es no, porque hay un camino más corto que existe que no está en el MST.

Fuente

2012-05-04 12:09:40

¿No está relacionado el MST con el nodo de inicio?
Luego intenta obtener la ruta más corta desde el nodo de inicio MST. Por lo tanto, sí, ¡el camino más corto viene dado por el MST desde A!

Fuente

2014-02-03 18:32:08 Pedro

No del todo, un MST intentará utilizar los "menos recursos posibles" para * alcance * todos los nodos, y la ruta más corta le dará la ruta más corta desde el * origen * al * destino *. Piénselo de esta manera: ya ha caminado '100 millas desde A hasta B', 'B a C está a 50 millas de distancia', pero 'A a C estaba a 120 millas de distancia'. 'A-> C' seguramente es más corto que' A-> B-> C', pero te gustaría caminar 'B-> C', en lugar de volver, ¿no? – Goodwine

Las diferencias entre árbol de expansión mínima y la ruta más corta del árbol

Respuesta

Cuestiones relacionadas