Unterschiede zwischen Minimum Spanning Tree und Shortest Path Baum

Question

Hier ist ein Verbrauch:

Entweder die folgenden beweisen oder ein Gegenbeispiel geben:

(a) Ist der Weg zwischen einem Paar von Scheitelpunkten in einem Minimum Spanning Tree eines ungerichteten Graphen notwendigerweise der kürzeste (Mindestgewicht) Pfad?

(b) Angenommen, der minimale Spannbaum des Graphen ist eindeutig. Ist der Pfad zwischen einem Scheitelpunktpaar in einem minimalen Spannbaum eines ungerichteten Graphen notwendigerweise der kürzeste Weg (minimales Gewicht)?

Meine Antwort ist

(a)

Nein, beispielsweise für die graphische Darstellung, 0, 1, 2, 0-1 4 1-2 2 ist, 2-0 ist, 5 , dann 0-2 wahre kürzester Weg 5, aber die mst ist 0-1-2, in mst 0-2 6

(b)

Mein Problem in dieser kommt (b).

Ich verstehe nicht, wie whether the MST is unique den kürzesten Weg beeinflussen kann.

Erstens, Mein Verständnis ist, dass, wenn die Gewichte der Kanten nicht unterscheidbar sind, mehrere MST zur gleichen Zeit existieren können, oder?

Zweitens, selbst wenn MST einzigartig ist, gilt die Antwort von (a) immer noch für (b), oder?

Answer 1

Bezüglich (a) stimme ich zu.

In Bezug auf (b) kann es bei einigen Graphen mehr minimal aufspannende Bäume mit dem gleichen Gewicht geben. Betrachten Sie einen Kreis C3 mit den Ecken a, b, c; Gewichte a-> b = 1, b-> c = 2, a-> c = 2. Dieser Graph hat zwei MSTs, {a-b-c} und {c-a-b}.

Trotzdem gilt Ihr Gegenbeispiel immer noch, denn die MST ist dort einzigartig.

Answer 2

So kann in einem sehr einfachen Graphen einen Blick:

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

Der minimale Spannbaum für dieses Graphen besteht aus den beiden Kanten A-B und B-C. Keine andere Gruppe von Kanten bildet einen minimalen Spannbaum.

Aber natürlich ist der kürzeste Weg von A zu CA-C, die nicht in der MST existiert.

EDIT

So Teil (b) die Antwort nein ist, zu beantworten, weil es ein kürzerer Weg ist, die also nicht in der MST besteht.

Answer 3

Ist die MST nicht auf den Startknoten bezogen ?!
Dann versucht er den kürzesten Pfad vom MST Startknoten zu bekommen. Also, ja, der kürzeste Weg ist von der MST ausgehend von A gegeben!