Oszczędny listonosz

Afiliacja: Doktorant, Wydział Matematyki, Informatyki i Mechaniki, Uniwersytet Warszawski

Wyobraźmy sobie miasteczko, w którym żyje \(n\) osób. Nie dotarł tam ani Internet, ani nawet idea urzędu pocztowego. Jest jednak zatrudniony listonosz, u którego można bezpośrednio nadać lub odebrać przesyłkę. Listonosz codziennie odwiedza każdego mieszkańca dokładnie jeden raz. Niektórzy mieszkańcy korespondują z innymi, lecz niekoniecznie każdy z każdym. Jeśli kogoś odwiedzi listonosz, to osoba ta z pewnością zapyta go, do kogo się jeszcze wybiera, a następnie wyśle list do wszystkich, z którymi koresponduje, a których listonosz jeszcze tego dnia nie odwiedził. Listonosz może sam wybrać kolejność, w jakiej odwiedza mieszkańców miasteczka. Zdążył się już też zorientować, kto z kim koresponduje, i chce odwiedzić mieszkańców w takiej kolejności, żeby w żadnym momencie nie dźwigać za dużo listów. Ile listów na pewno będzie musiał w pewnym momencie zmieścić w torbie listonosz?

Sami swoi

Zacznijmy od przypadku najprostszego do analizy – gdy każdy koresponduje z każdym. Wówczas niezależnie od kolejności, jaką wybrał listonosz, sytuacja wygląda następująco: jeśli listonosz odwiedził już dokładnie \(i\) mieszkańców, to ma w torbie \(i(n-i)\) listów. Istotnie, w torbie listonosza znajdują się listy od każdego z odwiedzonych mieszkańców do każdego z \(n-i\) jeszcze nieodwiedzonych. Wykonując proste szacowanie, możemy przekonać się, że \(i(n-i)\) wynosi maksymalnie \(\frac{n^2}{4}\) dla \(n\) parzystego oraz \(\frac{n^2-1}{4}\) dla \(n\) nieparzystego, co daje nam górne ograniczenie na rozmiar torby potrzebnej listonoszowi.

Korporacja

A co, jeśli nasze miasteczko to tak naprawdę nie miasteczko, ale wielka korporacja? Naturalnie w korporacji pracownicy mają przypisany jakiś stopień awansu zawodowego. Najwyższy stopień ma oczywiście prezes, którego będziemy oznaczać \(v_1.\) Ponadto założymy, że każdy pracownik \(v_i,\) którego stopień awansu nie jest najniższy (czyli nie jest na samym dole hierarchii), ma dokładnie dwóch bezpośrednich podwładnych: \(v_{2i}\) oraz \(v_{2i+1}.\) Mają oni dokładnie o jeden mniejszy od \(v_i\) stopień awansu zawodowego. Każdy pracownik oprócz \(v_1\) ma dokładnie jednego przełożonego. W przypadku tej korporacji wiadomości będą przesyłane jedynie pomiędzy pracownikiem a jego bezpośrednim podwładnym lub odwrotnie. Jak dużą torbę musi mieć listonosz w takim przypadku?

Ta sytuacja jest już nieco trudniejsza. Sformułujmy nasz problem w języku teorii grafów. Niech \(v_1, \dots, v_n\) oznaczają mieszkańców (albo pracowników, jak w przykładzie z korporacją) i niech \(V=\{v_1, \dots ,v_n\}.\) Rozpatrzmy graf \(G=(V,E),\) przy czym \((v_i,v_j)\in E\) oznacza, że \(v_i\) i \(v_j\) korespondują ze sobą. Naszym zadaniem jest znaleźć minimalną potrzebną pojemność torby, czyli dokładnie wartość: \[c(G) = \min_{\sigma \in \Sigma_n} \max_{1 \leq k \leq n} |\{(v_{\sigma(i)}, v_{\sigma(j)}) \in E : i \leq k < j \}|,\] gdzie \(\Sigma_n\) oznacza zbiór wszystkich permutacji zbioru \(\{1, 2, \dots, n \}.\) Funkcję \(c(G)\) nazywanym szerokością przekroju (ang. cutwidth) grafu \(G.\)

