Omówienie zadania Przyciski (I etap XXXI OI)

Opis rozwiązania stosuje elementarne pojęcia grafowe. Ich definicje można znaleźć np. w książkach "Wprowadzenie do algorytmów" (Cormen, Leiserson, Rivest, Stein, PWN 2012) lub "Wprowadzenie do teorii grafów" (Wilson, PWN 2023).

Niech \(G\) będzie grafem dwudzielnym, którego wierzchołkami są kolumny (wierzchołki jednego koloru) i rzędy (wierzchołki drugiego koloru), a krawędź występuje wtedy i tylko wtedy, gdy jest przycisk na skrzyżowaniu danej kolumny i danego rzędu. Zgodnie z oznaczeniami z treści zadania, graf \(G\) ma \(2n\) wierzchołków i \(m\) krawędzi. Chcemy wybrać taki niepusty zbiór krawędzi w grafie \(G\), że albo do każdego wierzchołka wchodzi parzysta liczba wybranych krawędzi (rozwiązanie parzyste), albo do każdego wierzchołka wchodzi nieparzysta liczba wybranych krawędzi (rozwiązanie nieparzyste). Rozwiązanie podzielimy na te dwa osobne przypadki.

Lemat 1 ("drugie podzadanie"). Rozwiązanie parzyste istnieje wtedy i tylko wtedy, gdy w grafie \(G\) jest cykl prosty (swoją drogą, cykl prosty istnieje wtw. gdy istnieje dowolny cykl).

Dowód.

Najpierw uzasadnijmy, że jeśli w grafie \(G\) jest cykl prosty, to dla grafu istnieje rozwiązanie parzyste. Rozwiązanie takie możemy skonstruować, wybierając wszystkie krawędzie na dowolnym ustalonym cyklu prostym w \(G\). Wówczas do wierzchołków na cyklu wchodzą po 2 krawędzie, do pozostałych po 0.

Teraz wykażemy, że jeśli w grafie \(G\) istnieje rozwiązanie parzyste, to w grafie jest cykl prosty. Ustalmy rozwiązanie parzyste i weźmy dowolny wierzchołek, do którego wchodzi jakaś wybrana krawędź. Pójdźmy dowolną krawędzią z tego wierzchołka, potem dowolną krawędzią z osiągniętego wierzchołka (lecz inną niż ta, którą weszliśmy), i tak dalej, aż do jakiegoś wierzchołka wejdziemy ponownie. To się zawsze udaje, bo z każdego wierzchołka wybraliśmy parzyście wiele krawędzi: jak jedną weszliśmy, to istnieje druga, którą możemy wyjść. A ponowne wejście do jakiegoś wierzchołka oznacza, że mamy cykl prosty (od pierwszego momentu odwiedzenia tego wierzchołka do drugiego). □

Lemat 2 ("trzecie podzadanie"). Rozwiązanie nieparzyste istnieje wtedy i tylko wtedy, gdy każda spójna składowa w grafie \(G\) ma parzyście wiele wierzchołków.

Dowód.

Tym razem najpierw uzasadnimy, że jeśli w grafie \(G\) istnieje rozwiązanie nieparzyste, to każda spójna składowa grafu ma parzyście wiele wierzchołków. Rozważmy zbiór krawędzi wybranych w jakiejś spójnej składowej. Liczba ich końców jest parzysta (każda krawędź ma dwa końce). Z drugiej strony, w każdym wierzchołku mamy nieparzystą liczbę końców wybranych krawędzi. Zatem wierzchołków (w tej, czyli w każdej) spójnej składowej musi być parzyście wiele.

Teraz wykażemy, że to, że każda spójna składowa grafu \(G\) ma parzyście wiele wierzchołków, wystarcza do tego, żeby w grafie istniało rozwiązanie nieparzyste. Każdą spójną składową przetwarzamy osobno. Weźmy dowolne drzewo rozpinające \(T\) w tej spójnej składowej i rozważmy dowolne jego ukorzenienie. Będziemy wybierać tylko krawędzie z tego drzewa. Krawędź wchodzącą do danego poddrzewa wybieramy, jeśli to poddrzewo ma nieparzyście wiele wierzchołków.

Przez indukcję po rozmiarze poddrzewa możemy wykazać, że w ten sposób otrzymujemy poprawne rozwiązanie nieparzyste. Faktycznie, jeśli korzeń poddrzewa ma pod sobą nieparzyście wiele poddrzew nieparzystego rozmiaru, to wybierzemy nieparzyście wiele krawędzi z tego korzenia w dół (do tych poddrzew właśnie); całe poddrzewo będzie rozmiaru parzystego (korzeń + nieparzyście wiele poddrzew rozmiaru nieparzystego + poddrzewa rozmiaru parzystego), więc krawędzi z korzenia w górę nie bierzemy; zgadza się. Podobnie jest dla całego drzewa, które z założenia ma rozmiar parzysty. Jeśli zaś korzeń poddrzewa ma pod sobą parzyście wiele poddrzew nieparzystego rozmiaru, to wybierzemy parzyście wiele krawędzi z tego korzenia w dół, ale także krawędź z tego korzenia w górę; ponownie wszystko się zgadza. □

Algorytm.

Daje to nam łatwy sposób sprawdzenia w czasie \(O(n+m)\), czy rozwiązanie istnieje: sprawdzamy, czy istnieje cykl lub czy każda spójna składowa ma rozmiar parzysty. Oba te warunki możemy sprawdzić za pomocą jednego przeszukiwania w głąb (DFS).

Dowody lematów pokazują także jak znajdować rozwiązanie. Jeśli istnieje cykl, to musimy go znaleźć (co można zrobić przy okazji wspomnianego DFS-a) i wypisać. Jeśli zaś każda spójna składowa ma rozmiar parzysty, to drzewo wywołań DFS-a (puszczanego przy okazji sprawdzania spójności) jest drzewem rozpinającym. Sprawdzamy, czy wywołanie rekurencyjne odwiedziło parzystą czy nieparzystą liczbę wierzchołków, i w zależności od tego wypisujemy lub nie krawędź, którą wchodziliśmy. Pełne rozwiązanie działa w czasie \(O(n+m)\).

Na marginesie zauważmy, że jeśli \(m\geq 2n\), to odpowiedzią na pewno jest TAK: w \(G\) jest \(2n\) wierzchołków i \(\geq 2n\) krawędzi, więc graf musi zawierać cykl, czyli dla grafu jest rozwiązanie parzyste.

W pierwszym podzadaniu, w którym \(m\leq 20\), możemy sprawdzić wszystkie możliwe wybory krawędzi, których jest \(2^m\). Przy odrobinie sprytu można to zrobić w czasie \(O(2^m)\): pamiętamy liczbę przycisków w każdej kolumnie/wierszu i aktualizujemy te liczby podczas dodawania/usuwania przycisku do/ze zbioru.