Kiedy minimalne drzewo rozpinające dla wykresu nie jest unikalne

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:

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

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:

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:

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.

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\}\in E \setminus F$$w(e)=m$$e$$C$$m$$F\cap C$$F\cap C$$m$$e$

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 | ) .$e$$G$$e$$e$$O(|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 .$G$$m$

$\ $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.$G$$m$$m$$m$

$\ $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|))$$m$$O(|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 masy$m'$$m$$G$$m$$w$$w$$m$$m'$$m$$m'$$w$ 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$w$$m'$$m$$e'$$S$$S\subset m$$w$$m$$e'$$w$$m$$S$ważą 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.$w$$S\subset m'.$$e'$$m'$$\{e'\}\cup S\subset m'$$m'$$e'$$S$

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 .

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$

• $m$$l$$m$$l$$l$$c$$l$$m$$m$$m_1$$m_2$$m_1$$m_2$$l$$c$$m_1$$m_2$$l'$$m'$$m_1$$m_2$$l'$$G$$m$$m'$$m$$m'$$l$$l'$$l$
• $m$$h'$$m$$h'$$m$$c$$h$$c$$h'$$m'$$m$$h$$h'$$m$$m'$$m$$m'$$h$$h'$$h'$$c$$h'$

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

$m$$e$$e$$m$$e$$m$$m$

„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.

• $e$$e$$\Leftrightarrow$ $e$$\Leftrightarrow$ $e$
• $e$$e$$\Leftrightarrow$ $e$$\Leftrightarrow$ $e$

Dwa wystarczające, ale niekonieczne warunki dla unikalnego MST

$ab\rightarrow 1, bc\rightarrow 1, cd\rightarrow 1, da\rightarrow 2, ac\rightarrow 2$

$1,1,2$