Matematyka dyskretna 1/Wykład 13: Grafy II

From Studia Informatyczne

Spis treści

Grafy eulerowskie

Leonhard Euler stanął przed następującym problemem. W Królewcu (wówczas Konigsbergu) 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:



Mapa mostów w Królewcu

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):



Mapa mostów w Królewcu

Naszym celem jest skonstruowanie specjalnego cyklu w grafie z rysunku Mapa mostów w Królewcu.



Przykład grafu eulerowskiego (a) i nieeulerowskiego (b)

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.

Graf na rysunku Grafy eulerowskie 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 13.1

Graf \mathbf{G}=\left( V,E \right) 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{G} jest eulerowski i niech E jakimś jego cyklem Eulera. Poruszając się po \mathbf{G} 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{G}.

Dla dowodu implikacji odwrotnej, pokażmy najpierw, że jeżeli w skończonym grafie \mathbf{G} dowolny wierzchołek ma parzysty stopień, to \mathbf{G} 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 \ldots\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{G}. Jak już zauważyliśmy powyżej, graf \mathbf{G} posiada jakiś cykl C. Usuńmy z grafu \mathbf{G} krawędzie i wierzchołki cyklu C otrzymując w ten sposób mniejszy graf \mathbf{G}'. Graf \mathbf{G}' może już nie być spójny, ale nadal będzie posiadał jedynie wierzchołki parzystego stopnia. Jeżeli \mathbf{G}' 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{G}' nie będącej punktem izolowanym, korzystając z założenia indukcyjnego, znajdujemy cykle Eulera E_1,\ldots E_l. Ponieważ graf \mathbf{G} był spójny, to cykl C musi przechodzić przez jakiś wierzchołek każdego cyklu E_1,\ldots E_l. Tak więc cykl Eulera dla grafu \mathbf{G} 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.

image:End_of_proof.gif

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

Analizując dowód Twierdzenia 13.1 dostajemy następujący wniosek.

Wniosek 13.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 13.3

Graf \mathbf{G}=\left( V,E \right) 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{G} jest jednokreślny, i marszruta przechodząca przez każda krawędź jest cyklem, to \mathbf{G} jest eulerowski i wobec Twierdzenia 13.1 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{G} wszystkie wierzchołki mają parzysty stopień, to \mathbf{G} jest eulerowski, a zatem jednokreślny. Jeśli zaś \mathbf{G} 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{G'}, w którym już wszystkie wierzchołki mają parzysty stopień. A zatem \mathbf{G'} 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{G}, świadcząca o jego jednokreślności.

image:End_of_proof.gif

Grafy hamiltonowskie



Graf połączeń między klientami firmy kurierskiej

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, nie ma połączeń umożliwiających przejazd między dowolnymi dwoma klientami.

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 13.4 [Ore 1960]

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



Cykl Hamiltona w grafie \mathbf{G}

Dowód

Dla dowodu niewprost załóżmy, że pewien niehamiltonowski graf \mathbf{G} o n wierzchołkach spełnia

(*) \deg{v}+\deg{w}\geq n, dla niesąsiednich wierzchołków v,w.

Dodawanie krawędzi do \mathbf{G} nie psuje warunku (*), więc do grafu \mathbf{G} 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{G} ma tę własność, że po dodaniu jakiejkolwiek krawędzi otrzymamy już cykl Hamiltona. Tak więc w \mathbf{G} musi istnieć ścieżka Hamiltona v_0\to v_1\to\ldots\to v_{n-1}\to v_n.

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

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

image:End_of_proof.gif

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

Wniosek 13.5 [G. A. Dirac 1952]

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

Wróćmy teraz do przykładu o kurierze. Licząc stopnie wierzchołków w grafie z rysunku 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{G}=\left( V,E \right), 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 \left( V_1\cup V_2,E \right). Zauważmy jednak, że podział taki nie jest jednoznaczny - np. w antyklice \mathcal{A}_{n} dowolny podział zbioru wierzchołków na dwa podzbiory jest podziałem dwudzielnym.

