ASD Ćwiczenia 12

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$. Zaadoptuj 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.