Matematyka dyskretna 1/Wykład 13: Grafy II

Grafy eulerowskie

Leonhard Euler stanął przed następującym problemem. W Królewcu (wówczas K{o}nigsbergu) na rzece Pregole, na której są dwie wyspy wybudowano siedem mostów łączące wyspy ze sobą, oraz z oboma brzegami rzeki. Układ mostów został przedstawiony na rysunku Uzupelnic pict mosty Krolewcu|.

{grafy_mosty_krolewca} {Mapa mostów w Królewcu. [Rysunek z pliku: grafymostykrolewca.eps]}

Pytanie, jakie zostało postawione Eulerowi, to czy można tak ułożyć spacer po wszystkich mostach Królewca, by po każdym przejść tylko raz i wrócić do punktu startowego. Euler oczywiście odpowiedział na zadane mu pytanie. Postaramy się rozwiązać Zagadnienie Mostów Królewieckich. Zacznijmy od przedstawienia powyższego problemu w języku grafów. Niech każdy spójny kawałek lądu w Królewcu odpowiada wierzchołkowi. Otrzymamy w ten sposób dwa wierzchołki odpowiadające wyspom oraz dwa obu brzegom Pregoły. Most pomiędzy dwoma kawałkami lądu będziemy interpretować jako krawędź łączącą wierzchołki odpowiadające tym skrawkom lądu. W ten sposób otrzymamy następujący graf (nie będący grafem prostym):

{grafy_graf_krolewca} {Mapa mostów w Królewcu. [Rysunek z pliku: grafygrafkrolewca.eps]}

Naszym celem jest skonstruowanie specjalnego cyklu w grafie z rysunku Uzupelnic pict graf Krolewcu|.

Cykl Eulera to zamknięta marszruta przechodząca przez każdą krawędź grafu dokładnie raz.

Graf eulerowski to graf posiadający cykl Eulera.

{grafy_eulerowskie} {Przykład grafu eulerowskiego (a) i nieeulerowskiego (b) [Rysunek z pliku: grafyeulerowskie.eps]}

Graf na rysunku Uzupelnic pict grafy eulerowskie|a posiada cykl Eulera $x\to u\to z\to y\to u\to z\to y\to x$, zaś graf w części b. nie jest eulerowski, bo jeżeli wejdzie się do wierzchołka $v$, to już nie będzie można z niego wyjść; jeśli zaś rozpoczęlibyśmy naszą marszrutę z wierzchołka $v$ to nie będzie można doń powrócić.

Grafy eulerowskie posiadają ładną charakterystykę umożliwiającą prostą i szybką weryfikację omawianej własności.

Twierdzenie 1

Graf $\mathbf{𝐆}=(V,E)$ jest eulerowski wtedy i tylko wtedy, gdy jest spójny i stopień każdego wierzchołka jest parzysty.

Dowód

Załóżmy najpierw, że $\mathbf{𝐆}$ jest eulerowski i niech $E$ jakimś jego cyklem Eulera. Poruszając się po $\mathbf{𝐆}$ wzdłuż cyklu $E$ zliczajmy stopniowo używane krawędzie incydentne do poszczególnych wierzchołków. Zawsze po wejściu i wyjściu z danego wierzchołka $v$ liczba policzonych krawędzi incydentnych z $v$ zwiększy się o $2$. Tak więc, jeśli $v$ nie jest początkiem cyklu, to zawsze będzie miał parzystą liczbę aktualnie policzonych krawędzi incydentnych. Początek cyklu zaś, dopóki nie przeszliśmy ostatnią krawędzią grafu (która oczywiście prowadzi do niego) będzie miał nieparzystą liczbę policzonych krawędzi. Po użyciu jednak tej ostatniej krawędzi okaże się, że i on ma parzysty stopień. Żadna krawędź nie zostanie pominięta, ani policzona wielokrotnie, bo przeczyłoby to eulerowskości cyklu $E$ lub spójności grafu $\mathbf{𝐆}$.

Dla dowodu implikacji odwrotnej, pokażmy najpierw, że jeżeli w skończonym grafie $\mathbf{𝐆}$ dowolny wierzchołek ma parzysty stopień, to $\mathbf{𝐆}$ posiada cykl. Istnienie takiego cyklu pokażemy wskazując jego kolejne krawędzie. Zaczynamy od dowolnie wybranej krawędzi $v_0{v}_1$. Następnie przechodzimy do jakiejkolwiek innej krawędzi wychodzącej z wierzchołka $v_1$. Załóżmy, że była to krawędź $v_1{v}_2$. Wybieramy następnie dowolną różną od $v_1{v}_2$ krawędź wychodzącą z $v_2$. Czynność tę powtarzamy tak długo, aż dojdziemy do jakiegoś wierzchołka $v_i$, który został już wcześniej odwiedzony. W ten sposób otrzymamy cykl $v_i\to v_{i+1}\to \dots \to v_k\to v_i$. Jedynym problemem mógłby, w jakimś momencie, być brak możliwości kontynuowania marszu zanim dojdziemy do odwiedzonego wcześniej punktu $v_i$. Sytuacja taka nie jest jednak możliwa, gdyż oznaczałoby to istnienie wierzchołka o incydentnego z jedną tylko krawędzią (wejściową), co stoi w sprzeczności z parzystością jego stopnia.