Twierdzenie 13.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{G}=\left( V,E \right) 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{G}|_{V_i} są antyklikami. Rozważmy cykl v_1\to v_2\to\ldots\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{G} 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\ldots\to u_1 oraz u_2\to\ldots\to v o parzystej długości. Gdyby u_1,u_2 były połączone krawędzią, to dostalibyśmy cykl v\to\ldots\to u_1\to u_2\to\ldots\to v o nieparzystej długości. A zatem \mathbf{G}|_{V_1} jest antykliką. Aby zobaczyć, że również \mathbf{G}|_{V_2} jest antykliką, wystarczy zauważyć że V_2 składa się z tych wierzchołków grafu \mathbf{G}, 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{G} ma l>1 spójnych składowych C_1,\ldots,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{G}_{C_i}. W konsekwencji daje to podział V na C_1^1\cup\ldots\cup C_l^1 oraz C_1^2\cup\ldots\cup C_l^2 świadczący o dwudzielności całego grafu \mathbf{G}.

image:End_of_proof.gif

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{G}_z\left( M,K \right) 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{G}=\left( V_1\cup V_2,E \right) to podzbiór krawędzi 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{G}=\left( V_1\cup V_2,E \right) 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{G}=\left( V_1\cup V_2, E \right). Odpowiedział na nie P. Hall. Użył do tego funkcji \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 13.7 [O Skojarzeniach w Grafie Dwudzielnym, P. Hall 1935]

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

Dowód

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

Dowód implikacji odwrotnej jest nieco trudniejszy. Przeprowadzimy go indukcyjnie ze względu na liczbę wierzchołków n_1=\left\vert V_1 \right\vert. Dla n_1=1 nierówność \left\vert V_1 \right\vert \leq\left\vert \Phi\!\left(V_1\right) \right\vert 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\vert \Phi\!\left(W\right) \right\vert>\left\vert W \right\vert. 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\lbrace v_1 \right\rbrace zbiór sąsiadów w zbiorze V_2 pomniejszonym o wybrany już v_2 jest nadal nie liczniejszy niż liczność \left\vert W \right\vert. Założenie indukcyjne gwarantuje nam więc jakieś skojarzenie pełne M zbioru V_1-\left\lbrace v_1 \right\rbrace z V_2-\left\lbrace v_2 \right\rbrace w grafie pozostałych wierzchołków \mathbf{G}|_{(V_1-\left\lbrace v_1 \right\rbrace)\cup(V_2-\left\lbrace v_2 \right\rbrace)}. Oczywiście M\cup{v_1v_2} jest poszukiwanym skojarzeniem pełnym w \mathbf{G}.
2. Istnieje właściwy podzbiór W zbioru V_1, taki że \left\vert \Phi\!\left(W\right) \right\vert=\left\vert W \right\vert.

Ponieważ dla A\subseteq W mamy \Phi\!\left(A\right)\subseteq \Phi\!\left(W\right), to


\left\vert A \right\vert\leq\left\vert \Phi\!\left(A\right) \right\vert=\left\vert \Phi\!\left(A\right)\cap\Phi\!\left(W\right) \right\vert.


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

Wystarczy więc znaleźć skojarzenie pozostałych elementów, czyli skojarzenie zbioru V_1- W ze zbiorem V_2- \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- \Phi\!\left(W\right) jest liczniejszy od A, tzn.


\left\vert A \right\vert\leq\left\vert \Phi\!\left(A\right)-\Phi\!\left(W\right) \right\vert.


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


\left\vert A\cup W \right\vert =\left\vert A \right\vert\cup\left\vert W \right\vert >\left\vert \Phi\!\left(A\right)-\Phi\!\left(W\right) \right\vert+\left\vert \Phi\!\left(W\right) \right\vert \geq\left\vert \Phi\!\left(A\cup W\right) \right\vert,


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

