Różnice między Minimum Spanning Tree i Najkrótsza ścieżka drzewa

Question

Oto akcyzowy:

Albo udowodnić następujące albo dać kontrprzykład:

(a) jest ścieżką między parą wierzchołków w minimalnej spanning tree nie przeszła grafu musi być najkrótsza (minimalna i waga) ścieżka?

(b) Załóżmy, że minimalne drzewo opinające wykresu jest unikalne. Czy ścieżka między parą wierzchołków w minimalnym drzewie opinającym z nieokreślonego grafu koniecznie musi być najkrótszą ścieżką (o minimalnej wadze)?

moja odpowiedź

(A)

nie, na przykład, na wykresie 0, 1, 2, 4 0-1 to 1-2 wynosi 2, 2-0 jest 5 , następnie 0-2 jest prawda najkrótsza ścieżka jest 5, ale MST jest 0-1-2, w MST 0-2 jest 6

(b)

Mój problem jest w tym (b).

Nie rozumiem, jak whether the MST is unique może wpłynąć na najkrótszą ścieżkę.

Po pierwsze, Rozumiem, że gdy waga brzegów nie jest różna, może istnieć wiele MST w tym samym czasie, prawda?

Po drugie, nawet jeśli MST jest unikatowy, odpowiedź (a) nadal obowiązuje dla (b), prawda?

Answer 1

Odnośnie (a), zgadzam się.

Odnośnie (b), dla niektórych wykresów może być więcej drzew o minimalnym opasaniu z taką samą wagą. Rozważmy okrąg C3 z wierzchołkami a, b, c; waga a-> b = 1, b-> c = 2, a-> c = 2. Ten wykres ma dwa MST: {a-b-c} i {c-a-b}.

Mimo to, twój kontrprzykład wciąż trwa, ponieważ MST jest tam unikalny.

Answer 2

Więc pozwala przyjrzeć się z bardzo prostego wykresu:

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

Minimalne drzewo rozpinające na tym wykresie składa się z dwóch krawędzi A-B i B-C. Żaden inny zestaw krawędzi nie tworzy minimalnego drzewa opinającego.

Ale oczywiście najkrótsza ścieżka od A do C to A-C, która nie istnieje w MST.

EDIT

Więc odpowiedzieć na część (b) odpowiedź brzmi nie, ponieważ jest krótsza ścieżka, która istnieje, że nie jest w MSP.

Answer 3

Czy MST nie jest powiązany z węzłem początkowym ?!
Następnie próbuje uzyskać najkrótszą ścieżkę z węzła początkowego MST. Dlatego tak, najkrótsza ścieżka jest podawana przez MST począwszy od A!