Teraz możemy przejść do dowodu Twierdzenia, który przeprowadzimy indukcyjnie ze względu na liczbę krawędzi w grafie $\mathbf{𝐆}$. Jak już zauważyliśmy powyżej, graf $\mathbf{𝐆}$ posiada jakiś cykl $C$. Usuńmy z grafu $\mathbf{𝐆}$ krawędzie i wierzchołki cyklu $C$ otrzymując w ten sposób mniejszy graf ${\mathbf{𝐆}}^{\prime }$. Graf ${\mathbf{𝐆}}^{\prime }$ może już nie być spójny, ale nadal będzie posiadał jedynie wierzchołki parzystego stopnia. Jeżeli ${\mathbf{𝐆}}^{\prime }$ jest pusty, to cykl $C$ jest cyklem Eulera, co kończyłoby dowód. W przeciwnym razie, w każdej spójnej składowej grafu ${\mathbf{𝐆}}^{\prime }$ nie będącej punktem izolowanym, korzystając z założenia indukcyjnego, znajdujemy cykle Eulera $E_1,\dots E_l$. Ponieważ graf $\mathbf{𝐆}$ był spójny, to cykl $C$ musi przechodzić przez jakiś wierzchołek każdego cyklu $E_1,\dots E_l$. Tak więc cykl Eulera dla grafu $\mathbf{𝐆}$ możemy wyznaczyć w ten sposób, że przechodząc przez cykl $C$, za każdym razem gdy napotkamy nieodwiedzony jeszcze cykl $E_i$, zbaczamy z cyklu $C$ i przechodzimy w całości $E_i$, a później kontynuujemy wędrówkę po cyklu $C$. W konsekwencji przejdziemy po wszystkich krawędziach, każdą odwiedzając jedynie raz.

Bogatsi o nowo zdobytą wiedzę możemy już negatywnie odpowiedzieć na pytanie postawione Leonhardowi Euler'owi.

Analizując dowód Twierdzenia Uzupelnic th Euler| dostajemy następujący wniosek.

Wniosek 2

Graf spójny jest eulerowski wtedy i tylko wtedy, gdy rodzinę jego krawędzi da się podzielić na rozłączne krawędziowo cykle.

Z grafami eulerowskimi ściśle związane są grafy, które można narysować bez odrywania ołówka i rysując każdą krawędź dokładnie raz.

Graf jednokreślny to graf posiadający marszrutę przechodzącą dokładnie raz przez każdą krawędź.

Wniosek 3

Graf $\mathbf{𝐆}=(V,E)$ jest jednokreślny wtedy i tylko wtedy, gdy jest spójny i jego wszystkie, poza co najwyżej dwoma wierzchołkami, mają parzysty stopień.

Dowód

Jeśli $\mathbf{𝐆}$ jest jednokreślny, i marszruta przechodząca przez każda krawędź jest cyklem, to $\mathbf{𝐆}$ jest eulerowski i wobec Twierdzenia Uzupelnic th Euler| ma jedynie wierzchołki o parzystym stopniu. Jeśli zaś marszruta ta nie jest cyklem, to oczywiście wszystkie wierzchołki poza początkowym i końcowym mają parzysty stopień.

Na odwrót, jeśli w grafie $\mathbf{𝐆}$ wszystkie wierzchołki mają parzysty stopień, to $\mathbf{𝐆}$ jest eulerowski, a zatem jednokreślny. Jeśli zaś $\mathbf{𝐆}$ ma wierzchołki o nieparzystym stopniu, to -- wobec naszego założenia, może ich mieć dokładnie dwa, bo może mieć jedynie parzyście wiele wierzchołków o nieparzystym stopniu. Łącząc teraz te dwa wierzchołki nową krawędzią, dostajemy graf ${\mathbf{𝐆}}^{\prime }$, w którym już wszystkie wierzchołki mają parzysty stopień. A zatem ${\mathbf{𝐆}}^{\prime }$ posiada cykl Eulera $E$. Cykl ten przechodzi oczywiście przez nowo dodana krawędź. Usuwając ją z cyklu $E$ dostajemy marszrutę w grafie $\mathbf{𝐆}$, świadcząca o jego jednokreślności.

Grafy hamiltonowskie

Inny, ciekawy problem można przedstawić na przykadzie firmy rozwożącej przesyłki. Dotyczy on pracy kuriera mającego rozwieść przesyłki do odbiorców, w ten sposób by odwiedzić każdego klienta jedynie raz, a na końcu wrócić do siedziby firmy. Załóżmy, że na przesyłki czeka następujący zbiór osób: Henryk, Elżbieta, Maciej, Jan, Ula, Izabela, Gabriela, oraz Maria. Niestety, jak widać z rysunku Uzupelnic pict grafy komiwojazer|, nie ma połączeń umożliwiających przejazd między dowolnymi dwoma klientami.

{grafy_komiwojazer} {Graf połączeń między klientami firmy kurierskiej. [Rysunek z pliku: grafykomiwojazer.eps]}

Zachodzi pytanie, czy kurier mimo to jest w stanie wykonać swoje zadanie. Jeśli prześledzimy warunki nałożone na trasę swojej wędrówki okaże się, że szukamy tzw. cyklu Hamiltona.

Cykl Hamiltona to cykl przechodzący przez wszystkie wierzchołki grafu (czyli marszruta zamknięta odwiedzająca każdy wierzchołek dokładnie raz).

Graf hamiltonowski to graf posiadający cykl Hamiltona.

Ścieżka Hamiltona to ścieżka przechodząca przez wszystkie wierzchołki, każdy odwiedzając jedynie jeden raz.

W odróżnieniu od grafów eulerowskich, grafy hamiltonowskie nie posiadają prostej i szybkiej w użyciu charakteryzacji. Nie znana jest żadna metoda, pozwalająca szybko (tzn. w czasie wielomianowym) stwierdzić czy dany graf jest hamiltonowski. Są natomiast znane pewne warunki wystarczające na to, by graf był hamiltonowski. Jednym z ciekawszych takich warunków wystarczających jest warunek wykorzystujący jedynie stopnie wierzchołków. Przedstawiony jest w postaci następującego twierdzenia.

Twierdzenie 4 [Ore 1960]

