[Algorytmy] Wierzchołek rozspójniający.

[matinf]

Cześć,

Mam takie coś:

Wierzchołkiem rozdzielającym w spójnym grafie nazywamy wierzchołek, którego usunięcie rozspójnia graf.
Mamy graf dany przez listy sąsiedztwa.

a) Jak znaleźć dowolny wierzchołek, który nie rozspójnia. (szybko)
Obliczam stopnie dla każdego wierzchołka.
Do usunięcia wskazuję wierzchołek stopnia 1. Jeśli takiego nie ma, to wskazuje dowolny (bo leży na cyklu).

b)
Jak efektywnie wyznaczyć kolejność usuwania wierzchołków grafu, tak że żadne usunięcie nie rozspójni grafu.

Kod: Zaznacz cały

1. Obliczam stopnie wszystkich wierzchołków i wsadzam do kolejki priorytetowej typu min. Niech to będzie kopiec fib.
while kolejka nie jest pusta
     wyciągnij węzeł o najmniejszym stopniu
     wszystkim jego sąsiadom zmniejsz stopien (operacje Decrease-key)

Kolejność usuwania z kolejki to szukana kolejność.
Całość działa w złożoności takiej jak Alg. Dijsktry: \(\displaystyle{ O(|V|\log(V) +|E|)}\) - zamortyzowany.

Ok ? Może ktoś lepiej potrafi ?

[Afish]

a) nie zadziała dla grafu o wierzchołkach A-E i krawędziach AB, AC, BC, CD, CE, DE. Nie ma wierzchołka o stopniu 1, wierzchołek C rozspójnia graf.

[matinf]

W takim razie trzeba usunąć węzeł o najmniejszym stopniu.

a b) ?

[norwimaj]

\(\displaystyle{ \begin{picture}(0,0)
\put(0,0){\circle*{4}}
\put(20,0){\circle*{4}}
\put(40,0){\circle*{4}}
\put(50,20){\circle*{4}}
\put(50,-20){\circle*{4}}
\put(-20,0){\circle*{4}}
\put(-40,0){\circle*{4}}
\put(-50,20){\circle*{4}}
\put(-50,-20){\circle*{4}}
\put(-40,0){\line(1,0){80}}
\put(20,0){\line(3,2){30}}
\put(40,0){\line(1,2){10}}
\put(-20,0){\line(-3,2){30}}
\put(-40,0){\line(-1,2){10}}
\put(20,0){\line(3,-2){30}}
\put(40,0){\line(1,-2){10}}
\put(-20,0){\line(-3,-2){30}}
\put(-40,0){\line(-1,-2){10}}
\put(50,-20){\line(0,1){40}}
\put(-50,-20){\line(0,1){40}}
\end{picture}}\)-- 30 lis 2015, o 20:51 --Może lepiej spróbuj jakiegoś przeszukiwania grafu. Czy ostatni odwiedzony wierzchołek nie będzie dobry? A później przedostatni, itd?

[matinf]

Ok, pomyślę. Odnieście się do b) proszę.

[norwimaj]

Odnieście się do b) proszę.

Przeczytaj wcześniejsze wpisy.

[Afish]

Słowo klucz: punkt artykulacji.

[matinf]

Ok, weźmy część a)

Rozwiązanie na bank dobre, hint od Afisha:

W czasie \(\displaystyle{ O(|V|+|E|)}\) znajdz wszystkie punkty artykulacyjne. Jako odpowiedź zwróć dowolny nieartykulacyjny.

Idąc za norwimajem:
Odpalmy DFS-a. Wierzchołek najpóźniej odwiedzony (po raz pierwszy- kolorowanie na szaro) jest odpowiedzią.
Jest to wierzchołek który w drzewie przeszukiwania w głąb jest liściem. Jeśli wychodzi z niego krawędź, to tworzy ona cykl.
Jeśli nie wychodzi z niego żadna krawędź to można go też usunąć i nie rozspójnić.


b)
Zdefiniujmy dwuspójną składową.
Dwuspójna składowa jest to taki podgraf, że każde dwa wierzchołki leżą wzajemnie na cyklu.

1. Podziel graf na dwuspójne.
2. Znajdź punkty artykulacyjne. Pokoloruj je na niebiesko i traktuj jakby ich w grafie nie było.
3. Usuwaj kolejno punkty z dwuspójnych składowych (de facto cykli). W dowolnej kolejności,
4. Przypomnij sobie o wierzchołkach niebieskich. Pozostałe wierzchołki nie tworzą żadnego cyklu, mamy więc drzewo.
Odpalmy DFS-a, żeby dostać ukorzenione drzewo. Teraz usuwamy węzły począwszy od najniższego poziomu.

Hmmm ?

[norwimaj]

To jest jakieś nowe zadanie, czy plan rozwiązania punktu b?

[matinf]

Plan rozwiązania.

[norwimaj]

A to było złe?

Może lepiej spróbuj jakiegoś przeszukiwania grafu. Czy ostatni odwiedzony wierzchołek nie będzie dobry? A później przedostatni, itd?

[matinf]

Użyłem tego do (a).

Być może też działa. Pomyślimy. Możesz rzucić okiem na obecne ?