Trudne związki

W ramach rozgrzewki przed sezonem proponuję krótkie i przyjemne zadanie o rekonstrukcji grafu na podstawie stopni jego wierzchołków. Żeby nie było całkiem standardowo, pozwalamy na istnienie wielokrotnych krawędzi (które nie są pętlami), ale za to graf koniecznie musi być spójny.

W treści widzimy, że co prawda graf jest na co najwyżej 5000 wierzchołkach, ale za to ich stopnie mogą być bardzo duże, nawet 10^9. Jesteśmy proszeni nie tylko o stwierdzenia, czy istnieje choć jeden graf o podanych stopniach poszczególnych wierzchołków, lecz także — co pewnie o wiele trudniejsze — o wypisanie takiego grafu w postaci macierzy sąsiedztwa, a dokładniej macierzy, w której zapisujemy liczbę krawędzi pomiędzy każdą parą wierzchołków. Tyle w kwestii treści.

Być może widzieliście już bardziej klasyczną wersję tego zadania, w której graf musi być prosty (czyli bez krawędzi wielokrotnych i pętli), ale niekoniecznie spójny. Okazuje się, że jeśli d_1 \geq d_2 \geq \ldots d_n jest posortowanym ciągiem wymarzonych stopni wierzchołków, taki graf istnieje dokładnie wtedy gdy \sum_{i=1}^{n} d_i jest parzyste oraz:

\sum_{i=1}^{k} d_i \leq k(k-1)+\sum_{i=k+1}^{n} \min(d_i,k)

dla każdego k=1,2,\ldots,n. Łatwo zauważyć, że jest to warunek konieczny, wystarczy bowiem wyobrazić sobie, że kroimy graf na dwie części złożone z wierzchołków \{1,2,\ldots,k\} oraz \{k+1,k+2,\ldots,n\}. Skoro graf jest prosty, to mamy co najwyżej \sum_{i=k+1}^{n} \min(d_i,k) krawędzi przechodzących pomiędzy różnymi częściami i co najwyżej \frac{k(k-1)}{2} krawędzi pomiędzy wierzchołkami w pierwszej części, co pozwala nam na ograniczenie z góry sumy stopni wierzchołków w tej pierwszej części. Pokazanie równoważności wymaga już chwili zastanowienia. Ta wersja jest na tyle znana, że pojawia się nawet na wikipedii.

Co prawda być może dokładne zrozumienie rozwiązania zadania w jego klasycznej wersji jest pomocne w poradzeniu sobie z tą zmodyfikowaną, ale na razie przyjmijmy, że spróbujemy tego uniknąć. Oczywiście \sum_{i=1}^{n} d_i musi być parzyste także i w naszej wersji. Czy można powiedzieć o tej sumie coś ciekawszego?

Pewnie można. Skoro graf ma być spójny, to w szczególności posiada jakieś drzewo spinające. Suma stopni w drzewie na n wierzchołkach musi być równa 2(n-1) (co pokażemy za chwilę), a więc \sum_{i=1}^{n} d_i \geq 2(n-1), nie jest to jednak jeszcze warunek wystarczający. Zanim pojedziemy dalej pomyślmy jeszcze przez chwilę o drzewach.

Lemat 1. d_1,d_2,\ldots,d_n jest ciągiem stopni wierzchołków drzewa dokładnie wtedy gdy n=1 i d_1=0 lub n\geq 2, d_1,d_2,\ldots,d_n \geq 1 oraz \sum_{i=1}^{n} d_i = 2(n-1).

Dowód. Konieczność jest jasna. Aby pokazać wystarczającość stosujemy indukcję względem n. Dla n \geq 2 zauważamy, że istnieją wierzchołki i oraz j dla których d_i = 1 oraz d_j \geq 2. Dlaczego? Średni stopień wierzchołka to \frac{2(n-1)}{n} < 2, czyli na pewno istnieje choć jeden wierzchołek stopnia mniejszego niż 2. A przecież nie ma wierzchołków stopnia 0, czyli istnieje choć jeden wierzchołek stopnia dokładnie 1. Nie może być tak, że wszystkie wierzchołki są stopnia 1, gdyż wtedy suma stopni wynosiłaby n < 2(n-1), czyli istnieje choć jeden wierzchołek stopnia przynajmniej 2. Teraz usuwamy wierzchołek i oraz zmniejszamy d_j o jeden. Widać, że z założenia indukcyjnego istnieje drzewo na n-1 wierzchołkach o tak zdefiniowanych stopniach. Podpinając wierzchołek i jako liść do wierzchołka j otrzymujemy szukane drzewo na n wierzchołkach.

Wróćmy do zadania. Przypadek n=1 rozważamy osobno. Dla n \geq 2 na pewno d_1,d_2,\ldots,d_n \geq 1. Wyobraźmy sobie, że ustalamy jakieś drzewo rozpinające w szukanym grafie i oznaczmy stopnie wierzchołków w tym drzewie przez d'_1,d'_2,\ldots,d'_n. Mamy więc \sum_{i=1}^{n} d'_i = 2(n-1) oraz d'_i \leq d_i dla każdego i=1,2,\ldots,n (stąd to wspomniane wcześniej \sum_{i=1}^{n} d_i \geq 2(n-1)). Dalej, wyobraźmy sobie, że powolutku przekształcamy szukany graf w to ustalone drzewo rozpinające usuwając nadmiarowe krawędzie. Kiedy takie przekształcenie jest możliwe? Dokładnie wtedy, gdy liczby d_1-d'_1,d_2-d'_2,\ldots,d_n-d'_n można przekształcić w ciąg samych zer wykonując operacje typu: wybierz dwie różne pozycje i zmniejsz znajdujące się tam liczby o jeden. Spróbujmy więc sformułować konieczny i wystarczający warunek na to, że takie przekształcenie jest możliwe.