Jeśli w grafie prostym $\mathbf{𝐆}=(V,E)$ o co najmniej $3$ wierzchołkach dowolne dwa niesąsiednie wierzchołki $v$ i $w$ spełniają $\mathrm{deg}v+\mathrm{deg}w\ge \left|V\right|$, to graf $\mathbf{𝐆}$ jest hamiltonowski.

Dowód

Dla dowodu niewprost załóżmy, że pewien niehamiltonowski graf $\mathbf{𝐆}$ o $n$ wierzchołkach spełnia (*) $\mathrm{deg}v+\mathrm{deg}w\ge n$, dla niesąsiednich wierzchołków $v,w$.

Dodawanie krawędzi do $\mathbf{𝐆}$ nie psuje warunku (*), więc do grafu $\mathbf{𝐆}$ można dokładać krawędzie tak długo, jak długo jest on niehamiltonowski. Możemy więc dodatkowo założyć, że $\mathbf{𝐆}$ ma tę własność, że po dodaniu jakiejkolwiek krawędzi otrzymamy już cykl Hamiltona. Tak więc w $\mathbf{𝐆}$ musi istnieć ścieżka Hamiltona $v_0\to v_1\to \dots \to v_{n-1}\to v_n$.

Wierzchołek $v_0$ ma, poza wierzchołkiem $v_1$, dodatkowo $\mathrm{deg}{v}_0-1$ sąsiadów. Oznaczmy ich przez $v_{i_1},\dots ,v_{i_{\mathrm{deg}{v}_0-1}}$. Z kolei, na mocy (*), wierzchołek $v_n$ w zbiorze $\{v_2,\dots ,v_{n-2}\}$ ma $\mathrm{deg}{v}_n-1>(n-3)-(\mathrm{deg}{v}_0-1)$ sąsiadów. To gwarantuje, że $v_n$ jest sąsiadem któregoś z $\mathrm{deg}{v}_0-1$ wierzchołków $v_{i_1-1},\dots ,v_{i_{\mathrm{deg}{v}_1-1}-1}$. Istnieje więc takie miejsce $j$ w ścieżce $v_0\to v_1\to \dots \to v_{n-1}\to v_n$, że $v_1$ jest incydentny z $v_j$, zaś $v_n$ z $v_{j-1}$.

{grafy_ore} {Cykl Hamiltona w grafie $\mathbf{𝐆}$. [Rysunek z pliku: grafyore.eps]}

Tak więc cykl $v_1\to v_j\to v_{j+1}\to \dots \to v_n\to v_{j-1}\to v_{j-2}\to \dots \to v_1$ jest cyklem Hamiltona w grafie $\mathbf{𝐆}$, co w konsekwencji daje sprzeczność z faktem, że $\mathbf{𝐆}$ miał nie być hamiltonowski.

Twierdzenie Ore'a jest uogólnieniem silniejszego warunku znalezionego parę lat wcześniej przez Dirac'a.

Wniosek 5 [G. A. Dirac 1952]

Graf prosty $\mathbf{𝐆}=(V,E)$, w którym każdy wierzchołek ma stopień co najmniej $\left|V\right|/2$ jest hamiltonowski.

Wróćmy teraz do przykładu o kurierze. Licząc stopnie wierzchołków w grafie z rysunku Uzupelnic pict grafy komiwojazer| i używając Twierdzenia Ore'a możemy stwierdzić, że graf ten ma cykl Hamiltona. Tak więc kurier, nie bojąc się utraty pracy, może spokojnie spełnić swoje zadanie.

Grafy dwudzielne i skojarzenia

Przypomnijmy, że:

Graf dwudzielny to graf $\mathbf{𝐆}=(V,E)$, w którym zbiór wierzchołków $V$ da się podzielić na dwa rozłączne podzbiory $V_1$ oraz $V_2$ tak, by żadne dwa wierzchołki w obrębie tego samego podzbioru $V_i$ nie były sąsiadami. Czasem, dla podkreślenia takiego podziału, graf dwudzielny będziemy oznaczać przez $(V_1\cup V_2,E)$. Zauważmy jednak, że podział taki nie jest jednoznaczny -- np. w antyklice ${{𝒜}}_n$ dowolny podział zbioru wierzchołków na dwa podzbiory jest podziałem dwudzielnym.

Twierdzenie 6

Graf jest dwudzielny wtedy i tylko wtedy, gdy każdy jego cykl ma parzystą długość.

Dowód

Załóżmy najpierw, że graf $\mathbf{𝐆}=(V,E)$ jest dwudzielny czyli, że $V$ można podzielić na dwa rozłączne zbiory wierzchołków $V_1$ oraz $V_2$, w ten sposób, że podgrafy indukowane $\mathbf{𝐆}{|}_{V_i}$ są antyklikami. Rozważmy cykl $v_1\to v_2\to \dots \to v_{k-1}\to v_k\to v_1$ o $k$ elementach. Bez straty ogólności możemy załóżyć, że $v_1\in V_1$. Ponieważ pomiędzy wierzchołkami z $V_1$ nie ma krawędzi, to $v_2\in V_2$. Z kolei $v_3\in V_1$, a $v_4\in V_2$ i tak dalej. Tak więc każdy $v_i$ o nieparzystym indeksie $i$ należy do $V_1$. W konsekwencji $v_k$ musi mieć parzysty indeks $k$, aby mógł być połączony z $v_1$. W rezultacie otrzymujemy, że cykle muszą być parzystej długości.

