Próbuję znaleźć skuteczną metodę wykrywania, czy dany wykres G ma dwa różne minimalne drzewa rozpinające. Próbuję również znaleźć metodę, aby sprawdzić, czy ma 3 różne minimalne drzewa rozpinające. Naiwnym rozwiązaniem, o którym myślałem, jest jednorazowe uruchomienie algorytmu Kruskala i znalezienie całkowitej masy 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 ciężarem 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, aby to zrobić.
Wszelkie sugestie byłyby pomocne, z góry dzięki
Odpowiedzi:
Kapoor i Ramesh ( odpowiednia wersja SIAM J. Comput. , Darmowa (?) Osobista wersja strony internetowej ) dają algorytm do wyliczania wszystkich drzew minimalnych obejmujących zarówno wykresy ważone, jak i nieważone.
Rozumiem podstawową ideę, że zaczynasz od jednego MST, a następnie zamieniasz krawędzie leżące wzdłuż cykli na wykresie (tak długo, jak ciężary są w porządku, zamieniasz jedną krawędź na drugą, o której wiesz, że ponownie połączy drzewo) .
W przypadku ważonym dają czas pracy do wyszczególnienia wszystkich minimalnych drzew opinających gdzie N jest liczbą takich drzew opinających. Wylicza je w kolejności rosnącej wagi, a moje obecne (pobieżne) rozumienie sugeruje, że całkowicie wykonalne jest zakończenie algorytmu po wygenerowaniu określonej liczby drzew (ponieważ zaczyna się od MST i tworzy je sekwencyjnie).O ( N⋅ | V.| ) N.
źródło
Można pokazać, że algorytm Kruskala może znaleźć każde minimalne drzewo rozpinające; patrz tutaj .
źródło
Aby sprawdzić, czy istnieje więcej niż jeden MST, rozważ np. Algorytm Kruskala. Jedynym sposobem, w jaki mógłby konstruować różne MST, jest pominięcie krawędzi i wybranie innego, gdy jest ich kilka o tej samej wadze. Ale te krawędzie o tej samej masie mogły zostać wykluczone, ponieważ tworzyły cykl z jaśniejszymi krawędziami ...
Powinieneś więc uruchomić algorytm Kruskala, a jeśli jest kilka krawędzi o tej samej wadze do rozważenia, dodaj wszystkie, które można dodać bez tworzenia cykli. Jeśli pozostała krawędź tego ciężaru i nie zamyka ona cyklu z żadną krawędzią o niższych obciążnikach (które były wcześniej dodawane), istnieje więcej niż jeden MST. Sprawdzenie, czy są dokładnie 2, 3 lub więcej itd., Wygląda na znacznie trudniejsze ...
źródło
Algorytm Modidying Kruskala: Przy zamawianiu krawędzi klastuj krawędzie o równej wadze. Teraz, w miejscu, w którym przetwarzasz krawędzie w kolejności, za każdym razem, gdy dotrzesz do nowego klastra, najpierw sprawdź wszystkie krawędzie osobno i usuń z klastra te, które zamknęłyby cykl, biorąc pod uwagę to, co zostało zbudowane przed klastrem. Następnie uruchom wszystkie pozostałe krawędzie w klastrze, próbując teraz dodać je do MST. Jeśli którykolwiek z nich zamyka cykl, to koniecznie było to spowodowane wstawieniem wcześniej innych krawędzi tego samego klastra, co oznacza, że masz więcej niż jeden MST.
To rozwiązanie zachowuje złożoność algorytmu Kruskala, tyle że zwiększa czas przetwarzania każdej krawędzi.
źródło