Omówienie zadania Sieć społecznościowa (III etap XXX OI)

Problem przedstawiony w zadaniu będziemy interpretować w języku teorii grafów. Skonstruujemy graf, w którym użytkownicy sieci stanowić będą wierzchołki, a łączące ich relacje znajomości – krawędzie.

Graf ten może składać się z wielu spójnych składowych, ale łatwo zauważyć, że wynik dla każdej z nich możemy policzyć niezależnie. W dalszym rozwiązaniu będziemy zakładać, że rozpatrujemy pojedynczą spójną składową. Nazwijmy ją \(G\).

Kiedy odpowiedzią jest "NIE"?

Przez \(opi[v]\) oznaczmy opinię przypisaną wierzchołkowi \(v \in G\).

Opinie przypisane wierzchołkom, które łączy krawędź, muszą różnić się o dokładnie jeden, a zatem muszą być różnej parzystości. Zauważmy, że w konsekwencji tego, jeśli wierzchołki \(u\) i \(v\) łączy ścieżka o długości nieparzystej, to \(opi[v] \not\equiv_2 opi[u]\). Jeżeli więc istnieje w grafie cykl długości nieparzystej z \(u\) do \(u\), to \(opi[u] \not\equiv_2 opi[u]\), co jest oczywistą sprzecznością.

Wiemy więc, że jeżeli w grafie istnieje cykl długości nieparzystej, to odpowiedzią musi być "NIE".

Istnienie takiego cyklu najłatwiej zweryfikować sprawdzając dwudzielność grafu, czyli czy da się pokolorować w nim wierzchołki na dwa kolory, tak żeby każde dwa wierzchołki połączone krawędzią miały przypisane różne kolory. Możemy to zrobić np. algorytmem DFS. Zaczniemy w nim od dowolnego wierzchołka i przypiszemy mu kolor 1. Jego sąsiadom przypiszemy kolor 2, nieodwiedzonym sąsiadom sąsiadów – 1 itd. Poprawność tak znalezionego kolorowania jest równoważna z dwudzielnością grafu.

Widać, że jeśli każdemu wierzchołkowi przypiszemy opinię równą jego kolorowi, to otrzymamy zgodne z warunkami zadania przypisanie opinii (choć niekoniecznie optymalne pod względem liczby opinii skrajnych). A zatem odpowiedzią jest "NIE" wtedy i tylko wtedy, gdy graf \(G\) nie jest dwudzielny.

Dalej zakładamy, że graf \(G\) jest dwudzielny.

Rozwiązanie dla \(k\) nieparzystego

Dwukolorowanie dzieli nam graf dwudzielny \(G\) na dwie strony według koloru. W dalszym rozwiązaniu mówiąc o wierzchołkach pokolorowanych na ten sam kolor będziemy mówić, że są po tej samej (lewej lub prawej) stronie grafu. Każda z krawędzi łączy dwa wierzchołki znajdujące się po różnych stronach.

Skoro \(k\) jest nieparzyste, to długości ścieżek pomiędzy wszystkimi wierzchołkami o skrajnych opiniach (1 lub \(k\)) muszą być parzyste. Oznacza to, że w grafie dwudzielnym wierzchołki te należą do tej samej strony. A zatem wynik będzie nie większy niż liczba wierzchołków liczniejszej ze stron. Taki wynik możemy łatwo uzyskać, ustawiając \(opi[v] = 1\) dla wierzchołków \(v\) liczniejszej ze stron i \(opi[u] = 2\) dla wierzchołków \(u\) ze strony, zawierającej mniej wierzchołków.

Oparty na powyższych obserwacjach algorytm działa w złożoności \(O(n+m)\) i otrzymuje \(15\) punktów, gdyż gwarancję nieparzystości \(k\) mamy tylko w pierwszym podzadaniu, gdzie \(k=3\).

Co jeśli \(k\) jest parzyste?

