Wykres ma dwa/trzy różne minimalne drzewa opinające?

Question

Próbuję znaleźć skuteczną metodę wykrywania, czy dany wykres G ma dwa różne minimalne drzewa opinające. Próbuję również znaleźć metodę sprawdzania, czy ma 3 różne minimalne drzewa opinające. Naiwne rozwiązanie, o którym mi chodzi, działa tylko na algorytmie Kruskala i znajduje całkowitą wagę minimalnego drzewa opinającego. Później, usuwając krawędź z wykresu i ponownie uruchamiając algorytm Kruskala i sprawdzając, czy ciężar nowego drzewa jest wagą oryginalnego minimalnego drzewa opinającego, a więc dla każdej krawędzi na wykresie. Środowisko wykonawcze to O (| V || E | log | V |), co wcale nie jest dobre i myślę, że jest lepszy sposób na zrobienie tego.

Wszelkie sugestie byłoby pomocne, góry dzięki

Answer 1

Załóżmy, że masz MST T0 wykresu. Teraz, jeśli możemy uzyskać inny MST T1, musi on mieć co najmniej jedną krawędź E inną niż oryginalna MST. Wyrzuć E z T1, teraz wykres jest podzielony na dwa składniki. Jednak w T0, te dwa komponenty muszą być połączone, więc będzie druga krawędź w tych dwóch komponentach, która ma dokładnie taką samą wagę jak E (lub możemy zastąpić tą drugą wagą drugą i uzyskać mniejszą ST) . Oznacza to, że zastąpienie tej drugiej krawędzi za pomocą E da ci inny MST.

To sugeruje, że jeśli istnieje więcej niż jeden MST, zawsze możemy zmienić tylko jedną krawędź z MST i uzyskać kolejny MST. Jeśli więc sprawdzasz każdą krawędź, spróbuj zastąpić krawędź tymi, które mają taką samą wagę, a jeśli uzyskasz kolejny ST, to jest to MST, otrzymasz szybszy algorytm.

Answer 2

Możesz zmodyfikować algorytm Kruskala, aby to zrobić.

Najpierw sortuj krawędzie według wagi. Następnie, dla każdej masy w porządku rosnącym, odfiltruj wszystkie nieistotne krawędzie. Odpowiednie krawędzie tworzą wykres na połączonych elementach dotychczasowego minimum lasu rozpiętości. Liczbę drzew opinających można policzyć na tym wykresie. Przenieś produkt na wszystkie masy i policzyłeś całkowitą liczbę minimalnych drzew opinających na wykresie.

Odzyskujesz ten sam czas działania, co algorytm Kruskala, jeśli zależy Ci tylko na przypadkach jedno drzewo, dwa drzewa i trzy lub więcej drzew. Sądzę, że kończysz wykonywanie kalkulacji determinującej lub coś w rodzaju wyliczenia ogólnie drzew, więc prawdopodobnie skończysz z najgorszym przypadkiem O (MM (n)).

Answer 3

Załóżmy, że G jest wykresem zawierającym n wierzchołków i m krawędzi; ciężar każdej krawędzi e to W (e); i że P to drzewo o minimalnej masie na G, ważące koszt (W, P).

Niech δ = minimalna dodatnia różnica między dowolnymi dwoma obciążeniami krawędzi. (Jeśli wszystkie grubości krawędzi są takie same, to δ jest nieokreślone, ale w tym przypadku każdy ST jest MST, więc nie ma to znaczenia). Weź ε takie, że δ> n · ε> 0.

Utwórz nowa funkcja wagowa U() z U (e) = W (e) + ε, gdy e jest w P, w przeciwnym razie U (e) = W (e). Oblicz Q, MST G w U. Jeśli Koszt (U, Q) < Koszt (U, P), a następnie Q ≠ P. Ale Koszt (W, Q) = Koszt (W, P) przez konstrukcję δ i ε. Stąd P i Q są odrębnymi MST G w W. Jeżeli Koszt (U, Q) ≥ Koszt (U, P), to Q = P i odrębne MST G w W nie istnieją.

Powyższy sposób określa czy istnieją co najmniej dwie różne MSTS w czasie O (H (n, m)), jeżeli O (h (n, m)) ograniczającą czasu znalezienia MST G.

Nie wiem, czy podobna metoda może leczyć, czy istnieją trzy (lub więcej) odrębne MST; proste przedłużenia sprowadzają się do prostych kontrprzykładów.