Matematyka dyskretna 1/Wykład 13: Grafy II

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 , zaś graf w części b. nie jest eulerowski, bo jeżeli wejdzie się do wierzchołka , to już nie będzie można z niego wyjść; jeśli zaś rozpoczęlibyśmy naszą marszrutę z wierzchołka 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 jest eulerowski wtedy i tylko wtedy, gdy jest spójny i stopień każdego wierzchołka jest parzysty.

Dowód

Załóżmy najpierw, że jest eulerowski i niech jakimś jego cyklem Eulera. Poruszając się po wzdłuż cyklu zliczajmy stopniowo używane krawędzie incydentne do poszczególnych wierzchołków. Zawsze po wejściu i wyjściu z danego wierzchołka liczba policzonych krawędzi incydentnych z zwiększy się o . Tak więc, jeśli 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 lub spójności grafu .

Dla dowodu implikacji odwrotnej, pokażmy najpierw, że jeżeli w skończonym grafie dowolny wierzchołek ma parzysty stopień, to posiada cykl. Istnienie takiego cyklu pokażemy wskazując jego kolejne krawędzie. Zaczynamy od dowolnie wybranej krawędzi . Następnie przechodzimy do jakiejkolwiek innej krawędzi wychodzącej z wierzchołka . Załóżmy, że była to krawędź . Wybieramy następnie dowolną różną od krawędź wychodzącą z . Czynność tę powtarzamy tak długo, aż dojdziemy do jakiegoś wierzchołka , który został już wcześniej odwiedzony. W ten sposób otrzymamy cykl . Jedynym problemem mógłby, w jakimś momencie, być brak możliwości kontynuowania marszu zanim dojdziemy do odwiedzonego wcześniej punktu . 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 . Jak już zauważyliśmy powyżej, graf posiada jakiś cykl . Usuńmy z grafu krawędzie i wierzchołki cyklu otrzymując w ten sposób mniejszy graf . Graf może już nie być spójny, ale nadal będzie posiadał jedynie wierzchołki parzystego stopnia. Jeżeli jest pusty, to cykl jest cyklem Eulera, co kończyłoby dowód. W przeciwnym razie, w każdej spójnej składowej grafu nie będącej punktem izolowanym, korzystając z założenia indukcyjnego, znajdujemy cykle Eulera . Ponieważ graf był spójny, to cykl musi przechodzić przez jakiś wierzchołek każdego cyklu . Tak więc cykl Eulera dla grafu możemy wyznaczyć w ten sposób, że przechodząc przez cykl , za każdym razem gdy napotkamy nieodwiedzony jeszcze cykl , zbaczamy z cyklu i przechodzimy w całości , a później kontynuujemy wędrówkę po cyklu . W konsekwencji przejdziemy po wszystkich krawędziach, każdą odwiedzając jedynie raz.

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 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 jest jednokreślny, i marszruta przechodząca przez każda krawędź jest cyklem, to 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 wszystkie wierzchołki mają parzysty stopień, to jest eulerowski, a zatem jednokreślny. Jeśli zaś 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 , w którym już wszystkie wierzchołki mają parzysty stopień. A zatem posiada cykl Eulera . Cykl ten przechodzi oczywiście przez nowo dodana krawędź. Usuwając ją z cyklu dostajemy marszrutę w grafie , świadcząca o jego jednokreślności.

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 o co najmniej wierzchołkach dowolne dwa niesąsiednie wierzchołki i spełniają , to graf jest hamiltonowski.

Cykl Hamiltona w grafie

Dowód

Dla dowodu niewprost załóżmy, że pewien niehamiltonowski graf o wierzchołkach spełnia

(*) , dla niesąsiednich wierzchołków .

Dodawanie krawędzi do nie psuje warunku (*), więc do grafu można dokładać krawędzie tak długo, jak długo jest on niehamiltonowski. Możemy więc dodatkowo założyć, że ma tę własność, że po dodaniu jakiejkolwiek krawędzi otrzymamy już cykl Hamiltona. Tak więc w musi istnieć ścieżka Hamiltona .

Wierzchołek ma, poza wierzchołkiem , dodatkowo sąsiadów. Oznaczmy ich przez . Z kolei, na mocy (*), wierzchołek w zbiorze ma sąsiadów. To gwarantuje, że jest sąsiadem któregoś z wierzchołków . Istnieje więc takie miejsce w ścieżce , że jest incydentny z , zaś z .