Jeśli \(k\) jest parzyste, to wierzchołki \(v\), takie że \(opi[v]=1\), muszą znajdować się po innej stronie grafu niż wierzchołki \(u\), dla których \(opi[u]=k\). Ponadto, jeśli dla jakichś wierzchołków \(v\) i \(u\), \(opi[v]=1\) i \(opi[u]=k\), to \(dist(v,u) \geq k-1\), gdzie \(dist(v,u)\) oznacza długość najkrótszej ścieżki pomiędzy wierzchołkami \(v\) i \(u\) w grafie \(G\).

Skonstruujmy graf \(H\) o wierzchołkach z \(G\). Wierzchołki \(v, u \in H\) łączymy krawędzią, wtedy i tylko wtedy, gdy \(v\) i \(u\) leżą po różnych stronach \(G\) oraz \(dist(v,u) < k-1\).

Zauważmy, że jeśli dla wierzchołka \(v\), \(opi[v] \in \{1,k\}\), to dla każdego \(u\), takiego że krawędź \((u,v) \in H\), \(opi[u] \not\in \{1,k\}\).

Co więcej, wybierzmy zbiór wierzchołków \(U \subseteq H\), taki że dla każdej pary \(u,v \in U\), \((u,v) \not\in H\). Taki zbiór z definicji jest zbiorem niezależnym w grafie \(H\). Udowodnijmy, że dla dowolnego \(U\), spełniającego powyższy warunek, wszystkim \(u \in U\) możemy przypisać opinie skrajne. Zrobimy to za pomocą następującego algorytmu:

Jeśli zbiór \(U\) jest pusty, to w oczywisty sposób wszystkim zeru \(u \in U\) możemy przypisać opinie skrajne.

Załóżmy więc, że zbiór nie jest pusty i że bez straty ogólności istnieje jakiś wierzchołek \(u \in U\), należący do lewej strony grafu.

Przez \(DIST(u)\) oznaczmy \(\min\limits_{\substack{v \in U, \\ v \in \text{ lewa strona }} } dist(v,u)\). A oto algorytm:

Wszystkim \(u \in U\), należącym do lewej strony grafu, przypiszmy \(opi[u] = 1\).
Dla pozostałych wierzchołków \(u\):
- Jeśli \(DIST(u) < k-1\), to \(opi[u] = DIST(u)+1\).
- W przeciwnym wypadku, jeśli \(2 \mid DIST(u)\), to \(opi[u]=k-1\).
  Jeśli zaś \(2 \not\mid DIST(u)\), to \(opi[u]=k\).

Udowodnijmy, że w takim przypisaniu opinii, opinie wierzchołków połączonych krawędzią w grafie \(G\) różnią się o dokładnie 1.

Zauważmy, że dla dwóch wierzchołków \(u,v\), pomiędzy którymi biegnie krawędź w \(G\), \(DIST(u) \not\equiv_2 DIST(v)\), czyli też \(DIST(u) \neq DIST(v)\), ponieważ wszystkie wierzchołki o opinii 1 znajdują się po jednej stronie grafu dwudzielnego. Co więcej, \(\vert DIST(u)-DIST(v) \vert = 1\), bo w przeciwnym wypadku jedna z tych wartości nie odpowiadałaby najkrótszej ścieżce (moglibyśmy poprowadzić krótszą ścieżkę przez krawędź \((v,u)\)). Wierzchołki \(u\) i \(v\) muszą leżeć po różnych stronach grafu dwudzielnego. Bez straty ogólności załóżmy, że \(u\) leży po lewej stronie. Rozpatrzmy trzy przypadki:

\(DIST(u) < k-2\)

Skoro \(DIST(u) < k-2\) oraz \(DIST(v) < k-1\), to \(opi[u] = DIST(u)+1\) i \(opi[v] = DIST(v)+1\), zatem skoro \(\vert DIST(u)-DIST(v) \vert = 1\), to również \(\vert opi[v]-opi[u] \vert = 1\)

\(DIST(u) = k-2\)

Wówczas albo \(DIST(v) = k-3\) albo \(DIST(v) = k-1\). W pierwszym przypadku \(opi[v] = DIST(v)+1 = k-2\), a \(opi[u] = DIST(u)+1 = k-1\). W drugim przypadku \(opi[v] = k\), ponieważ \(2 \not\mid k-1 = DIST(v)\). W takim razie w obu sytuacjach \(\vert opi[u]-opi[v] \vert = 1\).

