Kiedy minimalne drzewo rozpinające dla wykresu nie jest unikalne

22

Biorąc pod uwagę ważony, niekierowany wykres G: Które warunki muszą być spełnione, aby istniało wiele drzew minimalnych obejmujących G?

Wiem, że MST jest wyjątkowy, gdy wszystkie wagi są różne, ale nie można odwrócić tego stwierdzenia. Jeśli na wykresie jest wiele krawędzi o tej samej masie, może istnieć wiele MST, ale może być też tylko jedna:

wprowadź opis zdjęcia tutaj

W tym przykładzie wykres po lewej stronie ma unikalny MST, ale prawy nie.

Najbliżej mogłem znaleźć warunki dla niejednorodności MST:

Uwzględnij wszystkie cykle bez cięciwy (cykle, które nie zawierają innych cykli) na wykresie G. Jeśli w którymkolwiek z tych cykli maksymalna ważona krawędź istnieje wiele razy, wówczas wykres nie ma unikalnego drzewa obejmującego minimum.

Miałem pomysł, że w przypadku takiego cyklu

wprowadź opis zdjęcia tutaj

n wierzchołkami pozwala pominąć dokładnie jedną krawędź i nadal mieć połączone wszystkie wierzchołki. Dlatego masz wiele możliwości usunięcia krawędzi o najwyższej wadze, aby uzyskać MST, więc MST nie jest unikalny.

Potem jednak wpadłem na ten przykład:

wprowadź opis zdjęcia tutaj

Widać, że ten wykres ma cykl, który pasuje do mojego warunku: (E, F, G, H), ale o ile widzę, minimalne drzewo opinające jest unikalne:

wprowadź opis zdjęcia tutaj

Wygląda więc na to, że mój stan jest nieprawidłowy (a może po prostu nie do końca poprawny). Byłbym wdzięczny za wszelką pomoc w znalezieniu niezbędnych i wystarczających warunków dla wyjątkowości minimalnego drzewa opinającego.

Keiwan
źródło
1
Twoje najmniejsze cykle są znane jako cykle bezsznurowe (mniej więcej).
Yuval Filmus,

Odpowiedzi:

10

na pierwszym zdjęciu: prawy wykres ma unikalny MST, biorąc krawędzie i ( F , G ) o łącznej wadze 2.(F,H)(F,G)

Biorąc pod uwagę krzywą i niech M = ( V , M ) wynosi co najmniej drzewo rozpinające (MST), w G .G=(V,E)M=(V,F)G

Jeśli istnieje krawędź z wagą w ( e ) = m tak, że dodanie e do naszego MST daje cykl C , a niech m będzie również najniższą wagą krawędzi od F C , wtedy można utworzyć drugi MST przez wymianę krawędzi z F C z krawędzi masy m w e . Dlatego nie mamy wyjątkowości.e={v,w}EFw(e)=meCmFCFCme

dtt
źródło
Masz rację, poprawiłem teraz ten wykres w pytaniu. Czy wiesz, czy jest to najbardziej ogólny warunek, aby MST nie był unikalny? Czy też można to jakoś ustalić bez konieczności znalezienia MST?
Keiwan
1
@Keiwan Uważam, że jeśli weźmiesz pod uwagę to pytanie, warunek przedstawiony w tej odpowiedzi jest również warunkiem koniecznym posiadania wielu MST. Innymi słowy: wykres ma wiele MST, jeśli i tylko wtedy, gdy można wykonać konstrukcję opisaną przez HueHang. G
Bakuriu,
1
m nie musi być najniższą masą krawędzi od F∩C. W rzeczywistości może to być tylko najwyższa waga krawędzi, w przeciwnym razie M nie byłby w ogóle minimalny. Załóżmy, że w F∩C istniała krawędź e 'z w (e') = m '> m = w (e). Następnie zamiana e na e 'pozostawiłaby drzewo opinające o masie całkowitej mniejszej niż M, co byłoby sprzeczne z minimalnością M.
Czad
2

Poprzednia odpowiedź wskazuje algorytm określający, czy istnieje wiele MST, które dla każdej krawędzi nie w G znajdują cykl utworzony przez dodanie e do wstępnie obliczonego MST i sprawdzają, czy e nie jest unikalną najcięższą krawędzią w tym cyklu. Algorytm najprawdopodobniej zadziała w czasie O ( | E | | V | ) .eGeeO(|E||V|)

Prostszy algorytm do określania, czy istnieje wiele MST G w złożoności czasowej O(|E|log(|V|)) .

 1. Uruchom algorytm Kruskala na aby znaleźć MST m .Gm

 2. Spróbuj uruchomić Algorytm Kruskala na ponownie. W tym biegu, ilekroć mamy wybór między krawędziami o równej wadze, najpierw spróbujemy krawędzi nie wm , a następnie spróbujemy krawędzi wm . Ilekroć znaleźliśmy krawędź nie w m, łączy dwa różne drzewa, twierdzimy, że istnieje wiele MST, kończących algorytm.Gmmm

 3. Jeśli tutaj dotarliśmy, twierdzimy, że ma unikalny MST.G

Zwykły przebieg algorytmu Kruskala zajmuje czas . Dodatkowego wyboru krawędzi innych niż wm można dokonać w czasie O ( | E | ) . Zatem algorytm osiąga złożoność czasową O ( | E | log ( | V | ) ) .O(|E|log(|V|))mO(|E|)O(|E|log(|V|))

Dlaczego ten algorytm może ustalić, czy istnieje wiele MST?