Dowód odwrotnej implikacji przeprowadzimy najpierw przy założeniu, że graf $\mathbf{𝐆}$ jest spójny. Naszym celem jest takie podzielenie $V$ na dwa zbiory wierzchołków $V_1,V_2$, by, dla $i=1,2$, żadne dwa wierzchołki z $V_i$ nie były ze sobą połączone. Wybierzmy z $V$ dowolny wierzchołek $v$. Niech $V_1$ będzie zbiorem, do którego należy $v$ oraz wszystkie wierzchołki, do których można dojść z $v$ ścieżką parzystej długości, zaś $V_2$ niech składa się z pozostałych wierzchołków. Załóżmy, że $u_1,u_2\in V_1$. Wtedy oczywiście istnieją ścieżki $v\to \dots \to u_1$ oraz $u_2\to \dots \to v$ o parzystej długości. Gdyby $u_1,u_2$ były połączone krawędzią, to dostalibyśmy cykl $v\to \dots \to u_1\to u_2\to \dots \to v$ o nieparzystej długości. A zatem $\mathbf{𝐆}{|}_{V_1}$ jest antykliką. Aby zobaczyć, że również $\mathbf{𝐆}{|}_{V_2}$ jest antykliką, wystarczy zauważyć że $V_2$ składa się z tych wierzchołków grafu $\mathbf{𝐆}$, do których z początkowo wybranego wierzchołka $v$ można dojść jedynie ścieżkami nieparzystej długości. Teraz uzasadnienie, że także $V_2$ indukuje antyklikę jest analogiczne jak dla $V_1$.

Niech teraz graf $\mathbf{𝐆}$ ma $l>1$ spójnych składowych $C_1,\dots ,C_l$. Wtedy każdą spójną składową $C_i$ możemy podzielić na zbiory $C_i^1,C_i^2$ świadczące o dwudzielności grafu indukowanego ${\mathbf{𝐆}}_{C_i}$. W konsekwencji daje to podział $V$ na $C_1^1\cup \dots \cup C_l^1$ oraz $C_1^2\cup \dots \cup C_l^2$ świadczący o dwudzielności całego grafu $\mathbf{𝐆}$.

Z grafami dwudzielnymi związany jest problem biura matrymonialnego. Do biura matrymonialnego zgłaszają się mężczyźni i kobiety poszukujący swojej drugiej połowy. Niestety nie każdemu mężczyźnie odpowiada każda kobieta i na odwrót. A więc każdy zgłaszający podaje swój opis, jak i wymagania stawiane potencjalnemu partnerowi. Interpretując mężczyzn i kobiety jako wierzchołki grafu, w którym krawędzie łączą "mężczyznę" z "kobietą", jeśli nawzajem sobie odpowiadają, otrzymujemy dwudzielny graf ${\mathbf{𝐆}}_z(M,K)$ odpowiadający potencjalnym związkom. Biuro matrymonialne ku uciesze klientów (i maksymalizacji swojego zysku) chciałoby stworzyć jak najwięcej par. Optymalnie by było, gdyby nikt nie został samotny. Wtedy jednak musimy oczywiście założyć, że mężczyzn jest tyle samo co kobiet.

Skojarzenie w grafie dwudzielnym $\mathbf{𝐆}=(V_1\cup V_2,E)$ to podzbiór krawędzi Parser nie mógł rozpoznać (błąd składni): {\displaystyle M\subseteq{\sf E}\!\left(\mathbf{G}\right)} , w którym żadne dwie $v_1{v}_2,u_1{u}_2\in M$ nie wychodzą z tego samego wierzchołka.
Powiemy ponadto, że $v\in V_i$ jest skojarzony, jeśli istnieje $w\in V_{3-i}$ taki, że krawędź $vw$ należy do skojarzenia.

Pełne skojarzenie $V_1$ z $V_2$ w grafie dwudzielnym $\mathbf{𝐆}=(V_1\cup V_2,E)$ to skojarzenie, w którym każdy wierzchołek z $V_1$ jest skojarzony.

Naturalnym jest pytanie, kiedy istnieje pełne skojarzenie $V_1$ z $V_2$ w grafie dwudzielnym $\mathbf{𝐆}=(V_1\cup V_2,E)$. Odpowiedział na nie P. Hall. Użył do tego funkcji $\mathrm{\Phi }\left(A\right)$ zwracającej dla $A\subseteq V_1$ zbiór tych wierzchołków $V_2$, które są sąsiednie z przynajmniej jednym wierzchołkiem w $A$.

Twierdzenie 7 [O Skojarzeniach w Grafie Dwudzielnym, P. Hall 1935]

Niech $\mathbf{𝐆}=(V_1\cup V_2,E)$ będzie grafem dwudzielnym. Wówczas pełne skojarzenie $V_1$ z $V_2$ istnieje wtedy i tylko wtedy, gdy $\left|A\right|\le \left|\mathrm{\Phi }\left(A\right)\right|$ dla każdego podzbioru $A$ zbioru $V_1$.

Dowód

Dla dowodu nierówności $\left|A\right|\le \left|\mathrm{\Phi }\left(A\right)\right|$ załóżmy, że $M$ jest pełnym skojarzeniem. Elementy skojarzone z elementami zbioru $A$ muszą być oczywiście w $\mathrm{\Phi }\left(A\right)$. Z drugiej strony skojarzenie $M$ determinuje injekcję $A⟶\mathrm{\Phi }\left(A\right)$, skąd natychmiast $\left|A\right|\le \left|\mathrm{\Phi }\left(A\right)\right|$.

Dowód implikacji odwrotnej jest nieco trudniejszy. Przeprowadzimy go indukcyjnie ze względu na liczbę wierzchołków $n_1=\left|V_1\right|$. Dla $n_1=1$ nierówność $\left|V_1\right|\le \left|\mathrm{\Phi }\left(V_1\right)\right|$ gwarantuje, że jest co kojarzyć z jedynym wierzchołkiem w $V_1$. Załóżmy więc, że $n_1>1$ i rozważmy dwa przypadki:

