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

15

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

— itamar
źródło

Byłoby miło być wyczekiwanym na taki algorytm, ale nie rozwiąże on obecnego problemu

— itamar

2

Wykres

będzie miał unikalne minimalne drzewo opinające wtedy i tylko wtedy, gdy (1) dla dowolnego podziału

na dwa podzbiory, minimalna krawędź wagi z jednym punktem końcowym w każdym podzbiorze jest unikalna i (2) maksymalna waga krawędź w dowolnym cyklu

jest wyjątkowa.

G

$G$

V (G)

$V(G)$

G

$G$

— Juho

Czy te pytania pierwsze i drugie już odpowiadają na twoje pytanie?

— Juho

Zobacz problem 23-1 w CLRS, aby znaleźć drugi najlepszy MST w

.

O (n^{2})

$O(n^2)$

— Kaveh

7

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 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\cdot|V|)$ $N$

— Luke Mathieson
źródło

W tej sytuacji chcielibyśmy wcześniej przerwać działanie algorytmu, gdy wiemy, że istnieje więcej niż

rozwiązań. Czy algorytm na to pozwala?

k

$k$

— Raphael

1

@ Rafael, nie miałem czasu naprawdę się z tym uporać (tak, oznaczenie przydziału), ale z mojego szorstkiego zrozumienia powinno być to możliwe - zaczyna się od jakiegoś MST, a następnie generuje kolejne.

— Luke Mathieson

1

@SaeedAmiri: „Liczba takich drzew opinających ” oznacza „liczbę drzew minimalnych ”, a nie „liczbę drzew opinających”. Jeśli wszystkie

drzew rozpinających są drzewami minimalnymi, wówczas wykres wejściowy jest kompletny, a wszystkie krawędzie mają jednakową wagę.

n^{n - 2}

$n^{n-2}$

— JeffE

1

O (| V |)

$O(|V|)$

1

Po szybkim odczycie algorytm ważony generuje drzewa w kolejności rosnącej masy (oczywiście zaczynając od MST). Tak powinno być dla celów PO.

— Luke Mathieson

2

Można pokazać, że algorytm Kruskala może znaleźć każde minimalne drzewo rozpinające; patrz tutaj .

~~$k$ $k$~~

— Raphael
źródło

5

k

$k$

k

$k$

K_{1, 5}

$K_{1,5}$

@vonbrand Dobry punkt. Oczywiście możemy kontynuować, aby zakończyć wszystkie gałęzie obliczeń, ale wtedy środowisko wykonawcze zależy od liczby drzew opinających, które mogą być wykładnicze.

— Raphael

1

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

— vonbrand
źródło

0

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.

— Carlos A. Prolo
źródło

Wydaje się, że twierdzisz, że możesz przetwarzać cały klaster w stałym czasie, ale nie widzę żadnej oczywistej stałej związanej z rozmiarem klastra. Czy możesz podać więcej szczegółów na temat tego etapu?

— David Richerby,