Tak więc cykl jest cyklem Hamiltona w grafie , co w konsekwencji daje sprzeczność z faktem, że miał nie być hamiltonowski.

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 , w którym każdy wierzchołek ma stopień co najmniej 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 , w którym zbiór wierzchołków da się podzielić na dwa rozłączne podzbiory oraz tak, by żadne dwa wierzchołki w obrębie tego samego podzbioru nie były sąsiadami. Czasem, dla podkreślenia takiego podziału, graf dwudzielny będziemy oznaczać przez . Zauważmy jednak, że podział taki nie jest jednoznaczny - np. w antyklice 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 jest dwudzielny czyli, że można podzielić na dwa rozłączne zbiory wierzchołków oraz , w ten sposób, że podgrafy indukowane są antyklikami. Rozważmy cykl o elementach. Bez straty ogólności możemy załóżyć, że . Ponieważ pomiędzy wierzchołkami z nie ma krawędzi, to . Z kolei , a i tak dalej. Tak więc każdy o nieparzystym indeksie należy do . W konsekwencji musi mieć parzysty indeks , aby mógł być połączony z . W rezultacie otrzymujemy, że cykle muszą być parzystej długości.

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

Niech teraz graf ma spójnych składowych . Wtedy każdą spójną składową możemy podzielić na zbiory świadczące o dwudzielności grafu indukowanego . W konsekwencji daje to podział na oraz świadczący o dwudzielności całego grafu .

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 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 to podzbiór krawędzi , w którym żadne dwie nie wychodzą z tego samego wierzchołka.
Powiemy ponadto, że jest skojarzony, jeśli istnieje taki, że krawędź należy do skojarzenia.

Pełne skojarzenie z w grafie dwudzielnym to skojarzenie, w którym każdy wierzchołek z jest skojarzony.

Naturalnym jest pytanie, kiedy istnieje pełne skojarzenie z w grafie dwudzielnym . Odpowiedział na nie P. Hall. Użył do tego funkcji zwracającej dla zbiór tych wierzchołków , które są sąsiednie z przynajmniej jednym wierzchołkiem w .

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

Niech będzie grafem dwudzielnym. Wówczas pełne skojarzenie z istnieje wtedy i tylko wtedy, gdy dla każdego podzbioru zbioru .

Dowód

Dla dowodu nierówności załóżmy, że jest pełnym skojarzeniem. Elementy skojarzone z elementami zbioru muszą być oczywiście w . Z drugiej strony skojarzenie determinuje injekcję , skąd natychmiast .

Dowód implikacji odwrotnej jest nieco trudniejszy. Przeprowadzimy go indukcyjnie ze względu na liczbę wierzchołków . Dla nierówność gwarantuje, że jest co kojarzyć z jedynym wierzchołkiem w . Załóżmy więc, że i rozważmy dwa przypadki:

1. Dowolny właściwy podzbiór zbioru wierzchołków posiada więcej sąsiadów niż jego moc, tzn. . Wtedy wybieramy dowolne wierzchołki oraz i je kojarzymy. Dla zbiór sąsiadów w zbiorze pomniejszonym o wybrany już jest nadal nie liczniejszy niż liczność . Założenie indukcyjne gwarantuje nam więc jakieś skojarzenie pełne zbioru z w grafie pozostałych wierzchołków . Oczywiście jest poszukiwanym skojarzeniem pełnym w .
2. Istnieje właściwy podzbiór zbioru , taki że .

Ponieważ dla mamy , to



Ta nierówność pozwala użyć założenia indukcyjnego do skojarzenia wszystkich elementów ze zbioru z elementami należącymi do .

Wystarczy więc znaleźć skojarzenie pozostałych elementów, czyli skojarzenie zbioru ze zbiorem . Skojarzenie takie dostaniemy również indukcyjnie, o ile pokażemy, że dla dowolnego , zbiór jego sąsiadów w jest liczniejszy od , tzn.



Załóżmy, że jakiś zbiór nie spełnia powyższej nierówności. Wtedy



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

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 -spójny to graf, który po usunięciu dowolnie wybranych wierzchołków (i incydentnych z nimi krawędzi) pozostaje spójny.

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

Przykład

  • Grafy -spójne lub -spójne krawędziowo to po prostu grafy spójne.
  • Drzewa są spójne, ale nie -spójne i nie -spójne krawędziowo.
  • Klika jest -spójna i -spójna krawędziowo.

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

Zbiór rozdzielający wierzchołki to zbiór wierzchołków taki, że każda droga z do przechodzi przez któryś element ze zbioru .

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

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

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

Most to taka krawędź , że zbiór tworzy rozcięcie.

Uwaga

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

Grafy menger

W grafie z rysunku Grafy menger odpowiednim rozspajającym zbiorem z przypadku 1, może być zbiór zaznaczonych liniami przerywanymi


