Oszczędny listonosz

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)=\underset{\sigma \in {\mathrm{\Sigma }}_n}{min}\underset{1\le k\le n}{max}|\{(v_{\sigma (i)},v_{\sigma (j)})\in E:i\le k<j\}|,$$ gdzie ${\mathrm{\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\ge 2$ zachodzi $c(T_h)=\lceil \frac{h}{2}\rceil +1.$

Aby wykazać powyższą równość, zaczniemy od udowodnienia $c(T_h)\ge \lceil \frac{h}{2}\rceil +1$ dla $h\ge 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)}.$

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)\ge \lceil \frac{h}{2}\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 }^{\mathrm{\perp }}$ prostopadła do $\ell$ będzie przecięta przez co najmniej $\lceil \frac{h}{2}\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 }^{\mathrm{\perp }}$ przecina też pewna krawędź z tej ścieżki, czyli łącznie co najmniej $\lceil \frac{h}{2}\rceil +2=\lceil \frac{h+2}{2}\rceil +1$ krawędzi, co należało udowodnić.

Teraz trzeba jeszcze znaleźć dla każdego $h\ge 2$ taką permutację ${\sigma }_h$ wierzchołków $T_h,$ która zaświadcza, że szerokość przekroju $T_h$ faktycznie wynosi co najwyżej $\lceil \frac{h}{2}\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 $\lceil \frac{h}{2}\rceil +1,$ zaś każdy przekrój na prawo od korzenia ma szerokość co najwyżej $\lceil \frac{h}{2}\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 $\lceil \frac{h}{2}\rceil +1,$ zaś każdy przekrój na lewo od korzenia co najwyżej $\lceil \frac{h}{2}\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 $\lceil \frac{h+2}{2}\rceil +1,$ zaś te na prawo – co najwyżej $\lceil \frac{h+2}{2}\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 $\lceil \frac{h}{2}\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.