\(DIST(u) > k-2\)

\(u\) leży po lewej stronie, zatem \(2 \mid DIST(u)\). W takim razie \(opi[u] = k-1\). Także z racji na parzystość, \(DIST(u) > k-1\), więc \(DIST(v) \geq k-1\). Przypomnijmy, że \(2 \not \mid DIST(v)\), tak więc \(opi[v] = k\). Również w tym przypadku \(\vert opi[u] - opi[v] \vert = 1\).

Udało nam się wykazać, że w takim przypisaniu opinii różnica opinii wierzchołków połączonych krawędzią w \(G\) jest zawsze równa 1.

Ponadto, jeśli \(u \in U\) oraz \(u\) leży po prawej stronie grafu dwudzielnego, to \(DIST(u) > k-1\), bo w przeciwnym wypadku dla jakiegoś \(v \in U\) z lewej strony istniałaby krawędź \((v,u) \in H\). Dodatkowo \(u\) leży po prawej stronie, więc \(2 \not\mid DIST(u)\). Z tych dwóch faktów wynika, że przypisaliśmy \(opi[u] = k\).

Tak więc wszystkie wierzchołki \(u \in U\) mają przypisane skrajne opinie.

Jak znaleźć największy zbiór \(U\)?

Udowodniliśmy, że zbiorowi wierzchołków możemy przypisać skrajne opinie wtedy i tylko wtedy, gdy jest to zbiór niezależny w grafie \(H\). Ponieważ chcemy zmaksymalizować liczbę wierzchołków o skrajnych opiniach, to naszym zadaniem jest znaleźć największy zbiór niezależny w grafie \(H\).

Wykorzystamy tutaj znaną własność: największy zbiór niezależny w grafie można znaleźć przy pomocy maksymalnego skojarzenia.

Skojarzenie w grafie to taki podzbiór krawędzi, w którym żadne dwie nie są incydentne z tym samym wierzchołkiem. Maksymalne skojarzenie \(M \subseteq H\) można wyznaczyć korzystając z algorytmu Forda-Fulkersona w złożoności \(O(nm)\) lub algorytmu Hopcrofta-Karpa-Karzanova, działającego w złożoności \(O(\sqrt{n}m)\). W zadaniu tym wystarczało użycie mniej efektywnego z tych dwóch algorytmów.

Jak z maksymalnego skojarzenia \(M\) dostać największy zbiór niezależny?

Zaczynamy od spostrzeżenia, że dopełnieniem maksymalnego zbioru niezależnego do zbioru wszystkich wierzchołków w grafie jest minimalne pokrycie wierzchołkowe: czyli najmniejszy podzbiór wierzchołków \(S \subseteq H\), taki że każda krawędź grafu \(H\) jest incydentna z jakimś \(u \in S\).

Zauważmy, że w oczywisty sposób \(\vert S \vert \geq \vert M \vert\), bo w przeciwnym wypadku któraś z krawędzi maksymalnego skojarzenia nie byłaby pokryta przez wierzchołki ze zbioru \(S\). Postaramy się udowodnić, że \( \vert S \vert = \vert M \vert\). Przedstawimy następujący dowód konstruktywny:

Zdefiniujmy zbiór \(Z\). Na początku dodajmy do niego wszystkie leżące po lewej stronie grafu wierzchołki, do których nie istnieje krawędź incydentna w skojarzeniu \(M\).

Do zbioru \(Z\) dodajmy wszystkie wierzchołki, do których da się dojść z któregoś z powyższych wierzchołków ścieżką alternującą. Ścieżka alternująca to taka ścieżka, w której na zmianę występują krawędzie występujące i niewystępujące w skojarzeniu \(M\). Takie wierzchołki możemy znaleźć w czasie liniowym algorytmem BFS lub DFS (odwiedzanie wierzchołków więcej niż raz jest redundantne).

Niech do zbioru \(S\) należą:

wierzchołki z lewej strony grafu, które nie należą do \(Z\)
wierzchołki z prawej strony grafu, które należą do \(Z\)

Postaramy się udowodnić, że taki zbiór \(S\) jest pokryciem wierzchołkowym oraz \(\vert S \vert = \vert M \vert\).

