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

Wskazówka

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