Mosty i punkty artykulacji

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

W poszukiwaniu punktów artykulacji

Podobieństwo między punktem artykulacji i mostem nie leży jedynie w definicji. Sposób znajdowania obu tych obiektów jest również bardzo podobny. Pierwsze dwa kroki algorytmu szukania punktów artykulacji jest taki sam jak przy wyznaczaniu mostów: wykonujemy procedurę DFS, a następnie wyliczamy funkcję $ low $ dla wszystkich wierzchołków. Inny natomiast jest krok trzeci, ale nie ma czym się martwić, gdyż jest on tak samo prosty jak przy szukaniu mostów.

Zanim jednak podane zostanie rozwiązanie problemu wyszukiwania punktów artykulacji, przeprowadzimy dowody dwóch poniższych twierdzeń:

A. Korzeń drzewa przeszukiwania w głąb jest punktem artykulacji wtedy i tylko wtedy, gdy posiada on conajmniej dwóch synów.

B. Wierzchołek $ v $ nie będący korzeniem drzewa DFS jest punktem artykulacji wtedy i tylko wtedy, gdy przynajmniej dla jednego jego syna nie istnieje krawędź wtórna $ \{u,w\} $, taka że wierzchołek $ u $ jest potomkiem $ v $ i $ w $ jest przodkiem $ v $.

Zrozumienie dowodów tych twierdzeń nie jest wymagane, gdy zależy nam tylko na poznaniu gotowego algorytmu. Mimo wszystko gorąco zachęcam do przestudiowania następnych kilku akapitów.

Dowód twierdzenia A.

Najpierw udowodnimy implikację w prawo. Skorzystamy z prawa kontrapozycji i udowodnimy, że jeśli korzeń $ r $ drzewa DFS ma mniej niż dwóch synów, to nie może być punktem artykulacji. Jeśli $ r $ jest korzeniem i nie ma dzieci, to nie posiada żadnych krawędzi z niego wychodzących. Po usunięciu wierzchołka $ r $ nie zmieni się liczba spójnych składowych, więc $ r $ nie jest punktem artykulacji. Gdy $ r $ posiada tylko jednego syna, to każdy inny wierzchołek w drzewie DFS jest osiągalny poprzez tego syna. Czyli usunięcie $ r $ nie zmieni liczby spójnych składowych, więc $ r $ nie jest punktem artykulacji.

Implikację w lewą stronę udowodnimy przez sprzeczność. Załóżmy, że korzeń $ r $ ma dwóch synów $ w_1 $ i $ w_2 $ oraz $ r $ nie jest punktem artykulacji. Bez straty ogólności załóżmy, że $ w_1 $ było odwiedzone wcześniej niż $ w_2 $ podczas działania procedury DFS. Skoro $ r $ nie jest punktem artykulacji, to istnieje droga pomiędzy $ w_1 $ i $ w_2 $, która nie przechodzi przez $ r $. Do wierzchołka $ w_1 $ weszliśmy wcześniej, więc ta droga powinna zostać odwiedzona i $ w_2 $ powinien być synem jakiegoś potomka $ w_1 $. Ale skoro $ w_1 $ i $ w_2 $ leżą na dwóch różnych poddrzewach korzenia $ r $, to wiemy, że nie może istnieć inna droga pomiędzy tymi wierzchołkami. Dochodzimy do sprzeczności. Wierzchołek $ r $ musi być zatem punktem artykulacji.

Dowód twierdzenia B.

Dowód implikacji w prawo. Załóżmy, że $ v $ jest punktem artykulacji w grafie $ G $. Niech $ C_1 $ będzie spójną częścią grafu $ G $ zawierającą korzeń $ r $ drzewa DFS. Niech $ s $ będzie sąsiadem $ v $ nie należącym do $ C_1 $ i niech $ C_2 $ będzie spójną częścią grafu $ G $ zawierającą $ s $ (taki sąsiad istnieje, bo usunięcie $ v $ musi utworzyć przynajmniej dwie spójne składowe). W drzewie DFS wszyscy przodkowie $ v $ znajdują się w $ C_1 $ a wszyscy potomkowie $ s $ są w $ C_2 $. Więc nie może istnieć żadna krawędź pomiędzy potomkami $ s $ a przodkami $ v $.

Dowód w lewo. Jeśli nie ma krawędzi wtórnej z wierzchołka $ s $ i żadnego jego potomka do któregokolwiek przodka $ v $, to wiemy, że jedyna ścieżka z korzenia $ r $ do $ s $ wiedzie przez $ v $. Więc gdy usuniemy $ v $, graf rozspójni się. Czyli $ v $ jest punktem artykulacji.

Algorytm wyszukiwania punktów artykulacji

Oto upragnione rozwiązanie:

  • wykonujemy procedurę DFS
  • wyliczamy funkcję $ low $ dla każdego wierzchołka (tak, jak podczas szukania mostów)
  • wyznaczamy punkty artykulacji w dwóch krokach:
    • sprawdzamy czy korzeń drzewa DFS posiada przynajmniej dwóch synów. Jeśli tak, to znaleźliśmy jeden z punktów artykulacji (Twierdzenie A).
    • sprawdzamy wszystkie inne wierzchołki. Jeśli jakiś wierzchołek $ v $ posiada syna $ s $ w drzewie DFS, takiego że $ low[s] \ge d[v] $, wtedy $ s $ nie posiada krawędzi wtórnej do żadnego z przodków $ v $, w takim razie $ v $ jest punktem artykulacji (Twierdzenie B).

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com