1. Dowolny właściwy podzbiór $W$ zbioru wierzchołków $V_1$ posiada więcej sąsiadów niż jego moc, tzn. $\left|\mathrm{\Phi }\left(W\right)\right|>\left|W\right|$. Wtedy wybieramy dowolne wierzchołki $v_1\in V_1$ oraz $v_2\in V_2$ i je kojarzymy. Dla $W\subseteq V_1-\left\{v_1\right\}$ zbiór sąsiadów w zbiorze $V_2$ pomniejszonym o wybrany już $v_2$ jest nadal nie liczniejszy niż liczność $\left|W\right|$. Założenie indukcyjne gwarantuje nam więc jakieś skojarzenie pełne $M$ zbioru $V_1-\left\{v_1\right\}$ z $V_2-\left\{v_2\right\}$ w grafie pozostałych wierzchołków $\mathbf{𝐆}{|}_{(V_1-\left\{v_1\right\})\cup (V_2-\left\{v_2\right\})}$. Oczywiście $M\cup v_1{v}_2$ jest poszukiwanym skojarzeniem pełnym w $\mathbf{𝐆}$.
2. Istnieje właściwy podzbiór $W$ zbioru $V_1$, taki że $\left|\mathrm{\Phi }\left(W\right)\right|=\left|W\right|$.

Ponieważ dla $A\subseteq W$ mamy $\mathrm{\Phi }\left(A\right)\subseteq \mathrm{\Phi }\left(W\right)$, to

$\left|A\right|\le \left|\mathrm{\Phi }\left(A\right)\right|=|\mathrm{\Phi }\left(A\right)\cap \mathrm{\Phi }\left(W\right)|.$

Ta nierówność pozwala użyć założenia indukcyjnego do skojarzenia wszystkich elementów ze zbioru $W$ z elementami należącymi do $\mathrm{\Phi }\left(W\right)$.

Wystarczy więc znaleźć skojarzenie pozostałych elementów, czyli skojarzenie zbioru $V_1-W$ ze zbiorem $V_2-\mathrm{\Phi }\left(W\right)$. Skojarzenie takie dostaniemy również indukcyjnie, o ile pokażemy, że dla dowolnego $A\subseteq V_1-W$, zbiór jego sąsiadów w $V_2-\mathrm{\Phi }\left(W\right)$ jest liczniejszy od $A$, tzn.

$\left|A\right|\le |\mathrm{\Phi }\left(A\right)-\mathrm{\Phi }\left(W\right)|.$

Załóżmy, że jakiś zbiór $A\subseteq V_1-W$ nie spełnia powyższej nierówności. Wtedy

$|A\cup W|=\left|A\right|\cup \left|W\right|>|\mathrm{\Phi }\left(A\right)-\mathrm{\Phi }\left(W\right)|+\left|\mathrm{\Phi }\left(W\right)\right|\ge \left|\mathrm{\Phi }(A\cup W)\right|,$

co przeczy założeniu twierdzenia, przy którym pracujemy.

Wielospójność

Zarówno drzewo, jak i klika są grafami spójnymi. W drzewie jednak, usunięcie jakiegokolwiek wierzchołka nie będącego liściem rozspaja go. Z drugiej strony, klika pozostaje spójna po usunięciu dowolnej liczby wierzchołków. Aby rozróżnić te różne rodzaje spójności rozważa się następujące uogólnienia spójności.

Graf $k$-spójny to graf, który po usunięciu dowolnie wybranych $k-1$ wierzchołków (i incydentnych z nimi krawędzi) pozostaje spójny.

Graf $k$-spójny krawędziowo to graf, który po usunięcie dowolnie wybranych $k-1$ krawędzi (bez usuwania wierzchołków) pozostaje spójny.

Przykład

• Grafy $1$-spójne lub $1$-spójne krawędziowo to po prostu grafy spójne.
• Drzewa są spójne, ale nie $2$-spójne i nie $2$-spójne krawędziowo.
• Klika ${{𝒦}}_n$ jest $n$-spójna i $n-1$-spójna krawędziowo.

Z pojęciami wielospójności związane są następujące pojęcia:

Zbiór rozdzielający wierzchołki $u,v$ to zbiór wierzchołków $S\subseteq V-\{u,v\}$ taki, że każda droga z $u$ do $v$ przechodzi przez któryś element ze zbioru $S$.

Ponadto powiemy, że $S$ jest zbiorem rozdzielającym, jeśli $S$ jest zbiorem rozdzielającym jakichś dwu wierzchołków $u,v$.

Zbiór rozspajający wierzchołki $u,v$ to zbiór krawędzi $F\subseteq E$ taki, że każda droga z $u$ do $v$ zawiera jakąś krawędź z $F$.

Rozcięcie wierzchołków $u,v$ to zbiór rozspajający wierzchołki $u,v$, którego żaden podzbiór właściwy nie rozspaja $u$ z $v$.
Zbiór krawędzi $F$ będziemy nazywać rozcięciem, jeśli $F$ jest rozcięciem jakichś dwu wierzchołków $u,v$

Most to taka krawędź $e$, że zbiór $\left\{e\right\}$ tworzy rozcięcie.

Uwaga

Jeżeli graf jest $k$-spójny, to każdy jego zbiór rozdzielający musi mieć co najmniej $k$ wierzchołków. Analogicznie jeśli $\mathbf{𝐆}$ jest $k$-spójny krawędziowo, to każde jego rozcięcie musi mieć co najmniej $k$ krawędzi.

{grafy_menger} { [Rysunek z pliku: grafymenger.eps]}

Przykład

