Mosty i punkty artykulacji

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

Dlaczego to działa?

Znów przeprowadzimy dowód przez sprzeczność. Sprawdźmy co by się stało, gdyby dla pewnego wierzchołka $ v $ w grafie $ G $ zachodziło $ d[v] = low[v] $ a krawędź $ e=\{p[v],v
\} $ nie byłaby mostem.

Skorzystamy z faktu, że dla każdego wierzchołka $ v $: $ d[v] > d[p[v]] $. Ta relacja zachodzi w oczywisty sposób. Budując drzewo przeszukiwania w głąb przypisujemy etykiety czasowe o większej wartości wierzchołkom, które odwiedzamy później.

Skoro $ e $ nie jest mostem, to należy do jakiegoś cyklu prostego. Innymi słowy: istnieje inna droga prowadząca do $ p[v] $ nie przechodząca przez $ e $. Oznacza to, że istnieje krawędź wtórna, która albo jest bezpośrednio połączona z $ p[v] $, albo łączy się z którymś z przodków wierzchołka $ p[v] $ (nazwijmy go $ w $).

W takim razie, gdy obliczamy funkcję $ low $ i dochodzimy do wierzchołka $ v $, to $ low[v] \le d[p[v]] $ – wynika to z powyższego faktu. Czyli $ low[v] \neq d[v] $. Doszliśmy do sprzeczności.

Żeby oswoić się z nowo zdobytą wiedzą, prześledźmy jeszcze jeden przykład wyszukiwania mostów w postaci prostej animacji:

Na koniec przedstawimy wszystkie kroki algorytmu wyszukiwania mostów:

  • Wykonujemy procedurę DFS

  • Dla każdego wierzchołka $ v $ wyliczamy $ low[v] $ na podstawie wzoru z poprzedniej strony. Zaczynamy od liści drzewa przeszukiwania w głąb przechodząc w górę aż do korzenia

  • Przeglądamy wierzchołki grafu i dla tych $ v $, które spełniają zależność $ d[v]=low[v] $ wypisujemy, że krawędź $ \{p[v],v\} $ jest mostem (o ile $ p[v] $ istnieje).

Do mostów wrócimy jeszcze pod koniec tego artykułu, gdzie będziemy wyznaczać złożoność czasową przedstawionych algorytmów.

Punkty artykulacji

Rozważania na temat punktów artykulacji rozpoczniemy bez większego wstępu. Przejdźmy od razu do definicji:

Punktem artykulacji nazywamy taki wierzchołek, po którego usunięciu graf się rozspójni. Inaczej: po usunięciu tego wierzchołka zwiększy się liczba spójnych składowych w grafie wejściowym.

Nie da się ukryć, że definicja punktu artykulacji jest niemal identyczna do definicji mostu. Jednak tym razem będziemy szukali wierzchołków, a nie krawędzi.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com