Ein minimaler Flaschenhalsspannbaum einer gewichteten Grafik G ist ein Spannbaum von G, der das maximale Gewicht jeder Kante im Spannbaum minimiert. Ein MBST ist nicht unbedingt ein MST (minimum spanning tree).Wie unterscheidet sich ein Spannweitenbaum mit minimalem Engpass von einem minimalen Spannbaum?
Bitte geben Sie ein Beispiel, wo diese Aussagen sinnvoll sind.
Blick auf den MST example on Wikipedia Referenz:
Ein Engpaß in einem Spanning-Tree ist ein Maximalgewicht Rand in diesem Baum. Es kann mehrere Engpässe geben (natürlich alle das gleiche Gewicht) in einem Spannbaum. In der Wikipedia MST gibt es zwei Flaschenhälse von Gewicht 8.
Nun, nehmen Sie einen minimalen Spannbaum eines gegebenen Graphen (es kann mehrere MSTs geben, alle mit dem gleichen Gesamtkantengewicht natürlich) und nennen Sie das maximale Kantengewicht B. In unserem Beispiel ist B = 8.
Jeder Spanning-Baum, der ebenfalls einen Engpass von B = 8 hat, ist ein MBST. Aber es ist vielleicht kein MST (weil das gesamte Kantengewicht größer als das bestmögliche ist).
So nehmen Sie die Wikipedia MST und ändern Sie es (hinzufügen/entfernen einige Kanten), so dass
zum Beispiel ändern
Bevor Sie Ihre Frage zu beantworten, lassen Sie mich einige Begriffe definieren, die hier verwendet werden, ...
1) Spanning Tree: Spanning Tree eines Graphen ist ein Baum, der die Eckpunkte alle in diesem Diagramm abdeckt.
2) Minimaler Spannbaum (MST): MST eines gegebenen Graphen ist ein Spannbaum, dessen Länge unter allen möglichen Spannbäumen dieses Graphen minimal ist. Deutlicher, für einen gegebenen Graph liste alle möglichen aufspannenden Bäume (die sehr groß sein können) auf und wähle diejenige, deren Summe der Kantengewichte minimal ist.
3) Minimum Engpass Spanning Tree (MBST): MBST eines gegebenen Graphen ist ein Spanning-Tree, dessen maximales Kantengewicht unter allen möglichen Spanning-Bäumen minimal ist. Deutlicher, für einen gegebenen Graph liste man alle möglichen Spannbäume und das maximale Kantengewicht für jeden der Spannbäume auf. Unter diesen wählen Sie den Spannbaum, dessen maximales Kantengewicht minimal ist.
uns jetzt auf das folgende Bild mit einem Vier-Knoten-Graph aussehen lassen ...
Graph-A ist die gegebene ursprünglichen Graphen. Wenn ich alle möglichen aufspannenden Bäume für dieses Diagramm aufliste und dasjenige auswähle, dessen Summe der Kantengewichte minimal ist, dann werde ich das Diagramm-B erhalten. So Graph-B ist der Minimum Spanning Tree (MST). Beachten Sie, dass das Gesamtgewicht 1 + 2 + 3 = 6 ist.
Wenn ich jetzt einen Spannbaum auswähle, dessen maximales Kantengewicht minimal ist (d. H. MBST), kann ich am Ende entweder Graph-B (oder) Graph-C aufheben. Beachten Sie, dass diese beiden aufspannenden Bäume ein maximales Kantengewicht 3 haben, das unter allen möglichen Spannbäumen das Minimum ist.
Aus dem Graph-B und Graph-C, ist klar, dass, obwohl das Graph-C ein MBST ist, es nicht MST ist. Weil sein Gesamtgewicht 1 + 3 + 3 = 7 ist, was größer ist als das Gesamtgewicht des MST, das in Kurve B (d. H. 6) gezeichnet ist.
Also MBST nicht unbedingt eine MST eines gegebenen Graphen sein. Aber die MST muss MBST sein.
Große Antwort. Ich habe Details zum Algorithmus in eine andere SO-Antwort geschrieben: http://stackoverflow.com/questions/14297409/what-isa-a-minimum-bottleeck-spanning-tree – ShitalShah
Sie meinen die Kantenlängen von {2,2,3}, die links und nicht rechts liegen? –
Natürlich nicht, wenn Sie die Gewichte ändern, haben Sie eine andere Grafik. Sehen Sie sich die EXISTIG-Figur an. Auf der rechten Seite der fettgedruckten MST befinden sich Kanten mit den Gewichten {2, 2, 3}. Lösche diese aus dem fettgedruckten Baum und ersetze sie durch die VORHANDENEN Kanten mit den Bezeichnungen 2, 3 und 6. Obwohl ich das Gefühl habe, dass du die Grundlagen vielleicht nicht verstehst ... – dan3
Oh ... Ich habe links und rechts gemischt, ich war ursprünglich Blick auf einen anderen Teilbaum. Fest. – dan3