Przykładowymi zbiorami rozdzielającymi wierzchołki $u,w$ w grafie z rysunku Uzupelnic pict Menger| są zbiory $\{x,y,z\}$ i $\{s,t\}$. Zbiory $\{xs,xy,ys,ys,zt\}$ jest rozspajający, a zbiór $\{xs,xy,uy,uz\}$ jest rozcięciem. Graf ten jest $2$-spójny oraz $2$-spójny krawędziowo.

Okazuje się, że dla dwu różnych wierzchołków istnieje powiązanie -- między wielkością rozcięcia, a liczbą dróg pomiędzy nimi -- silniejsze niż to wynikające z definicji.

Twierdzenie 8 [Menger 1927]

Największa możliwa liczba krawędziowo rozłącznych dróg łączących dwa różne niesąsiednie wierzchołki grafu spójnego, jest równa najmniejszej liczbie krawędzi w zbiorze rozspajającym te wierzchołki.

Dowód

Niech $w,u$ będą dwoma różnymi i niesąsiednimi wierzchołkami grafu spójnego $\mathbf{𝐆}=(V,E)$. Przez $k$ oznaczmy najmniejszą możliwą liczność zbioru krawędzi rozspajającego $w,u$. Oczywiście każda droga łącząca $w$ z $u$ musi przejść przez każdy zbiór rozspajający. A zatem dróg krawędziowo rozłącznych łączących $w$ z $u$ nie może być więcej niż $k$. Tak więc wystarczy pokazać, że istnieje $k$ rozłącznych krawędziowo dróg z $w$ do $u$.

Dowód przeprowadzimy indukcyjnie ze względu na liczbę krawędzi w grafie $\mathbf{𝐆}$ rozważając dwa przypadki.

1. Pewien zbiór rozspajający $X$ mocy $k$ ma krawędź nie incydentną z $w$ oraz ma krawędź (być może inną) nie incydentną z $u$.

Graf $G$, po usunięciu wszystkich krawędzi z $X$, podzieli się na dwie spójne składowe $W$ oraz $U$, do których odpowiednio należą $w$ i $u$.

{grafy_menger2} {W grafie z rysunku Uzupelnic pict Menger| odpowiednim rozspajającym zbiorem $X$ z przypadku 1, może być zbiór $\{xs,xy,uy,zt\}$ zaznaczonych liniami przerywanymi. [Rysunek z pliku: grafymenger2.eps]}

Przez ${\mathbf{𝐖}}^{\prime }$ oznaczmy graf powstały z grafu $\mathbf{𝐆}$ poprzez ściągnięcie $U$ w jeden wierzchołek $u^{\prime }$. Wtedy $u^{\prime }$ jest połączony z tymi wierzchołkami $t\in W$, z którymi połączony był jakiś wierzchołek $s\in U$. Warto zauważyć, że wtedy musiało być $st\in X$. Krawędzie łączące wierzchołki wewnątrz $W$ pozostały niezmienione. Graf ${\mathbf{𝐔}}^{\prime }$ definiujemy analogicznie, poprzez ściągnięcie zbioru $W$ do wierzchołka $w^{\prime }$.

{grafy_menger3} {Kontynuacja przykładu z rysunków Uzupelnic pict Menger| i Uzupelnic pict Menger2|. Pokazane są grafy ${\mathbf{𝐔}}^{\prime }$ (a) oraz ${\mathbf{𝐖}}^{\prime }$ (b). [Rysunek z pliku: grafymenger3.eps]}

W grafie ${\mathbf{𝐖}}^{\prime }$ zbiór krawędzi incydentnych z $u^{\prime }$, których jest $k$, tworzy minimalny zbiór rozspajający wierzchołki $w,u^{\prime }$. Ponieważ założyliśmy, że w $X$ istnieje krawędź nieincydentna z $u$, to $U$ ma co najmniej dwa wierzchołki, a zatem graf ${\mathbf{𝐖}}^{\prime }$ ma mniej krawędzi niż $\mathbf{𝐆}$. Tak więc możemy skorzystać z założenia indukcyjnego otrzymując $k$ rozłącznych krawędziowo dróg łączących $w$ z $u^{\prime }$. Analogicznie w grafie ${\mathbf{𝐔}}^{\prime }$ otrzymujemy $k$ rozłącznych krawędziowo dróg łączących $w^{\prime }$ z $u$. Sklejając obie te rodziny dróg otrzymujemy $k$ rozłącznych ścieżek łączących $w$ z $u$ w grafie $\mathbf{𝐆}$.

2. W każdym zbiorze rozspajającym $X$ o mocy $k$ każda krawędź jest incydentna do $w$ lub do $u$.

Możemy wtedy założyć, że $\mathbf{𝐆}$ zawiera jedynie krawędzie należące do któregoś zbioru rozspajającego $w,u$ o liczności $k$. Gdyby tak nie było i istniałaby jakaś inna krawędź $e$, to moglibyśmy $e$ usunąć i, na mocy założenia indukcyjnego, otrzymać natychmiast $k$ rozłącznych dróg łączących $w,u$. Tak więc pozostały nam jedynie te krawędzie, które są w minimalnych zbiorach rozspajających $w,u$. To zaś, zgodnie z założeniem przypadku 2 oznacza, że każda krawędź jest incydentna z $w$ lub z $u$. W ten sposób drugi przypadek sprowadziliśmy do sytuacji, w której każda ścieżka z $w$ do $u$ ma co najwyżej dwie krawędzie. Wśród takich ścieżek nietrudno jest już wskazać $k$ rozłącznych krawędziowo.

Jako ćwiczenie [ex][dowod twierdzenia wierzcholkowego Menger] pozostawiamy dowód twierdzenia analogicznego do Twierdzenia Uzupelnic th krawedziowe Menger|, a wiążącego tym razem zbiory rozdzielające z drogami rozłącznymi wierzchołkowo.

Twierdzenie 9

