Le differenze tra minimo Spanning Tree e Shortest Path Albero

Question

Ecco un accise:

O dimostrare il seguente o dare un contro:

(a) è il percorso tra un paio di vertici in un minimo spanning tree di un grafo non orientato necessariamente il percorso più breve (peso minimo)?

(b) Supponiamo che l'albero spanning minimo del grafico sia unico. il percorso tra una coppia di vertici in un albero di copertura minimo di un grafo orientato necessariamente il percorso più breve (peso minimo)?

mia risposta è

(a)

n, per esempio, per il grafico 0, 1, 2, 0-1 è 4, 1-2 è 2, 2-0 è 5 , poi vero percorso più breve 0-2 di è 5, ma il MST è 0-1-2, in MST, 0-2 è 6

(b)

il mio problema viene in questo (b).

Non capisco come whether the MST is unique possa influire sul percorso più breve.

In primo luogo, la mia comprensione è che quando i pesi dei bordi non sono distinti, possono esistere più MST allo stesso tempo, giusto?

Secondo, anche se MST è univoco, la risposta di (a) sopra si applica ancora per (b), giusto?

Answer 1

Per quanto riguarda (a), sono d'accordo.

Riguardo a (b), per alcuni grafici, potrebbero esserci più spanning tree con lo stesso peso. Considera un cerchio C3 con i vertici a, b, c; pesi a-> b = 1, b-> c = 2, a-> c = 2. Questo grafico ha due MST, {a-b-c} e {c-a-b}.

Tuttavia, il tuo controesempio rimane valido, poiché l'MST è unico lì.

Answer 2

così lascia dare un'occhiata a un semplice grafico:

(A)---2----(B)----2---(C) 
\     /
    ---------3---------- 

L'albero di copertura minima per questo grafico è costituito da due bordi A-B e B-C. Nessun altro gruppo di spigoli forma un albero spanning minimo.

Ma ovviamente il percorso più breve da A a C è A-C, che non esiste nel MST.

EDIT

Quindi, per rispondere parte (b) la risposta è no, perché non v'è un percorso più breve che esiste che non è nel MST.

Answer 3

L'MST non è correlato al nodo di avvio ?!
Quindi sta cercando di ottenere il percorso più breve dal nodo di avvio MST. Pertanto, sì, il percorso più breve è dato dal MST a partire da A!