Kontynuacja przykładu z rysunku Grafy menger i rysunku z liniami przerywanymi. Pokazane są grafy (a) oraz (b)

Przykład

Przykładowymi zbiorami rozdzielającymi wierzchołki w grafie z rysunku Grafy menger są zbiory i . Zbiory jest rozspajający, a zbiór jest rozcięciem. Graf ten jest -spójny oraz -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 będą dwoma różnymi i niesąsiednimi wierzchołkami grafu spójnego . Przez oznaczmy najmniejszą możliwą liczność zbioru krawędzi rozspajającego . Oczywiście każda droga łącząca z musi przejść przez każdy zbiór rozspajający. A zatem dróg krawędziowo rozłącznych łączących z nie może być więcej niż . Tak więc wystarczy pokazać, że istnieje rozłącznych krawędziowo dróg z do .

Dowód przeprowadzimy indukcyjnie ze względu na liczbę krawędzi w grafie rozważając dwa przypadki.

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

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

Przez oznaczmy graf powstały z grafu poprzez ściągnięcie w jeden wierzchołek . Wtedy jest połączony z tymi wierzchołkami , z którymi połączony był jakiś wierzchołek . Warto zauważyć, że wtedy musiało być . Krawędzie łączące wierzchołki wewnątrz pozostały niezmienione. Graf definiujemy analogicznie, poprzez ściągnięcie zbioru do wierzchołka .

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

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

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

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

Wniosek 13.10

Graf z co najmniej wierzchołkami jest -spójny wtedy i tylko wtedy, gdy dowolne dwa wierzchołki są połączone przynajmniej 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 krawędziami jest -spójny krawędziowo wtedy i tylko wtedy, gdy dowolne dwa wierzchołki są połączone przynajmniej 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 , w której:

  • jest pełnym digrafem (czyli ),
  • funkcja , zwana przepustowością sieci, każdej krawędzi przypisuje nieujemną liczbę rzeczywistą .
  • Ponadto wyróżnia się dwa wierzchołki , które są odpowiednio źródłem oraz ujściem sieci.

Przepustowość krawędzi może być interpretowana jako wartość potencjalnie maksymalnego przepływu z wierzchołka do . Jeśli przepustowość jakiejś krawędzi wynosi , to krawędź jest pomijana w graficznym przedstawieniu sieci.

Przepływ w sieci to funkcja spełniająca warunki:

  • dla każdej krawędzi . Wartość przepływu daną krawędzią nie może przekroczyć przepustowości tej krawędzi.
  • dla każdego wierzchołka poza źródłem i ujściem . 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.
  • , 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 .

Do analizy przepływów przydatne okazuje się pojęcie przekroju sieci. Można go sobie wyobrażać jako zbiór krawędzi , usunięcie których z sieci rozspaja sieć na dwie części oraz , przy czym zawiera źródło, a ujście. Warto zauważyć, że tworzy zbiór rozspajający w grafie szkieletowym digrafu . 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 zbioru wierzchołków , taka że:

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

Przepustowość przekroju to suma



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 będzie siecią o źródle i ujściu . 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 w sieci .

Niech będzie zbiorem zawierającym źródło oraz te wierzchołki , które w grafie szkieletowym digrafu połączone są ze źródłem pewną ścieżką , w której łuk ma niepełny przepływ (tzn. ) lub też łuk ma niezerowy przepływ . W języku firmy wodociągowej jest zbiorem wierzchołków, do których można jeszcze przepchnąć choć trochę wody.

Załóżmy przez chwilę, że . Istnieje wtedy ścieżka , w której dla każdej pary kolejnych wierzchołków można byłoby zwiększyć przepływ na łuku lub zmniejszyć na łuku . Niech będzie jakąś wartością zmian przepływu możliwych do wykonania na każdej parze kolejnych wierzchołków ścieżki. Wtedy, modyfikując odpowiednio łuki pomiędzy wierzchołkami uzyskalibyśmy przepływ o wartości , co przeczy maksymalności przepływu .

Udowodniliśmy właśnie, że tworzy przekrój sieci , gdzie . Pokażmy, że przepustowość tego przekroju równa się wartości przepływu . Z definicji wynika, że jeżeli rozważymy dwa elementy oraz , to przepływ oraz .Tak więc przepustowość przekroju równa jest



Z faktu, że dla wartość tego co wpływa jest równa temu co wypływa, czyli innymi słowy



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



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



Powtarzając wielokrotnie przekładanie kolejnych punktów z do otrzymamy w konsekwencji



co na mocy (1) oznacza, że wartość przepływu z wierzchołka do wierzchołka jest równa przepustowości przekroju wyznaczonego przez zbiory .

End of proof.gif