Największa możliwa liczba wierzchołkowo rozłącznych dróg łączących dwa różne niesąsiednie wierzchołki grafu spójnego, jest równa najmniejszej liczbie wierzchołków w zbiorze rozdzielającym te wierzchołki.

Z Twierdzenia Uzupelnic th Menger2| można w łatwy sposób wywnioskować Twierdzenie Uzupelnic th hall| o skojarzeniach w grafach dwudzielnych. Wyprowadzenie to pozostawiamy jako ćwiczenie {Menger=>Hall}.

W grafie $k$-spójnym usunięcie jakichś $k-1$ punktów nie rozspaja go. A zatem zbiór rozdzielający jakieś dwa wierzchołki $w,u$ ma co najmniej $k$ wierzchołków. Tym samym między $u$ a $w$ musi istnieć co najmniej $k$ dróg. Pisząc zwięźlej możemy powiedzieć, że:

Wniosek 10

Graf z co najmniej $k+1$ wierzchołkami jest $k$-spójny wtedy i tylko wtedy, gdy dowolne dwa wierzchołki są połączone przynajmniej $k$ drogami wierzchołkowo rozłącznymi.

Analogiczne rozumowanie przeprowadzone dla ścieżek rozłącznych krawędziowo prowadzi do następującego wniosku.

Wniosek 11

Graf z co najmniej $k-1$ krawędziami jest $k$-spójny krawędziowo wtedy i tylko wtedy, gdy dowolne dwa wierzchołki są połączone przynajmniej $k$ drogami krawędziowo rozłącznymi.

Przepływy i przekroje

Wyobraźmy sobie sieć wodociągową, składającą się z rur o zadanej przepustowości, przystosowanych do przesyłania wody w określonym z góry kierunku oraz ze zbiorników połączonych tymi rurami. W przedstawionej sieci dwa zbiorniki są wyróżnione. Jeden z nich to źródło, w którym jest umieszczona pompa wpompowująca wodę, oraz ujście, czyli klient firmy wodociągowej lubiący nad wyraz zużywać wodę. Zadaniem firmy wodociągowej jest dostarczanie jak największej ilości wody klientowi. Ilość przesyłanej wody konkretną rurą nie może oczywiście przekraczać jej przepustowości. Pytanie, na które chciałby sobie odpowiedzieć właściciel firmy doprowadzającej wodę, to ile maksymalnie wody jest w stanie przesyłać w każdej chwili do klienta. Formalnym modelem dla tego typu zagadnień są sieci.

Sieć to trójką Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{N}=\left( V, A, {\sf c} \right)} , w której:

• $(V,A)$ jest pełnym digrafem (czyli $A=V\times V$),
• funkcja Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf c}:E \longrightarrow [0,+\infty) } , zwana przepustowością sieci, każdej krawędzi $vw$ przypisuje nieujemną liczbę rzeczywistą Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf c}\!\left(vw\right)} .
• Ponadto wyróżnia się dwa wierzchołki $s,t\in V$, które są odpowiednio źródłem oraz ujściem sieci.

Przepustowość Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf c}(vw)} krawędzi $vw$ może być interpretowana jako wartość potencjalnie maksymalnego przepływu z wierzchołka $v$ do $w$. Jeśli przepustowość jakiejś krawędzi $e$ wynosi $0$, to krawędź $e$ jest pomijana w graficznym przedstawieniu sieci.

{grafy_siec} {Przykładowa sieć. [Rysunek z pliku: grafysiec.eps]}

Przepływ w sieci Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{N}=\left( V, A, {\sf c} \right)} to funkcja Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf f}:E \longrightarrow [0,+\infty)} spełniająca warunki:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0\leq{\sf f}\!\left(vw\right)\leq{\sf c}\!\left(vw\right)} dla każdej krawędzi $vw$. Wartość przepływu daną krawędzią nie może przekroczyć przepustowości tej krawędzi.
• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{x\in V}{\sf f}\!\left(xv\right)=\sum_{x\in V}{\sf f}\!\left(vx\right)} dla każdego wierzchołka $v$ poza źródłem $s$ i ujściem $t$. Równość ta oznacza, że sumaryczna wartość tego, co wpływa do wierzchołka jest równa sumarycznej wartości tego, co zeń wypływa.
• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{x\in V}\left( {\sf f}\!\left(sx\right)-{\sf f}\!\left(xs\right) \right)=\sum_{x\in V}\left( {\sf f}\!\left(xt\right)-{\sf f}\!\left(tx\right) \right)} , tzn. sumaryczna wartość tego, co wypływa ze źródła musi być równa sumarycznej wartości tego, co wpływa do ujścia. Wartość ta będzie określana wartością przepływu Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf f}} .

{grafy_przeplyw} {Przepływ w siei z rysunku Uzupelnic pict siec|. [Rysunek z pliku: grafyprzeplyw.eps]}

Do analizy przepływów przydatne okazuje się pojęcie przekroju sieci. Można go sobie wyobrażać jako zbiór krawędzi $X\subseteq A$, usunięcie których z sieci Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{N}=\left( V, A, {\sf c} \right)} rozspaja sieć na dwie części $S$ oraz $T$, przy czym $S$ zawiera źródło, a $T$ ujście. Warto zauważyć, że $X$ tworzy zbiór rozspajający w grafie szkieletowym digrafu $(V,A)$. Formalnie przekrój zdefiniujemy jako parę powstałych zbiorów wierzchołków. Taka definicja okaże się bardziej użyteczna w praktyce.

Przekrój sieci to para podzbiorów $(S,T)$ zbioru wierzchołków $V$, taka że:

• $S,T$ tworzą podział $V$, tzn. są rozłączne i w sumie dają cały zbiór $V$,
• źródło $s$ należy do $S$, a ujście $t$ należy do zbioru $T$.

