Minimalne wąskie gardło obejmujące drzewo ważonego wykresu G to drzewo opinające z G, które minimalizuje maksymalną masę krawędzi w drzewie opinającym. MBST niekoniecznie jest MST (minimalne drzewo opinające).W jaki sposób minimalne drzewo obejmujące wąskie gardło różni się od minimalnego drzewa opinającego?
Podaj przykład, gdzie te stwierdzenia mają sens.
spojrzenie na MST example on Wikipedia dokumencie:
wąskim gardłem w drzewa rozpinającego jest krawędź maksymalnej wagi w tym drzewie. W drzewie opinającym może występować kilka wąskich gardeł (o tej samej wadze). W Wikipedii MST są dwa wąskie gardła o wadze 8.
Teraz, weźcie minimalne drzewo opinające danego wykresu (może być kilka MSTów, wszystkie o tej samej łącznej wadze krawędzi oczywiście) i zadzwońcie do maksymalnej wagi krawędzi B. W naszym przykładzie B = 8.
Dowolne drzewo opinające, które również ma wąskie gardło B = 8, to MBST. Ale nie może to być MST (ponieważ całkowita waga krawędzi jest większa niż najlepsza z możliwych).
więc wziąć Wikipedii MST i modyfikować (dodawać/usuwać niektóre krawędzie), tak że
na przykład zmiany tylko sub-tree "po lewej stronie" w Wikipedia MST (składający się z ciężarków {2, 2, 3}) do {2, 3, 6}, zwiększając całkowitą wagę krawędzi o 4 bez zmieniając wąskie gardło 8. Bingo, utworzyłeś MBST, który nie jest MST.
Zanim odpowiemy na to pytanie, pozwól mi określić niektóre z warunków, które są tutaj używane ...
1) Spanning Tree: Spanning Tree danego wykresu jest drzewem, które obejmuje wszystkie wierzchołki tego grafu.
2) Minimalne drzewo opinające (MST): MST danego wykresu to drzewo opinające, którego długość jest minimalna spośród wszystkich możliwych drzew opinających na tym wykresie. Bardziej wyraźnie, dla danego wykresu, wylistuj wszystkie możliwe drzewa opinające (które mogą być bardzo duże) i wybierz ten, którego suma grubości krawędzi jest minimalna.
3) Minimalne drzewo napinania wąskiego gardła (MBST): MBST danego wykresu to drzewo opinające, którego maksymalny ciężar krawędziowy jest minimalny wśród wszystkich możliwych drzew opinających. Bardziej wyraźnie, dla danego wykresu, wymień wszystkie możliwe drzewa opinające i maksymalną wagę krawędzi dla każdego z drzew opinających. Wśród nich wybierz drzewo opinające, którego maksymalna waga krawędzi jest minimalna.
Teraz spójrzmy na poniższym rysunku z wykresu czterech węzłów ...
Graph-A jest dana oryginalny wykres. Jeśli podam listę wszystkich możliwych drzew opinających dla tego wykresu i wybiorę ten, którego suma grubości krawędzi jest minimalna, otrzymam wykres-B. Zatem Graph-B jest drzewem minimalnym opinającym (MST). Należy pamiętać, że jego całkowita waga wynosi 1 + 2 + 3 = 6.
Teraz, jeśli wybiorę drzewo opinające, którego maksymalna waga krawędziowa jest minimalna (tj. MBST), to może dojść do pobrania wykresu B (lub) wykresu-C. Zwróć uwagę, że oba te drzewa opinające mają maksymalną wagę krawędzi 3, która jest minimalna wśród wszystkich możliwych drzew opinających.
Z wykresu-B i wykresu-C wynika jasno, że nawet jeśli wykres-C to MBST, to nie jest to MST. Ponieważ jego całkowita waga wynosi 1 + 3 + 3 = 7, czyli jest większa niż całkowita waga MST narysowana na wykresie B (tj. 6).
Więc MBST niekoniecznie musi być MST danego wykresu. Ale MST musi być MBST.
Świetna odpowiedź. Umieściłem szczegóły na temat algorytmu w innej odpowiedzi SO: http://stackoverflow.com/questions/14297409/what-is-a-minimum-bottleneck-spanning-tree – ShitalShah
masz na myśli edytowanie długości krawędzi {2,2,3}, które są po lewej, a nie po prawej? –
Oczywiście nie, jeśli ZMIENIASZ ciężary, masz inny wykres. Spójrz na rysunek EXISTIG, są krawędzie o masach {2, 2, 3} po prawej stronie pogrubionego MST. Usuń je z pogrubionego drzewa i zastąp je krawędziami EXISTING oznaczonymi 2, 3 i 6. Chociaż mam przeczucie, że możesz nie zrozumieć podstaw ... – dan3
Och ... Pomieszałem w lewo i prawo, Pierwotnie patrząc na inne poddrzewo. Naprawiony. – dan3