Załóżmy, że mamy MST który nie jest taki sam jak m . Wystarczy pokazać, że algorytm działający na G nie osiągnie kroku 3, ponieważ krawędź znaleziona na końcu kroku 2, która nie znajduje się w mi, a połączenie dwóch różnych drzew byłoby uwzględnione w wynikowym MST, gdybyśmy uruchomili Kruskala algorytm do zakończenia. Niech w będzie największą masą taką, że dla każdej krawędzi o wadze mniejszej niż w jest w m wtedy i tylko wtedy, gdy jest w m . Ponieważ m i m ' mają taką samą liczbę krawędzi masy w , istnieją krawędzie masymmGmwwmmmmw które są w m ′, ale nie w m . Jeśli algorytm zakończył działanie przed przetwarzaniem krawędzi tych krawędzi, jesteśmy skończeni. W przeciwnym razie załóżmy, że algorytm przetworzy teraz pierwszą krawędź e wśród tych krawędzi. Niech S będzie zbiorem wszystkich zachowanych do tej pory krawędzi, które zostaną uwzględnione w wynikowym MST. S m . Ponieważ algorytm nie zakończył przetwarzania krawędzi masy w nie w m, takiej jak e , nie mógł rozpocząć przetwarzania krawędzi masy w w m . Więc krawędzie w S.wmmeSSmwmewmSważą mniej niż . To znaczy S m . Przypomnij sobie, że e jest w m . Ponieważ { e } S m , gdzie m jest drzewem, e musi połączyć dwa różne drzewa w S, a algorytm kończy się w tym momencie.wSm.em{e}SmmeS

Uwaga na temat dalszego rozwoju
Krok 1 i krok 2 mogą być przeplatane, dzięki czemu możemy zakończyć algorytm tak szybko, jak to możliwe, bez przetwarzania krawędzi o większych wagach.
Jeśli chcesz obliczyć liczbę MST, możesz sprawdzić odpowiedź na to, jak obliczyć liczbę MST .

Apass.Jack
źródło
1

Niech będzie (nieskończonym) połączonym wykresem nieważonym o prostych krawędziach z co najmniej dwoma wierzchołkami. Niech ST oznacza drzewo rozpinające, a MST oznacza minimalne drzewo rozpinające. Pozwól mi najpierw zdefiniować niektóre mniej popularne terminy.G

  • Krawędź jest najcięższa w cyklu, jeśli jest unikalną najcięższą krawędzią w jakimś cyklu.
  • Krawędź nie jest najcięższa, jeśli nigdy nie jest najcięższą krawędzią w żadnym cyklu.
  • Krawędź jest wyjątkowo najcięższa, jeśli jest to najlżejsza krawędź do przecięcia.
  • Krawędź nie jest najlżejsza, jeśli nigdy nie jest najlżejszą krawędzią do przecięcia jakiegokolwiek cięcia.
  • Dwa ST sąsiadują ze sobą, jeśli każdy ST ma dokładnie jedną krawędź, która nie znajduje się w drugim ST.
  • MST jest izolowanym MST, jeśli nie sąsiaduje z innym MST (gdy oba MST są uważane za ST).

Kiedy jest więcej niż jedno minimalne drzewo opinające?

G

  • Istnieją dwa sąsiednie MST.
  • Nie ma izolowanego MST.
  • Istnieje ST, który jest tak lekki lub jaśniejszy niż wszystkie sąsiednie ST i który jest tak lekki jak jeden sąsiedni ST.
  • Istnieje krawędź, która nie jest ani najcięższa jak i najcięższa w cyklu.
  • Istnieje krawędź, która nie jest ani najlżejsza, ani najlżejsza

Nowością tej odpowiedzi są głównie dwie ostatnie charakterystyki. Drugą z ostatnich cech można uznać za kolejny krok w podejściu PO . Pierwsze trzy charakterystyki razem można uznać za nieco ulepszoną wersję odpowiedzi dtt .

G

Kiedy unikalne są minimalne drzewa rozpinające?

G

  • Wyjątkowość MST : Istnieje unikalny MST.
  • Brak sąsiadujących MST : nie ma sąsiadujących MST.
  • Jeden izolowany MST : istnieje izolowany MST.
  • Jeden lokalny minimalny ST : istnieje ST, który jest lżejszy niż wszystkie sąsiednie ST.
  • Ekstremalna krawędź cyklu : każda krawędź jest albo najcięższa w cyklu albo najcięższa w cyklu.
  • Ekstremalnie cięta krawędź : każda krawędź jest albo najlżejsza, albo najlżejsza

Oto mój dowód.

„Unikalność MST” => „Brak sąsiadujących MST”: oczywiste.

„Brak sąsiadujących MST” => „Jeden izolowany MST”: oczywisty.

„Jeden izolowany MST” => „Jeden lokalny minimalny ST”: Izolowany MST jest lżejszy niż wszystkie sąsiednie ST.

m

  • mlmllclmmm1m2m1m2lcm1m2lmm1m2lGmmmmlll
  • mhmhmchchmmhhmmmmhhhch

„Lokalny minimalny ST” => „Ekstremalna krawędź cięcia”: Dowód pozostaje jako ćwiczenie.

meememm

„Extreme cut edge” => „Wyjątkowość MST”: Dowód pozostaje jako ćwiczenie.

Powyższe łańcuchy implikacji dowodzą twierdzenia.

Po raz kolejny nowością w tych odpowiedziach jest przede wszystkim właściwość „ekstremalnego ostrza cyklu” i właściwość „ekstremalnej krawędzi cięcia”, która wykorzystuje koncepcje: nie obciążająca cyklu i najcięższa. Nie widziałem tych koncepcji gdzie indziej, chociaż są one całkiem naturalne.


Oto dwie powiązane interesujące obserwacje.

  • ee e e
  • ee e e

Dwa wystarczające, ale niekonieczne warunki dla unikalnego MST

ab1,bc1,cd1,da2,ac2

1,1,2

Apass.Jack
źródło