Sprawdź, czy minimalne drzewo opinające zawiera krawędź w czasie liniowym?

Question

I mają następujące problemy w pracy domowej:

Podać O (n + m) algorytm zauważyć, że, czy krawędzi E byłyby częścią MST wykresu

(Możemy uzyskać pomoc od innych osób na tym zleceniu, więc to nie jest oszustwo.)

Myślę, że mógłbym zrobić BFS i dowiedzieć się, czy ta krawędź jest krawędzią między dwiema warstwami, a jeśli tak, czy ta krawędź była najmniejszy na tych warstwach. Ale co mogę powiedzieć, gdy ta krawędź nie jest krawędzią drzewa BFS?

Answer 1

Jako wskazówka, jeśli krawędź nie jest najcięższą krawędzią w każdym cyklu, który ją zawiera, istnieje pewien MST, który zawiera tę krawędź. Aby to zobaczyć, rozważ dowolny MST. Jeśli MST już zawiera krawędź, świetnie! Skończyliśmy. Jeśli nie, dodaj krawędź do MST. Tworzy to cykl na wykresie. Teraz znajdź najcięższą krawędź w tym cyklu i usuń ją z wykresu. Wszystko jest teraz w dalszym ciągu połączone (ponieważ jeśli dwa węzły były połączone ścieżką, która przechodziła przez tę krawędź, teraz można je połączyć, po prostu przechodząc dookoła cyklu w drugą stronę). Ponadto, ponieważ koszt krawędzi został usunięty nie był mniejszy niż koszt danej krawędzi (ponieważ krawędź nie jest najcięższą krawędzią w cyklu), koszt tego drzewa nie może być większy niż przed. Ponieważ zaczęliśmy od MST, musimy zatem zakończyć z MST.

Używając tej właściwości, sprawdź, czy krawędź jest najcięższą krawędzią w dowolnym cyklu w czasie liniowym.

Answer 2

Znajdź, czy istnieją ścieżki, które są tańsze niż aktualny (u, v), który tworzy cykl dla u i v. Jeśli tak, to (u, v) nie znajduje się na mst. W przeciwnym razie jest. Można to udowodnić za pomocą właściwości cut i właściwości cycle.

Answer 3

Rozwiążemy to za pomocą MST cycle property, który mówi, że "dla dowolnego cyklu C na wykresie, jeżeli waga krawędzi e C jest większa niż waga wszystkich innych krawędzi C, to ta krawędź nie może należeć do MST. "

Teraz uruchom następujący algorytm: O(E+V), aby sprawdzić, czy krawędź E łącząca wierzchołki u i v będzie częścią jakiegoś MST, czy nie.

Etap 1

Run DF z jednym z punktów końcowych (albo U lub V) krawędzi E rozważa tylko te krawędzie, które mają mniejszą masę niż E.

krok 2

Przypadek 1 Jeżeli na końcu tego DFS wierzchołków uiv połączenia się, a następnie krawędź E nie może być częścią niektórych MST. Wynika to z tego, że w tym przypadku istnieje zdecydowanie wykres na wykresie, którego krawędź E ma maksymalną masę i nie może być częścią MST (z właściwości cyklu).

Przypadek 2 Ale jeśli na koniec DFS u i v zostać odłączony, a następnie krawędź E musi być częścią jakiegoś MST jak w tym przypadku E nie zawsze jest maksymalna krawędź waga wszystkich cykli jest częścią.