rys1 Przykładowe drzewo o wierzchołkach i wyróżnionym zbiorze Mamy tu dwa minimalne zbiory blokujące: i

Zadanie można przeformułować następująco: dane jest -wierzchołkowe drzewo, w którym wyróżniono podzbiór wierzchołków Należy znaleźć najmniejszy blokujący zbiór wierzchołków (rozłączny z ), taki że każda ścieżka z dowolnego wierzchołka zbioru do dowolnego liścia drzewa musi przechodzić przez co najmniej jeden wierzchołek ze zbioru blokującego (patrz drzewo na rysunku 1).

Rys. 2 Drzewo Minimalny zbiór blokujący ma 7 wierzchołków.

Na początek wypróbujmy kilku kandydatów na zbiór blokujący. Oczywiste jest, że zbiór wszystkich liści w drzewie jest zbiorem blokującym (zakładamy, że nie zawiera liścia, w przeciwnym przypadku zbiór blokujący nie istnieje). Również jest nim zbiór wszystkich niewyróżnionych sąsiadów wierzchołków z Dość łatwo się jednak przekonać, że żaden z nich nie musi być minimalny - dla drzewa są to zbiory oraz ; oba mają po 4 wierzchołki.

Zacznijmy jednak od zbioru liści i spróbujmy usunąć z niego nadmiarowe wierzchołki. Jeśli jedyny sąsiad liścia należy do zbioru to każdy zbiór blokujący musi zawierać liść (np. każdy zbiór blokujący dla drzewa musi zawierać wierzchołki 1 i 6). Z drugiej strony, jeśli wierzchołek nie należy do to istnieje minimalny zbiór blokujący, który nie zawiera liścia Jest tak dlatego, że każda ścieżka z do przechodzi przez więc, blokując wierzchołek zamiast wierzchołka dostajemy równie dobre rozwiązanie. Postępując w ten sposób z drzewem pozbędziemy się liści i znajdziemy zbiór blokujący ale nie dla każdego drzewa tak znaleziony zbiór będzie minimalny (patrz drzewo na rysunku 2).

Rys. 3 Jedyna składowa drzewa ukorzeniona w Wierzchołki z zaznaczone zostały kolorem, wierzchołki z są czarne.

Zwodnicze jest, że w treści zadania liście oraz wyróżnione wierzchołki pełnią nieco inną rolę (w szczególności można blokować liście, ale nie wierzchołki z ). Możemy jednak nieznacznie przeformułować treść zadania, aby te role stały się w pełni symetryczne. Zauważyliśmy już, że musimy blokować jedynie liście sąsiadujące z a ponieważ nie wpływają one na resztę wierzchołków, możemy je dodać do zbioru blokującego i usunąć z drzewa. Następnie oznaczmy zbiór pozostałych liści przez Składową w drzewie nazwiemy maksymalny zbiór wierzchołków, z których każde dwa można połączyć ścieżką, której wewnętrzne wierzchołki nie należą do zbioru Przykładowo w drzewie mamy jedną składową zawierającą 17 wierzchołków, a gdyby wierzchołek należał do to mielibyśmy trzy składowe, o licznościach 6, 6 i 7. Zauważmy, że zbiór blokujący możemy wyznaczyć dla każdej składowej niezależnie. Będzie to taki podzbiór wierzchołków spoza że każda ścieżka ze zbioru do zbioru musi przecinać ten podzbiór.

Weźmy zatem składową i ukorzeńmy ją w dowolnym wierzchołku spoza (Rys. 3). Zastosujemy teraz programowanie dynamiczne - przeglądając drzewo składowej od liści do korzenia, w każdym poddrzewie będziemy konstruować minimalny zbiór blokujący. Jednocześnie każdy wierzchołek będziemy wrzucać do jednego z trzech zbiorów: (jeśli poddrzewo zaczepione w zawiera taki wierzchołek z do którego ścieżka z nie zawiera zablokowanych wierzchołków), (poddrzewo to zawiera niezablokowany wierzchołek z ) oraz (wszystkie wierzchołki z w tym poddrzewie są zablokowane - być może z powodu dodania wierzchołka do zbioru blokującego).

Rys. 4 Wierzchołki składowej przydzielone do zbiorów zaznaczone są odpowiednio na biało, kolorowo i czarno. Wyróżniono również wierzchołki minimalnego zbioru blokującego oraz odpowiadające im ścieżki.

Wierzchołki ze zbiorów i lądują odpowiednio w zbiorach i Rozważmy teraz wierzchołek wewnętrzny ; jeśli ma on takie dwoje dzieci, z których jedno należy do a drugie należy do to przez wierzchołek przechodzi (co najmniej jedna) niezablokowana ścieżka łącząca pewien wierzchołek z z pewnym wierzchołkiem z Dodajemy zatem do zbioru blokującego oraz do zbioru W przeciwnym przypadku wszystkie dzieci należą do zbioru lub i dodajemy wierzchołek odpowiednio do zbioru lub (Rys. 4).

Jasne jest, że w ten sposób skonstruujemy poprawny zbiór blokujący Dowodem na jego minimalność jest skonstruowany, niejako przy okazji, zbiór ścieżek które są rozłączne, a każda musi zawierać co najmniej jeden wierzchołek z Złożoność czasowa rozwiązania to