Lemat 2. Ciąg (a_1,a_2,\ldots,a_n) można przekształcić w (0,0,\ldots,0) wykonując operacje polegające na wybraniu i<j i zmniejszeniu i-tej oraz j-tej liczby o jeden dokładnie wtedy, gdy \max_{i=1}^{n} a_i \leq \frac{1}{2}\sum_{i=1}^{n} a_i oraz \sum_{i=1}^{n} a_i jest parzyste.

Dowód. Konieczność takiego warunku jest dość jasna: w każdym ruchu zmniejszamy sumę o 2, a maksimum co najwyżej o 1. Chcąc zredukować obydwa wyrażenia do zera nie możemy więc zacząć ze zbyt dużym maksimum. Wystarczającość najłatwiej zobaczyć na rysunku.

trudne1

Wyobraźmy sobie, że każde a_i odpowiada segmentowi złożonym z a_i pól. Układamy wszystkie takie segmenty jeden po drugim i malujemy na różne kolory. Następnie przecinamy otrzymany segment (złożony z \sum_{i=1}^{n} a_i pól) w połowie i układamy otrzymane połówki pod sobą. Skoro \max_{i=1}^{n} a_i \leq \frac{1}{2}\sum_{i=1}^{n} a_i to każde dwa pola sąsiadujące w pionie mają różne kolory, co wyznacza nam szukany ciąg operacji. W k-tej z nich zmniejszamy liczby na pozycjach odpowiadających kolorom w k-tej kolumnie.

Otrzymaliśmy więc następujący warunek: szukany graf istnieje dokładnie wtedy gdy można znaleźć takie liczby całkowite a_1\in [0,d_1),a_2\in [0,d_2),\ldots,a_n\in [0,d_n), że \max_{i=1}^{n} a_i \leq \frac{1}{2}\sum_{i=1}^{n} a_i oraz \sum_{i=1}^{n}a_i = \sum_{i=1}^{n}d_i - 2(n-1). Ale jak to sprawdzić?

Dość łatwo. Przecież znamy \sum_{i=1}^{n} a_i = S, więc tak naprawdę wiemy jak duże może być każde a_i (mniejsze niż d_i i nie większe niż połowa tej znanej sumy). Wystarczy więc sprawdzić czy biorąc takie największe możliwe a_i jesteśmy w stanie uzbierać przynajmniej \sum_{i=1}^{n}d_i - 2(n-1).

Świetnie, czyli umiemy już sprawdzić czy istnieje choć jeden graf o podanych stopniach wierzchołków. Ale czy to całe rozumowanie prowadzi do efektywnego algorytmu? Nietrudno uwierzyć, że owszem. Przede wszystkim, łatwo wyznaczyć szukane liczby a_i w czasie \mathcal{O}(n). Trzeba tylko przeglądać kolejne i wybierając jak największe a_i, które jest mniejsze niż d_i, nie większe niż połowa S, a jednocześnie nie powoduje, że \sum_{i=1}^{n} a_i przekracza S. Każde kolejne a_i może być wyznaczone w czasie stałym prostym wzorkiem. Teraz używamy Lematu 2 na ciągu (a_1,a_2,\ldots,a_n) i Lematu 1 na (posortowanych) d_1-a_1,d_2-a_2,\ldots,d_n-a_n. Co prawda dowód Lematu 2 sugerował, że jawnie konstruujemy wszystkie pola (a tych może być przecież strasznie dużo!), jednak nie jest to konieczne. Można operować na grupkach pól tego samego koloru w obydwu połówkach i w czasie \mathcal{O}(n) wyznaczyć skompresowany opis wszystkich par, w którym podajemy ciąg par kolorów wraz z krotnościami. Dowód Lematu 1 był dość algorytmiczny: w każdym kroku wybieramy i<j, odpalamy się rekurencyjnie, a następnie doklejamy jeden liść. Dość trywialnie możemy więc zaimplementować całą procedurę w czasie \mathcal{O}(n^2), nietrudno też zmniejszyć ten czas do liniowego utrzymując listę wierzchołków stopnia jeden i listę wierzchołków stopnia przynajmniej dwa. Daje nam to więc rozwiązanie całego zadania, które w zasadzie działa w czasie liniowym, poza przykrą koniecznością wypisania grafu w postaci macierzy sąsiedztwa (w której większość pól to i tak zera).

Reklamy

2 myśli nt. „Trudne związki

  1. O ile dobrze rozumiem Twój algorytm, to w macierzy sąsiedztwa jest co najwyżej O(n) niezerowych pól (drzewo ma n-1 krawędzi, a merdżowanie dwóch list zawierających łącznie n+1 pasków może dać coś koło 2*n multikrawędzi). Trochę dziwi zatem taki a nie inny wybór formatu wyjścia. Może nie chcieli podpowiedzieć rozwiązania.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s