image:End_of_proof.gif

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 \mathcal{K}_{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- \left\lbrace u,v \right\rbrace 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\lbrace e \right\rbrace 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{G} jest k-spójny krawędziowo, to każde jego rozcięcie musi mieć co najmniej k krawędzi.



Grafy menger



W grafie z rysunku Grafy menger odpowiednim rozspajającym zbiorem X z przypadku 1, może być zbiór \left\lbrace xs,xy,uy,zt \right\rbrace zaznaczonych liniami przerywanymi


Kontynuacja przykładu z rysunku Grafy menger i rysunku z liniami przerywanymi. Pokazane są grafy \mathbf{U}' (a) oraz \mathbf{W}' (b)

Przykład

Przykładowymi zbiorami rozdzielającymi wierzchołki u,w w grafie z rysunku Grafy menger są zbiory \left\lbrace x,y,z \right\rbrace i \left\lbrace s,t \right\rbrace. Zbiory \left\lbrace xs,xy,ys,ys,zt \right\rbrace jest rozspajający, a zbiór \left\lbrace xs,xy,uy,uz \right\rbrace 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 13.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{G}=\left( V,E \right). 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{G} 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.

Przez \mathbf{W}' oznaczmy graf powstały z grafu \mathbf{G} poprzez ściągnięcie U w jeden wierzchołek u'. Wtedy u' 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{U}' definiujemy analogicznie, poprzez ściągnięcie zbioru W do wierzchołka w'.

W grafie \mathbf{W}' zbiór krawędzi incydentnych z u', których jest k, tworzy minimalny zbiór rozspajający wierzchołki w,u'. 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{W}' ma mniej krawędzi niż \mathbf{G}. 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'. Analogicznie w grafie \mathbf{U}' otrzymujemy k rozłącznych krawędziowo dróg łączących w' z u. Sklejając obie te rodziny dróg otrzymujemy k rozłącznych ścieżek łączących w z u w grafie \mathbf{G}.

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{G} 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.

image:End_of_proof.gif

Jako ćwiczenie 9 pozostawiamy dowód twierdzenia analogicznego do Twierdzenia 13.8, a wiążącego tym razem zbiory rozdzielające z drogami rozłącznymi wierzchołkowo.

Twierdzenie 13.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 13.9, można w łatwy sposób wywnioskować Twierdzenia 13.7, o skojarzeniach w grafach dwudzielnych. Wyprowadzenie to pozostawiamy jako ćwiczenie 10.

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 13.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 13.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.



Przykładowa sieć



Przepływ w sieci z rysunku Przykładowa sieć

Sieć to trójka \mathbf{N}=\left( V, A, {\sf c} \right), w której:

  • \left( V,A \right) jest pełnym digrafem (czyli A=V\times V),
  • funkcja {\sf c}:E \longrightarrow [0,+\infty), zwana przepustowością sieci, każdej krawędzi vw przypisuje nieujemną liczbę rzeczywistą {\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ść {\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.

Przepływ w sieci \mathbf{N}=\left( V, A, {\sf c} \right) to funkcja {\sf f}:E \longrightarrow [0,+\infty) spełniająca warunki:

  • 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.
  • \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.
  • \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 {\sf f}.

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 \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 \left( V,A \right). 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 \left( S,T \right) 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 \left( S,T \right) to suma


\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 13.12 [Ford i Fulkerson 1956]

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

Dowód

Niech \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 {\sf f} w sieci \mathbf{N}.

Niech S\subseteq V będzie zbiorem zawierającym źródło s oraz te wierzchołki w, które w grafie szkieletowym digrafu \left( V,A \right) połączone są ze źródłem pewną ścieżką s=v_1\to\ldots\to v_k=w, w której łuk v_i v_{i+1} ma niepełny przepływ (tzn. {\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 {\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\ldots\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 \varepsilon>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 {\sf f}+\epsilon, co przeczy maksymalności przepływu {\sf f}.

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


\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).\qquad (1)


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


\sum_{x\in V}\left( {\sf f}\!\left(ux\right)-{\sf f}\!\left(xu\right) \right)=0,


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


\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 (1) można więc przekształcić w następujący sposób:


\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


\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 (1) oznacza, że wartość przepływu z wierzchołka s do wierzchołka t jest równa przepustowości przekroju wyznaczonego przez zbiory S,T.

image:End_of_proof.gif