Pomyślmy o tym w następujący sposób: Ustawiamy wierzchołki grafu \(G\) na prostej \(\ell.\) Wówczas \(c(G)\) to najmniejsza liczba \(k,\) dla której istnieje ustawienie wierzchołków takie że, każda prosta prostopadła do \(\ell\) przecina co najwyżej \(k\) krawędzi (patrz rys. 1). Proste prostopadłe do \(\ell\) będziemy nazywać przekrojami, zaś liczbę krawędzi \(G,\) które przecinają dany przekrój, będziemy nazywać jego szerokością.

Wróćmy do problemu listonosza zatrudnionego w korporacji. Niech \(T_h\) oznacza pełne drzewo binarne o wysokości \(h\) (czyli dokładnie graf reprezentujący korespondujących ze sobą pracowników, jeśli mamy korporację z \(h+1\) możliwymi stopniami awansu zawodowego). Oznaczmy wierzchołki tak jak poprzednio. Zauważmy, że \(T_h\) ma \(n = 2^{h+1}-1\) wierzchołków. Nasze zadanie polega na obliczeniu \(c(T_h).\) Warto zacząć od małych wartości \(h.\) Łatwo stwierdzić, że \(c(T_0) = 0\) oraz \(c(T_1) = 1.\) Przy odrobinie wysiłku obliczamy też, że \(c(T_2) = 2.\) Jeśli poświęcimy problemowi nieco więcej czasu i pomysłowości, to udowodnimy, że \(c(T_3) = 3\) (zachęcamy Czytelnika Dociekliwego do samodzielnego sprawdzenia).

Można więc wysnuć hipotezę, iż \(c(T_h) = h\) dla wszystkich \(h \in \mathbb{N}.\) Niemałym zaskoczeniem może być zatem fakt, że \(c(T_4) = 3.\) Ogólne rozwiązanie daje następujące twierdzenie:

Twierdzenie. Dla \(h \geq 2\) zachodzi \(c(T_h) = \big\lceil \frac{h}{2} \big\rceil + 1.\)

Aby wykazać powyższą równość, zaczniemy od udowodnienia \(c(T_h) \geq \big\lceil \frac{h}{2} \big\rceil + 1\) dla \(h \geq 2.\) Dowód będzie indukcyjny. Zostawiamy jako ćwiczenie sprawdzenie przypadków \(h = 2\) i \(h = 3.\) Chcemy udowodnić tezę dla \(T_{h+2}\) przy założeniu tezy dla \(T_{h}.\) Rozważmy dowolną permutację \(\sigma\) wierzchołków \(T_{h+2}.\) Rozważmy też poddrzewa \(T_{h+2}\) o korzeniach odpowiednio \(v_4, v_5, v_6, v_7.\) Wśród nich na pewno znajdziemy takie poddrzewo \(P,\) które nie zawiera \(v_{\sigma(1)}\) ani \(v_{\sigma(n)}.\)

Pomysł, żeby pokazywać tezę dla \(h+2,\) zakładając jej prawdziwość dla \(h,\) nie jest taki oczywisty, ale wydaje się w tym przypadku jedynym słusznym. Autor widział wiele prób pokazania tezy dla \(h+1,\) przy założeniu jej prawdziwości dla \(h,\) ale wszystkie one były błędne.

Ponieważ \(P\) wygląda tak samo jak \(T_h\) (tzn. różnią się one jedynie nazwami wierzchołków, a matematyk powiedziałby, że są izomorficzne), więc z założenia indukcyjnego \(c(P) \geq \big\lceil \frac{h}{2} \big\rceil + 1.\) Oznacza to, że jeśli ustawimy wierzchołki \(T_{h+2}\) na prostej \(\ell\) w takiej kolejności jak w permutacji \(\sigma,\) to pewna prosta \(\ell^{\bot}\) prostopadła do \(\ell\) będzie przecięta przez co najmniej \(\lceil \frac{h}{2} \big\rceil + 1\) krawędzi \(P.\) Zauważmy, że istnieje ścieżka z \(v_{\sigma(1)}\) do \(v_{\sigma(n)},\) która nie zawiera wierzchołków z \(P.\) Oznacza to, że prostą \(\ell^{\bot}\) przecina też pewna krawędź z tej ścieżki, czyli łącznie co najmniej \(\lceil \frac{h}{2} \big\rceil + 2 = \lceil \frac{h+2}{2} \big\rceil + 1\) krawędzi, co należało udowodnić.

