Mosty i punkty artykulacji

02.10.2010 - Michał Karpiński
TrudnośćTrudność

W poszukiwaniu mostów cd.

Zbierając do kupy wszystkie nasze rozważania z poprzedniej strony można wywnioskować, że poniższe zdanie jest prawdziwe:

Krawędź z grafu $ G $ jest mostem wtedy i tylko wtedy, gdy nie leży na żadnym cyklu prostym w grafie $ G $.

Więcej informacji na temat przeszukiwania w głąb znajdziesz w tym artykule

To twierdzenie w znaczący sposób ułatwi nam konstruowanie algorytmu, ponieważ problem znajdowania mostów sprowadza się do problemu znajdowania cykli w grafie nieskierowanym. W takim razie wejściowy graf należy przeszukiwać w głąb.

Przeszukujemy graf metodą DFS. Na pewno każdy się zgodzi, że jeśli w grafie istnieją jakiekolwiek mosty, to należą one do lasu przeszukiwania w głąb. Jest tak dlatego, że wszystkie krawędzie nie należące do żadnego drzewa przeszukiwania w głąb są krawędziami wtórnymi: czyli po dodaniu ich do któregoś z drzew utworzyłyby cykl, a przecież z powyższego twierdzenia wiemy, że żaden most nie leży na cyklu.

Mówiąc wprost: rozpatrujemy tylko krawędzie, przez które przechodziliśmy podczas przeszukiwania grafu metodą DFS.

Funkcja „Low”

Większość krawędzi należących do lasu przeszukiwania w głąb raczej nie ma szans być mostami (przykładem jest powyższy rysunek, gdzie tylko jedna krawędź jest mostem). Żeby wyodrębnić poszukiwane przez nas krawędzie wprowadzimy dodatkowy atrybut dla każdego wierzchołka. Atrybut ten nazwiemy $ low $ (czyt. loł), czyli "niski".

Poniższy fragment może wydawać się z początku trudny - nie zniechęcaj się jednak - po paru akapitach wszystko stanie się jaśniejsze.

$ low[v] $ obliczamy zaczynając od liści drzewa przeszukiwania w głąb (idąc aż do korzenia) w następujący sposób:

Przypominamy, że $ d[v] $ jest to czas odwiedzenia wierzchołka $ v $ podczas przeszukiwania grafu w głąb

Na pierwszy rzut oka podany wzór wydaje się być skomplikowany. Powstaje pytanie: po co w ogóle stosujemy tego typu udziwnienia? Okazuje się, że wcale nie komplikujemy sobie zadania, a po wyliczeniu $ low[v] $ dla każdego $ v $ w łatwy sposób będziemy mogli stwierdzić, które krawędzie są mostami.

Zamiast tłumaczyć słownie (co byłoby nudne i niezrozumiałe), pozwolę sobie przedstawić działanie i znaczenie atrybutu $ low $ na prostym przykładzie. Weźmy graf z rysunku powyżej. Oznaczmy w nim drzewo przeszukiwania w głąb, krawędzie wtórne oraz atrybut $ d $ (czas odwiedzenia) dla każdego wierzchołka (patrz rysunek obok). Obliczamy atrybut $ low $:

Atrybut $ low $ został wyliczony dla wszystkich wierzchołków. Nie łatwo jest wpaść na to, po co właściwie robiliśmy wszystkie te obliczenia, dlatego od razu podam wzór na wyciągniecie z grafu wszystkich mostów:

Dla każdego $ v $ należącego do $ G $: jeśli $ d[v] = low[v] $, to krawędź $ \{p[v],v\} $ jest mostem. (gdzie $ p[v] $ jest poprzednikiem wierzchołka $ v $ w drzewie przeszukiwania w głąb)

Spójrzmy na graf z naszego przykładu. Faktycznie jeden koniec mostu znajduje się w wierzchołku, który ma $ d[v] = low[v] $. Zauważmy, że korzeń również spełnia tą zależność, ale nie posiada on poprzednika, dlatego nie może być częścią mostu.

4.636365
Twoja ocena: Brak Ocena: 4.6 (11 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com