Ćwiczenia

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.

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.

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.

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.