Przepustowość przekroju $(S,T)$ to suma

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf c}\!\left(S,T\right)=\sum_{v\in S,\ w\in T}{\sf c}\!\left(vw\right). }

Zależność między przepływem a przekrojem została podana w następującym Twierdzeniu o maksymalnym przepływie i minimalnym przekroju.

Twierdzenie 12 [Ford i Fulkerson 1956]

W dowolnej sieci wartość maksymalnego przepływu jest równa przepustowości minimalnego przekroju.

Dowód

Niech Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{N}=\left( V, A, {\sf c} \right)} będzie siecią o źródle $s$ i ujściu $t$. Oczywiście wartość maksymalnego przepływu nie może przekraczać przepustowości minimalnego przekroju. Wystarczy więc wskazać przekrój, którego przepustowość równa się wartości maksymalnego przepływu Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf f}} w sieci $\mathbf{𝐍}$.

Niech $S\subseteq V$ będzie zbiorem zawierającym źródło $s$ oraz te wierzchołki $w$, które w grafie szkieletowym digrafu $(V,A)$ połączone są ze źródłem pewną ścieżką $s=v_1\to \dots \to v_k=w$, w której łuk $v_i{v}_{i+1}$ ma niepełny przepływ (tzn. Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf f}\!\left(v_i v_{i+1}\right)<{\sf c}\!\left(v_i v_{i+1}\right)} ) lub też łuk $v_{i+1}{v}_i$ ma niezerowy przepływ Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf f}\!\left(v_{i+1} v_i\right)>0} . W języku firmy wodociągowej $S$ jest zbiorem wierzchołków, do których można jeszcze przepchnąć choć trochę wody.

Załóżmy przez chwilę, że $t\in S$. Istnieje wtedy ścieżka $s=v_0\to \dots \to v_k=t$, w której dla każdej pary kolejnych wierzchołków $v_i,v_{i+1}$ można byłoby zwiększyć przepływ na łuku $v_i{v}_{i+1}$ lub zmniejszyć na łuku $v_{i+1}{v}_i$. Niech $\epsilon >0$ będzie jakąś wartością zmian przepływu możliwych do wykonania na każdej parze $v_i,v_{i+1}$ kolejnych wierzchołków ścieżki. Wtedy, modyfikując odpowiednio łuki pomiędzy wierzchołkami $v_i,v_{i+1}$ uzyskalibyśmy przepływ o wartości Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf f}+\epsilon} , co przeczy maksymalności przepływu Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf f}} .

Udowodniliśmy właśnie, że $S,T$ tworzy przekrój sieci $\mathbf{𝐍}$, gdzie $T=V-S$. Pokażmy, że przepustowość tego przekroju równa się wartości przepływu Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf f}} . Z definicji $S$ wynika, że jeżeli rozważymy dwa elementy $v\in S$ oraz $w\in T$, to przepływ Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf f}\!\left(vw\right)={\sf c}\!\left(vw\right)} oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf f}\!\left(wv\right)=0} .Tak więc przepustowość przekroju równa jest

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{v\in S,\ w\in T}{\sf c}\!\left(vw\right)=\sum_{v\in S,\ w\in T}\left( {\sf f}\!\left(vw\right)-{\sf f}\!\left(wv\right) \right). }

Z faktu, że dla $u\in S-\left\{s\right\}$ wartość tego co wpływa jest równa temu co wypływa, czyli innymi słowy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{x\in V}\left( {\sf f}\!\left(ux\right)-{\sf f}\!\left(xu\right) \right)=0, }

otrzymujemy następującą równość:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{x\in T}\left( {\sf f}\!\left(ux\right)-{\sf f}\!\left(xu\right) \right)= \sum_{x\in S-\left\lbrace u \right\rbrace}\left( {\sf f}\!\left(xu\right)-{\sf f}\!\left(ux\right) \right). }

Prawą stronę równości (Uzupelnic eq grafy_ford_fulkerson|) można więc przekształcić w następujący sposób:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \sum_{v\in S}\sum_{w\in T}\left( {\sf f}\!\left(vw\right)-{\sf f}\!\left(wv\right) \right) &=&\sum_{v\in S-\left\lbrace u \right\rbrace}\sum_{w\in T}\left( {\sf f}\!\left(vw\right)-{\sf f}\!\left(wv\right) \right)+\sum_{x\in T}\left( {\sf f}\!\left(ux\right)-{\sf f}\!\left(xu\right) \right)\\ &=&\sum_{v\in S-\left\lbrace u \right\rbrace}\sum_{w\in T}\left( {\sf f}\!\left(vw\right)-{\sf f}\!\left(wv\right) \right)+\sum_{x\in S-\left\lbrace u \right\rbrace}\left( {\sf f}\!\left(xu\right)-{\sf f}\!\left(ux\right) \right)\\ &=&\sum_{v\in S-\left\lbrace u \right\rbrace}\sum_{w\in T\cup\left\lbrace u \right\rbrace}\left( {\sf f}\!\left(vw\right)-{\sf f}\!\left(wv\right) \right) \endaligned}

Powtarzając wielokrotnie przekładanie kolejnych punktów $u$ z $S$ do $T$ otrzymamy w konsekwencji

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{v\in S}\sum_{w\in T}\left( {\sf f}\!\left(vw\right)-{\sf f}\!\left(wv\right) \right)=\sum_{w\in V-\left\lbrace v \right\rbrace}\left( {\sf f}\!\left(sw\right)-{\sf f}\!\left(ws\right) \right), }

co na mocy (Uzupelnic eq grafy_ford_fulkerson|) oznacza, że wartość przepływu z wierzchołka $s$ do wierzchołka $t$ jest równa przepustowości przekroju wyznaczonego przez zbiory $S,T$.