Zacznijmy od udowodnienia, że każda krawędź \((u,v) \in H\) jest pokrywana przez zbiór \(S\). Bez straty ogólności załóżmy, że \(u\) należy do lewej strony grafu, a \(v\) do prawej.

Jeśli \(u \not \in Z\), to \(u \in S\), więc w oczywisty sposób krawędź \((u,v)\) jest pokryta.
Jeśli \(u \in Z\), to: jeśli krawędź \(u,v\) nie należy do skojarzenia, to \(v \in Z\), gdyż z \(u\) do \(v\) prowadzi jednokrawędziowa ścieżka alternująca. Tak więc również \(v \in S\) i \((v,u)\) jest pokryta. Jeśli zaś \(u,v\) należy do skojarzenia, to na pewno \(u\) nie było początkowym wierzchołkiem zbioru \(Z\), gdyż należy do skojarzenia. Tak więc istnieje jakaś ścieżka alternująca z jednego z wierzchołków początkowych \(Z\) do \(u\). Nazwijmy ją \(A\), a ten wierzchołek początkowy \(s\). Wierzchołki \(s\) i \(u\) leżą po tej samej stronie grafu dwudzielnego, więc długość ścieżki \(A\) jest parzysta. Co więcej \(s\) nie ma żadnej krawędzi skojarzonej w \(M\), tak więc ścieżka \(A\) zaczyna się od krawędzi nieskojarzonej. Tak więc ostatnia krawędź \(A\) jest skojarzona, a z definicji skojarzenia istnieje dokładnie jedna krawędź skojarzona incydentna z \(u\) – jest to krawędź prowadząca do \(v\). Ale w takim razie ścieżka \(A \setminus (u,v)\) jest ścieżką alternującą z \(s\) do \(v\), czyli \(v \in Z\). Skoro \(v\) należy do prawej strony, to \(v \in S\), czyli krawędź \((u,v)\) jest pokryta.

Tak więc \(S\) jest pokryciem wierzchołkowym. Jak już wykazaliśmy, wynika z tego, że \(\vert S \vert \geq \vert M \vert\). Czyli jeśli dodatkowo pokażemy, że \(\vert S \vert = \vert M \vert\), to będzie to oznaczało, że \(S\) jest minimalnym pokryciem wierzchołkowym.

Udowodnijmy, że każdy wierzchołek \(u \in S\) jest końcem jednej krawędzi ze skojarzenia \(M\). Co więcej, każdy wierzchołek z \(S\) będzie końcem innej krawędzi z \(M\), bo \(S\) jest pokryciem wierzchołkowym. Udowodni nam to równoliczność \(S\) i \(M\).
Z definicji skojarzenia, \(u\) może być końcem co najwyżej jednej krawędzi z \(M\). Jeśli \(u\) należy do lewej strony, to \(u \not \in Z\), więc \(u\) musi być incydentny z jakąś krawędzią ze skojarzenia (w przeciwnym wypadku byłby wierzchołkiem początkowym \(Z\)). Jeśli zaś \(u\) należy do prawej strony, to \(u \in S\) implikuje, że istnieje ścieżka alternująca \(A\) z jakiegoś wierzchołka początkowego \(s\) do \(u\). Wierzchołek \(s\) jest nieskojarzony. Jeśli \(u\) jest nieskojarzone, to po dodaniu wszystkich nieskojarzonych krawędzi z \(A\) do skojarzenia oraz usunięciu wszystkich skojarzonych krawędzi z \(A\) ze skojarzenia, otrzymalibyśmy skojarzenie o jeden większe od \(M\), co jest sprzeczne z założeniem, że \(M\) jest skojarzeniem maksymalnym. Tak więc wierzchołek \(s\) musi być incydentny z jakąś krawędzią ze skojarzenia, co należało wykazać.

Otrzymany powyżej wynik często określany jest twierdzeniem Kőniga.

Podsumowanie

Opis przygotowano w ramach projektu "Mistrzostwa w Algorytmice i Programowaniu - Uczniowie" - zadania finansowanego ze środków Ministerstwa Cyfryzacji.