Teraz trzeba jeszcze znaleźć dla każdego \(h \geq 2\) taką permutację \(\sigma_h\) wierzchołków \(T_h,\) która zaświadcza, że szerokość przekroju \(T_h\) faktycznie wynosi co najwyżej \(\big\lceil \frac{h}{2} \big\rceil +1.\) Zaczniemy od konstrukcji dla nieparzystych \(h.\) Teza indukcji będzie nawet nieco mocniejsza: istnieje takie ustawienie \(\sigma_h^-\) wierzchołków \(T_h\) na prostej, przy którym każdy przekrój na lewo od korzenia ma szerokość co najwyżej \(\big\lceil \frac{h}{2} \big\rceil + 1,\) zaś każdy przekrój na prawo od korzenia ma szerokość co najwyżej \(\big\lceil \frac{h}{2} \big\rceil.\) Łatwo znaleźć takie ustawienie dla \(h=1.\) Udowodnimy teraz tezę dla \(h+2\) przy założeniu tezy dla \(h.\) Niech \(\sigma_h^+\) oznacza ustawienie wierzchołków \(T_h\) powstałe z \(\sigma_h^-\) przez zapisanie wierzchołków w odwrotnej kolejności (wtedy każdy przekrój na prawo od korzenia ma szerokość co najwyżej \(\big\lceil \frac{h}{2} \big\rceil + 1,\) zaś każdy przekrój na lewo od korzenia co najwyżej \(\big\lceil \frac{h}{2} \big\rceil\)). Zauważmy, że poddrzewa \(P_4, P_5, P_6, P_7\) drzewa \(T_{h+2}\) o korzeniach odpowiednio \(v_4, v_5, v_6, v_7\) są izomorficzne z \(T_h,\) więc ma sens powiedzenie, że ustawiamy wierzchołki któregoś z nich w kolejności \(\sigma_h^+\) lub \(\sigma_h^-.\) Ustawmy więc wierzchołki \(T_{h+2}\) w następującej kolejności: najpierw wierzchołki \(P_4\) w kolejności \(\sigma_h^-,\) potem \(v_2,\) następnie wierzchołki \(P_5\) w kolejności \(\sigma_h^+,\) wierzchołki \(P_6\) w kolejności \(\sigma_h^-,\) \(v_3,\) \(v_1,\) a na koniec wierzchołki \(P_7\) w kolejności \(\sigma_h^+\) (rys. 5). Nietrudno sprawdzić, że tak otrzymana kolejność \(\sigma_{h+2}^-\) spełnia tezę indukcyjną, to znaczy przekroje na lewo od \(v_1\) mają szerokość co najwyżej \(\big\lceil \frac{h + 2}{2} \big\rceil + 1,\) zaś te na prawo – co najwyżej \(\big\lceil \frac{h + 2}{2} \big\rceil.\)

Mając tak wzmocnioną tezę udowodnioną dla wszystkich \(h\) nieparzystych, nietrudno już udowodnić, że dla \(h\) parzystych również mamy permutację zaświadczającą, że szerokość

przekroju \(T_h\) wynosi co najwyżej \(\big\lceil \frac{h}{2}\big\rceil + 1.\) Odpowiednią konstrukcję przedstawia rysunek na marginesie, a szczegóły pozostawiamy jako zadanie dla Czytelnika.

W ten sposób problem listonosza w korporacji został rozwiązany. Zachęcamy do pomyślenia, jak dużej torby będzie potrzebował listonosz w jeszcze innych sytuacjach, np. gdy graf pokazujący komunikowanie się mieszkańców w miasteczku jest cyklem albo pełnym grafem dwudzielnym.

Na koniec dodajmy, że w teorii grafów rozważa się wiele różnych parametrów nazywanych ogólnie szerokościami grafowymi. Typowo z każdym takim parametrem wiąże się pewna dekompozycja i jeśli graf ma małą wartość parametru, to możemy znaleźć odpowiednio prostą dekompozycję. Cutwidth jest uznawany za jeden z najbardziej podstawowych parametrów tego typu – dekompozycja to liniowe ułożenie wierzchołków grafu i jest ona prosta, jeśli przez każdy jej przekrój przechodzi mało krawędzi.

Inne przykłady szerokości grafowych na pewno pojawią się jeszcze nie raz w Delcie – przyp. red.