Ćwiczenia | Informatyka MIMUW

Zadanie 1

Pokaż, w jaki sposób sprawdzić w czasie liniowym, czy graf jest grafem dwudzielnym:

a) za pomocą przeszukiwania wszerz,
b) z wykorzystaniem przeszukiwania w głąb.

Wskazówka

Skorzystaj z faktu, że graf jest grafem dwudzielnym wtedy i tylko wtedy, gdy nie zawiera żadnego cyklu o długości nieparzystej. Przeanalizuj te miejsca w obu algorytmach, w których wykrywany jest cykl.

Zadanie 2

Niech \( G=(V,E) \) będzie grafem spójnym. Wierzchołkiem rozdzielającym w grafie \( G \) nazywamy każdy wierzchołek, którego usunięcie rozspójnia \( G \). Zaadaptuj algorytm wykrywania mostów grafie do znajdowania wszystkich wierzchołków rozdzielających.

Wskazówka

Udowodnij następujące twierdzenie.

Niech \( T \) będzie drzewem przeszukiwania w głąb grafu \( G \). Wierzchołek \( v \) jest wierzchołkiem rozdzielającym w grafie \( G \) wtedy i tylko wtedy, gdy \( v \) jest korzeniem \( T \) i ma w \( T \) dwóch synów lub \( v \) nie jest korzeniem, ale posiada syna \( u \) takiego, że \( nr[v] \le low[u] \).

Zadanie 3

Graf spójny bez wierzchołków rozdzielających nazywamy grafem dwuspójnym. Dwuspójną składową grafu G nazywam każdy jego maksymalny (w sensie zawierania) dwuspójny podgraf.
a) Udowodnij, że każda krawędź grafu należy do dokładnie jednej dwuspójnej składowej.
b) Zaprojektuj algorytm, który w czasie liniowym policzy wszystkie dwuspójne składowe danego (przez listy sąsiedztw), spójnego grafu, tzn. podzieli zbiór wszystkich krawędzi na podzbiory odpowiadające poszczególnym dwuspójnym składowym.

Wskazówka

Zaadaptuj algorytm do wykrywania wierzchołków rozdzielających. Każdą nowo odwiedzaną krawędź \( u-v \) odkładaj na stos. Bez straty ogólności przyjmijmy, że \( u \) jest przodkiem \( v \) w drzewie. Jeśli \( u-v \) jest krawędzią drzewową, to odkładamy ją na stos będąc w wierzchołku \( u \), natomiast jeśli jest to krawędź niedrzewowa, to będąc w wierzchołku \( v \). Po wykryciu każdego wierzchołka rozdzielającego \( v \) wypisz wszystkie krawędzie ze stosu kończąc na krawędzi drzewowej \( v-u \) takiej, że \( low[u] \ge nr[v] \).

Zadanie 4

Dotychczas rozważaliśmy tylko grafy nieskierowane. Zaproponuj sposób reprezentacji grafu skierowanego za pomocą list sąsiedztw.

Zadanie 5

Powiemy, że graf skierowany jest silnie spójny, jeśli dla każdej pary wierzchołków \( u \), \( v \) istnieją skierowane ścieżki z \( u \) do \( v \) i z \( v \) do \( u \). Zaprojektuj algorytm, który w czasie \( O(n+m) \) sprawdza, czy dany graf jest grafem silnie spójnym.

Zadanie 6

Zaproponuj algorytm, który w czasie liniowym zorientuje krawędzie grafu dwuspójnego w taki sposób, żeby otrzymany graf był silnie spójny.