Mosty i punkty artykulacji

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

W poszukiwaniu mostów

W tym rozdziale bajeczka o Bajtowie kończy się. Pora zająć się analizą problemu, któremu poświęcona jest pierwsza połowa tego artykułu. Nasze zadanie można sformułować w następujący sposób:

Należy skonstruować algorytm, który dla podanego grafu nieskierowanego w krótkim czasie wyszuka w nim wszystkie mosty.

Można spytać: dlaczego potrzebny jest nam taki algorytm? Odpowiedź jest prosta: żeby można było szybko wyszukiwać mosty dla dowolnie skomplikowanego grafu. W niektórych przypadkach znalezienie wszystkich mostów nie zajmie nawet minuty:

Na rysunku powyżej mosty zostały oznaczone na czerwono. Wyszukiwanie mostów w grafach o takim rozmiarze przypomina dziecinną zabawę. Jednak najczęściej graf wejściowy będzie znacznie większy i nie dość, że trudno będzie odnaleźć choć jeden most, to nie do końca będzie pewne, czy graf w ogóle takowe posiada.

Rozpoczynamy analizę. Na początek dobrze jest wyodrębnić te krawędzie, które na pewno nie mogą być mostami. Po krótkim namyśle zapisujemy prostą obserwację:

Krawędź $ e $ łącząca wierzchołki $ u $ i $ v $ nie może być mostem, jeśli po usunięciu $ e $ z grafu nadal istnieje droga z $ u $ do $ v $ (inna niż przez $ e $).

Powyższe stwierdzenie jest bardzo prosto udowodnić. Skoro istnieje droga z $ u $ do $ v $ po usunięciu $ e $ oznacza to, że graf pozostał spójny, czyli krawędź $ e $ na pewno nie jest mostem.

Załóżmy, że nie usuwamy $ e $ z grafu. Wiedząc, że istnieje jakaś inna droga z $ u $ do $ v $ łatwo jest zauważyć, że $ e $ należy do cyklu prostego. Można by spytać: a co w takim razie z krawędziami nie należącymi do żadnego cyklu? Udowodnimy następujące twierdzenie:

Jeśli krawędź z grafu $ G $ nie leży na żadnym cyklu prostym, to jest ona mostem.

Przeprowadzimy dowód przez sprzeczność. Załóżmy, że krawędź $ \{u,v\} $ nie leży na żadnym cyklu prostym i nie jest ona mostem. Usuwamy krawędź $ \{u,v\} $ z grafu. Skoro $ \{u,v\} $ nie jest mostem, to znaczy, że wciąż istnieje droga łącząca $ u $ i $ v $: $ u – x_1 – x_2 – x_3 - .. – x_n – v $. A to oznacza, że $ u – v – x_1 – x_2 - ... – x_n – u $ tworzy cykl prosty. Sprzeczność z założeniem, że $ \{u,v\} $ nie leży na cyklu prostym. Krawędź $ \{u,v\} $ musi być mostem.

Spróbujmy teraz udowodnić powyższe twierdzenie „w drugą stronę”:

Jeśli krawędź z grafu $ G $ jest mostem, to nie leży ona na żadnym cyklu prostym.

Poprawność tego twierdzenia wynika z poprzednio udowodnionego faktu, że skoro krawędź leży na cyklu prostym, to nie może być mostem.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com