Problem maksymalnego przepływu - Maximum flow problem

Sieć przepływów dla problemu: Każdy człowiek (ri) jest skłonny adoptować kota (wi1) i/lub psa (wi2).  Jednak każde zwierzę (pi) preferuje tylko podzbiór ludzi.  Znajdź dowolne dopasowanie zwierząt domowych do ludzi, tak aby maksymalna liczba zwierząt została zaadoptowana przez jednego z preferowanych ludzi.
Sieć przepływów dla problemu: Każdy człowiek (r i ) jest skłonny adoptować kota (w i 1) i/lub psa (w i 2). Jednak każdy pet (p ja ) ma preferencje tylko podzbioru ludzi. Znajdź dowolne dopasowanie zwierząt domowych do ludzi, tak aby maksymalna liczba zwierząt została zaadoptowana przez jednego z preferowanych ludzi.

W teorii optymalizacji , maksymalne problemy przepływowe obejmują znalezienie wykonalnego przepływ poprzez sieć przepływu , która uzyskuje maksymalną możliwą szybkość przepływu.

Problem maksymalnego przepływu może być postrzegany jako szczególny przypadek bardziej złożonych problemów z przepływem w sieci, takich jak problem z cyrkulacją . Maksymalna wartość przepływu st (tj. przepływu od źródła s do ujścia t) jest równa minimalnej przepustowości odcięcia st (tj. odcięcia s od t) w sieci, jak podano w max-flow min- twierdzenie o cięciu .

Historia

Problem maksymalnego przepływu został po raz pierwszy sformułowany w 1954 r. przez TE Harrisa i FS Rossa jako uproszczony model przepływu ruchu kolejowego w Związku Radzieckim.

W 1955 roku Lester R. Ford, Jr. i Delbert R. Fulkerson stworzyli pierwszy znany algorytm, algorytm Forda-Fulkersona . W swoim artykule z 1955 roku Ford i Fulkerson napisali, że problem Harrisa i Rossa sformułowano w następujący sposób (patrz s. 5):

Rozważmy sieć kolejową łączącą dwa miasta za pomocą liczby miast pośrednich, gdzie każde łącze sieci ma przypisany numer reprezentujący jego przepustowość. Zakładając stan ustalony, znajdź maksymalny przepływ z jednego miasta do drugiego.

W swojej książce Flows in Network w 1962 roku Ford i Fulkerson napisali:

Postawił go autorom wiosną 1955 r. TE Harris, który wspólnie z generałem FS Rossem (w stanie spoczynku) sformułował uproszczony model przepływu ruchu kolejowego i wskazał ten konkretny problem jako główny, sugerowany przez wzór [11].

gdzie [11] odnosi się do tajnego raportu z 1955 r. Fundamentals of a Method for Evaluating Rail net Capacities autorstwa Harrisa i Rossa (patrz s. 5).

Z biegiem lat odkryto różne ulepszone rozwiązania problemu maksymalnego przepływu, w szczególności najkrótszy algorytm ścieżki rozszerzającej Edmondsa i Karpa oraz niezależnie Dinitza; algorytm blokowania przepływu Dinitza; algorytm push-Znakowanie od Goldberg i Tarjan ; oraz binarny algorytm blokowania przepływu Goldberga i Rao. Algorytmy odpowiednio Shermana i Kelnera, Lee, Orecchii i Sidforda znajdują w przybliżeniu optymalny maksymalny przepływ, ale działają tylko w grafach nieskierowanych.

W 2013 roku James B. Orlin opublikował artykuł opisujący algorytm.

Definicja

Sieć przepływu ze źródłem s i Umywalka t . Liczby obok krawędzi to pojemności.

Najpierw ustalamy pewną notację:

  • Niech będzie siecią będącą odpowiednio źródłem i ujściem .
  • Jeżeli jest funkcją na krawędziach to jego wartość on jest oznaczana przez lub

Definicja. Pojemność od krawędzi jest maksymalną ilość gazu, którą może przechodzić przez krawędź. Formalnie jest to mapa

Definicja. Przepływu znajduje się mapa , która spełnia następujące:

  • Ograniczenie pojemności . Przepływ krawędzi nie może przekroczyć jej możliwości, innymi słowy: dla wszystkich
  • Ochrona przepływów. Suma przepływów wchodzących do węzła musi być równa sumie przepływów wychodzących z tego węzła, z wyjątkiem źródła i ujścia. Lub:

Uwaga . Przepływy są skośnie symetryczne: dla wszystkich

Definicja. Wartość przepływu jest ilość przepływającego od źródła do zlewu przepływu. Formalnie dla przepływu wyraża się wzorem:

Definicja. Problem maksymalnego przepływu polega na skierowaniu jak największego przepływu od źródła do ujścia, innymi słowy znalezienie przepływu o maksymalnej wartości.

Zauważ, że może istnieć kilka przepływów maksymalnych, a jeśli dozwolone są dowolne rzeczywiste (lub nawet racjonalne) wartości przepływu (zamiast tylko liczb całkowitych), to istnieje albo dokładnie jeden przepływ maksymalny, albo nieskończenie wiele, ponieważ istnieje nieskończenie wiele kombinacji liniowych bazowe maksymalne przepływy. Innymi słowy, jeśli wyślemy jednostki przepływu na krawędzi w jednym maksymalnym przepływie, a jednostki przepływu w innym maksymalnym przepływie, to dla każdego możemy wysłać jednostki i odpowiednio skierować przepływ na pozostałe krawędzie, aby uzyskać inny maksymalny przepływ. Jeśli wartości przepływu mogą być dowolnymi liczbami rzeczywistymi lub wymiernymi, to dla każdej pary takich wartości jest nieskończenie wiele .

Algorytmy

W poniższej tabeli wymieniono algorytmy rozwiązywania problemu maksymalnego przepływu.

metoda Złożoność Opis
Programowanie liniowe Ograniczenia wynikające z definicji przepływu prawnego . Zobacz program liniowy tutaj.
Algorytm Forda-Fulkersona Dopóki na wykresie resztkowym istnieje otwarta ścieżka, wyślij minimalną pojemność resztkową na ścieżce.

Algorytm gwarantuje zakończenie działania tylko wtedy, gdy wszystkie wagi są racjonalne , w takim przypadku kwota dodana do przepływu w każdym kroku jest co najmniej największym wspólnym dzielnikiem wag. W przeciwnym razie możliwe jest, że algorytm nie osiągnie maksymalnej wartości. Jeśli jednak algorytm się zakończy, gwarantowane jest znalezienie wartości maksymalnej.

Algorytm Edmondsa-Karpa Specjalizacja Forda-Fulkersona, znajdowanie ścieżek rozszerzających za pomocą przeszukiwania wszerz .
Algorytm Dinica W każdej fazie algorytmy budują graf warstwowy z przeszukiwaniem wszerz na grafie rezydualnym . Maksymalny przepływ na wykresie warstwowym można obliczyć w czasie, a maksymalna liczba faz wynosi . W sieciach o pojemnościach jednostkowych algorytm Dinica kończy się w czasie.
Algorytm MKM (Malhotra, Kumar, Maheshwari) Modyfikacja algorytmu Dinica z innym podejściem do konstruowania przepływów blokujących. Zapoznaj się z oryginalnym papierem .
Algorytm Dinica z dynamicznymi drzewami Struktura danych dynamicznych drzew przyspiesza obliczanie maksymalnego przepływu na wykresie warstwowym do .
Ogólny algorytm push-relabel Algorytm push relabel utrzymuje preflow, czyli funkcję przepływu z możliwością przekroczenia wierzchołków. Algorytm działa, gdy w grafie znajduje się wierzchołek z dodatnim nadmiarem, czyli aktywny wierzchołek. Operacja przepchnięcia zwiększa przepływ na krawędzi szczątkowej, a funkcja wysokości wierzchołków kontroluje, przez które krawędzie szczątkowe mogą być przepchnięte. Funkcja wysokości jest zmieniana przez operację zmiany etykiety. Właściwe definicje tych operacji gwarantują, że wynikowa funkcja przepływu jest przepływem maksymalnym.
Algorytm push-relabel z regułą wyboru wierzchołków FIFO Wariant algorytmu push-relabel, który zawsze wybiera ostatni aktywny wierzchołek i wykonuje operacje push, gdy nadmiar jest dodatni i istnieją dopuszczalne krawędzie resztkowe z tego wierzchołka.
Algorytm push-relabel z regułą wyboru wierzchołków maksymalnej odległości Wariant algorytmu push-relabel, który zawsze wybiera najdalszy wierzchołek z lub (tj. wierzchołek o najwyższej etykietce), ale poza tym działa jak algorytm FIFO.
Algorytm push-relabel z dynamicznymi drzewami Algorytm buduje drzewa o ograniczonej wielkości na wykresie resztowym w odniesieniu do funkcji wysokości. Te drzewa zapewniają wielopoziomowe operacje wypychania, tj. wypychanie wzdłuż całej ścieżki nasycenia zamiast pojedynczej krawędzi.
Algorytm KRT (King, Rao, Tarjan)
Binarny algorytm blokowania przepływu Wartość U odpowiada maksymalnej przepustowości sieci.
Algorytm Jamesa B Orlina + KRT (King, Rao, Tarjan) Algorytm Orlina rozwiązuje max-flow w czasie for, podczas gdy KRT rozwiązuje go w for .
Algorytm Kathurii-Liu-Sidforda Metody punktów wewnętrznych i wzmacnianie krawędzi za pomocą przepływów -norm. Opiera się na wcześniejszym algorytmie Madry, który osiągnął runtime .
Algorytm BLNPSSSW / BLLSSSW

Metody punktów wewnętrznych i dynamiczne utrzymywanie przepływów elektrycznych z rozkładami ekspanderów.
Algorytm Gao-Liu-Peng Algorytm Gao, Liu i Penga opiera się na dynamicznym utrzymywaniu zwiększających się przepływów elektrycznych w rdzeniu algorytmu opartego na metodzie punktów wewnętrznych z [Mądry JACM '16]. Wiąże się to z projektowaniem struktur danych, które przy ograniczonych ustawieniach zwracają krawędzie z dużą energią elektryczną na wykresie podlegającym aktualizacji rezystancji.

Dodatkowe algorytmy, patrz Goldberg i Tarjan (1988) .

Twierdzenie o przepływie całkowym

Twierdzenie o przepływie całkowym mówi, że

Jeżeli każda krawędź w sieci przepływowej ma integralną przepustowość, wówczas istnieje całkowity przepływ maksymalny.

Twierdzi się nie tylko, że wartość przepływu jest liczbą całkowitą, która wynika bezpośrednio z twierdzenia max-flow min-cut , ale że przepływ na każdej krawędzi jest całkowy. Ma to kluczowe znaczenie dla wielu zastosowań kombinatorycznych (patrz poniżej), gdzie przepływ przez krawędź może kodować, czy element odpowiadający tej krawędzi ma być zawarty w poszukiwanym zestawie, czy nie.

Podanie

Problem z maksymalnym przepływem wielu źródeł z wieloma zlewami

Rys. 4.1.1. Przekształcenie problemu maksymalnego przepływu z wielu źródeł z wieloma zlewami w problem z maksymalnym przepływem z jednego źródła z jednym zlewem

Mając sieć ze zbiorem źródeł i zbiorem ujścia zamiast tylko jednego źródła i jednego ujścia, musimy znaleźć maksymalny przepływ w poprzek . Możemy przekształcić wieloźródłowy problem z wieloma ujściami w problem maksymalnego przepływu, dodając skonsolidowane źródło łączące się z każdym wierzchołkiem w i skonsolidowane ujście połączone przez każdy wierzchołek w (znane również jako superźródło i superzlew ) o nieskończonej pojemności na każdej krawędzi ( Patrz rys. 4.1.1.).

Dwustronne dopasowanie maksymalnej kardynalności

Rys. 4.3.1. Przekształcenie problemu maksymalnego dwuczęściowego dopasowania w problem maksymalnego przepływu

Mając graf dwudzielny , musimy znaleźć dopasowanie maksymalnej kardynalności w , czyli dopasowanie, które zawiera największą możliwą liczbę krawędzi. Problem ten można przekształcić w problem maksymalnego przepływu, budując sieć , w której

  1. zawiera krawędzie w skierowanych od do .
  2. dla każdego i dla każdego .
  3. dla każdego (patrz rys. 4.3.1).

Następnie wartość maksymalnego przepływu w jest równa rozmiarowi maksymalnego dopasowania w , a dopasowanie maksymalnej kardynalności można znaleźć, biorąc te krawędzie, które mają przepływ w całkowitym maksymalnym przepływie.

Minimalne pokrycie ścieżki w skierowanym grafie acyklicznym

Mając skierowany graf acykliczny , musimy znaleźć minimalną liczbę ścieżek rozłącznych wierzchołków, aby pokryć każdy wierzchołek w . Możemy skonstruować graf dwudzielny z , gdzie

  1. .

Następnie można wykazać, że ma dopasowanie rozmiaru wtedy i tylko wtedy, gdy pokrywa ścieżki rozłącznych wierzchołków zawiera krawędzie i ścieżki, gdzie jest liczbą wierzchołków w . Dlatego problem można rozwiązać, znajdując zamiast tego maksymalne dopasowanie kardynalności .

Intuicyjnie, jeśli dwa wierzchołki są dopasowane w , to krawędź jest zawarta w . Oczywiście liczba krawędzi w jest . Aby zobaczyć, że jest to wierzchołek rozłączny, rozważ następujące kwestie:

  1. Każdy wierzchołek in może być niedopasowany w , w którym to przypadku nie ma żadnych krawędzi w ; lub może być dopasowane , w takim przypadku istnieje dokładnie jedna krawędź pozostawiając w . W obu przypadkach nie więcej niż jedna krawędź pozostawia wierzchołek w .
  2. Podobnie dla każdego wierzchołka in – jeśli jest dopasowany, do in ; w przeciwnym razie nie ma przychodzących krawędzi w .

Zatem żaden wierzchołek nie ma dwóch krawędzi przychodzących lub dwóch wychodzących w , co oznacza, że ​​wszystkie ścieżki w są wierzchołkami rozłącznymi.

Aby pokazać, że okładka ma rozmiar , zaczynamy od pustej okładki i budujemy ją stopniowo. Aby dodać wierzchołek do okładki, możemy dodać go do istniejącej ścieżki lub utworzyć nową ścieżkę o długości zerowej, zaczynając od tego wierzchołka. Pierwszy przypadek ma zastosowanie, gdy jedna i jakaś ścieżka w okładce zaczyna się o , albo jakaś ścieżka kończy się o . Ten ostatni przypadek ma zawsze zastosowanie. W pierwszym przypadku całkowita liczba krawędzi w okładce zwiększa się o 1, a liczba ścieżek pozostaje taka sama; w tym drugim przypadku zwiększa się liczba ścieżek, a liczba krawędzi pozostaje taka sama. Teraz jest jasne, że po pokryciu wszystkich wierzchołków suma liczby ścieżek i krawędzi w otulinie wynosi . Dlatego jeśli liczba krawędzi w okładce wynosi , liczba ścieżek wynosi .

Maksymalny przepływ przy pojemnościach wierzchołków

Rys. 4.4.1. Przekształcenie problemu maksymalnego przepływu z ograniczeniem pojemności wierzchołków w pierwotny problem maksymalnego przepływu przez podział węzłów

Niech będzie siecią. Załóżmy, że w każdym węźle istnieje przepustowość oprócz przepustowości krawędzi, to znaczy odwzorowanie takie, że przepływ musi spełniać nie tylko ograniczenie przepustowości i zachowanie przepływów, ale także ograniczenie przepustowości wierzchołków

Innymi słowy, wielkość przepływu przechodzącego przez wierzchołek nie może przekroczyć jego przepustowości. Aby znaleźć maksymalny przepływ w poprzek , możemy przekształcić problem w problem maksymalnego przepływu w pierwotnym znaczeniu poprzez rozszerzenie . Najpierw każdy jest zastąpiony przez i , gdzie jest połączony krawędziami wchodzącymi i połączonymi z krawędziami wychodzącymi z , a następnie przypisz pojemność krawędzi łączącej i (patrz rys. 4.4.1). W tej rozszerzonej sieci ograniczenie przepustowości wierzchołków jest usuwane, a zatem problem można traktować jako pierwotny problem maksymalnego przepływu.

Maksymalna liczba ścieżek od s do t

Mając graf skierowany i dwa wierzchołki i , mamy znaleźć maksymalną liczbę ścieżek od do . Ten problem ma kilka wariantów:

1. Ścieżki muszą być rozłączne krawędziowo. Problem ten można przekształcić w problem maksymalnego przepływu, konstruując sieć z , z i będącą odpowiednio źródłem i ujściem , oraz przypisując każdej krawędzi pojemność . W tej sieci maksymalny przepływ jest wtedy, gdy istnieją ścieżki rozłączne na krawędziach.

2. Ścieżki muszą być niezależne, tj. wierzchołki rozłączne (z wyjątkiem i ). Możemy skonstruować sieć z o pojemności wierzchołków, gdzie moce wszystkich wierzchołków i wszystkie krawędzie . Wtedy wartość maksymalnego przepływu jest równa maksymalnej liczbie niezależnych ścieżek od do .

3. Oprócz tego, że ścieżki są rozłączne krawędziami i/lub wierzchołkami, ścieżki mają również ograniczenie długości: liczymy tylko ścieżki, których długość wynosi dokładnie , lub co najwyżej . Większość wariantów tego problemu jest NP-zupełna, z wyjątkiem małych wartości .

Problem z zamknięciem

Zamknięcie ukierunkowanej wykresie to zbiór wierzchołków C tak, że krawędzie nie pozostawiać C . Problemem zamknięcie jest zadanie znalezienia maksymalnym masy lub zamknięcie minimalnego ciężaru na wierzchołku skierowanym ważone wykresie. Można go rozwiązać w czasie wielomianowym, stosując redukcję do problemu maksymalnego przepływu.

Aplikacje w świecie rzeczywistym

Eliminacja baseballu

Budowa przepływu sieciowego dla problemu eliminacji baseballu

W eliminacyjnym problemie baseballowym w lidze rywalizuje n drużyn. Na określonym etapie sezonu ligowego w i to liczba wygranych, a r i to liczba meczów pozostałych do rozegrania dla drużyny i, a r ij to liczba meczów pozostałych do rozegrania przeciwko drużynie j . Drużyna zostaje wyeliminowana, jeśli nie ma szans na ukończenie sezonu na pierwszym miejscu. Zadaniem problemu eliminacji baseballa jest ustalenie, które drużyny są eliminowane w każdym punkcie sezonu. Schwartz zaproponował metodę, która sprowadza ten problem do maksymalnego przepływu w sieci. W tej metodzie tworzona jest sieć w celu ustalenia, czy zespół k jest eliminowany.

Niech G = ( V , E ) będzie siecią, w której s , tV będzie odpowiednio źródłem i ujściem. Jeden dodaje węzeł gry ij – który reprezentuje liczbę rozgrywek między tymi dwoma zespołami. Dodajemy również węzeł drużyny dla każdej drużyny i łączymy każdy węzeł gry { i , j } z i < j do V , a każdy z nich łączymy od s krawędzią o pojemności r ij – co reprezentuje liczbę zagrań między tymi dwoma zespoły. Dodajemy również węzeł zespołu dla każdej drużyny i łączymy każdy węzeł gry { i , j } z dwoma węzłami zespołu i oraz j, aby zapewnić, że jeden z nich wygra. Nie trzeba ograniczać wartości przepływu na tych krawędziach. Na koniec, krawędzie są tworzone od węzła zespołu i do węzła ujścia t, a pojemność w k + r kw i jest ustawiona tak, aby zespół i nie wygrał więcej niż w k + r k . Niech S będzie zbiorem wszystkich drużyn biorących udział w lidze i niech

.

W tej metodzie twierdzi się, że zespół k nie jest wyeliminowany wtedy i tylko wtedy, gdy w sieci G istnieje wartość przepływu o wielkości r ( S − { k } ) . We wspomnianym artykule udowodniono, że ta wartość przepływu jest maksymalną wartością przepływu od s do t .

Planowanie linii lotniczych

W branży lotniczej poważnym problemem jest planowanie załóg lotniczych. Problem planowania linii lotniczych można rozpatrywać jako zastosowanie rozszerzonego maksymalnego przepływu w sieci. Dane wejściowe do tego problemu to zbiór lotów F, który zawiera informacje o tym, gdzie i kiedy każdy lot odlatuje i przylatuje. W jednej z wersji planowania linii lotniczych celem jest stworzenie możliwego do zrealizowania harmonogramu z maksymalnie tysiącami załóg.

W celu rozwiązania tego problemu stosuje się odmianę problemu cyrkulacji zwaną cyrkulacją ograniczoną, która jest uogólnieniem problemów przepływu sieciowego , z dodatkowym ograniczeniem dolnego ograniczenia przepływów brzegowych.

Niech G = ( V , E ) będzie siecią z s , tV jako węzłami źródłowymi i ujściami. Dla źródła i przeznaczenia każdego lotu í , jeden dodaje dwa węzły do V , węzeł y : i jako źródło i węzła d I jako węzła docelowego lotu í . Dodaje się również następujące krawędzie do E :

  1. Krawędź o pojemności [0, 1] pomiędzy s a każdym s i .
  2. Krawędź o pojemności [0, 1] pomiędzy każdym d i oraz t .
  3. Krawędź o nośności [1, 1] pomiędzy każdą parą s i oraz d i .
  4. Krawędź o pojemności [0, 1], pomiędzy każdym d i a s j , gdy source s j jest osiągalny z wystarczającą ilość czasu i kosztów, z miejsca przelotu ı .
  5. Krawędź o pojemności [0, ] pomiędzy s i t .

We wspomnianej metodzie stwierdzono i udowodniono, że znalezienie wartości przepływu k w G pomiędzy s i t jest równoznaczne ze znalezieniem wykonalnego harmonogramu dla zestawu lotów F z co najwyżej k załóg.

Inną wersją planowania linii lotniczych jest znalezienie minimalnej liczby załóg potrzebnych do wykonania wszystkich lotów. W celu znalezienia odpowiedzi na ten problem tworzony jest dwudzielny graf G' = ( AB , E ), w którym każdy lot ma kopię w zbiorze A i zbiorze B . Jeżeli ten sam samolot może wykonać lotu j po locie ja , iA jest podłączony do jB . Dopasowanie w G' indukuje harmonogram dla F i oczywiście maksymalne dopasowanie dwustronne na tym wykresie daje rozkład linii lotniczych z minimalną liczbą załóg. Jak wspomniano w części dotyczącej aplikacji tego artykułu, dwuczęściowe dopasowanie maksymalnej kardynalności jest zastosowaniem problemu maksymalnego przepływu.

Problem cyrkulacyjno-popytowy

Jest kilka fabryk produkujących towary i kilka wiosek, do których towary muszą zostać dostarczone. Są one połączone siecią dróg, przy czym każda droga ma przepustowość c dla maksymalnej ilości towarów, które mogą przez nią przepływać. Problem polega na tym, aby znaleźć nakład, który zaspokaja popyt. Ten problem można przekształcić w problem maksymalnego przepływu.

  1. Dodaj węzeł źródłowy s i dodać go do krawędzi z każdego węzła fabrycznej f I o pojemności p í gdzie p i jest tempo produkcji fabryki f I .
  2. Dodaj węzeł ujścia t i dodaj krawędzie ze wszystkich wsi v i do t o pojemności d i , gdzie d i jest stopą popytu wsi v i .

Niech G = ( V , E ) będzie tą nową siecią. Istnieje obieg, który zaspokaja zapotrzebowanie wtedy i tylko wtedy, gdy:

Maksymalna wartość przepływu ( G ) .

Jeśli istnieje cyrkulacja, spojrzenie na rozwiązanie z maksymalnym przepływem dałoby odpowiedź, ile towarów trzeba wysłać daną drogą, aby zaspokoić zapotrzebowanie.

Problem można rozszerzyć, dodając dolne ograniczenie przepływu na niektórych krawędziach.


Segmentacja obrazu

Obraz źródłowy o rozmiarze 8x8.
Sieć zbudowana z mapy bitowej. Źródło znajduje się po lewej stronie, zlew po prawej. Im ciemniejsza krawędź, tym większa jej pojemność. a i jest wysokie, gdy piksel jest zielony, b i, gdy piksel nie jest zielony. Wszystkie kary p ij są równe.

W swojej książce Kleinberg i Tardos przedstawiają algorytm segmentacji obrazu. Przedstawiają algorytm znajdowania tła i pierwszego planu na obrazie. Dokładniej, algorytm przyjmuje bitmapę jako dane wejściowe modelowane w następujący sposób: a i ≥ 0 to prawdopodobieństwo, że piksel i należy do pierwszego planu, b i ≥ 0 to prawdopodobieństwo, że piksel i należy do tła, a p ij to prawdopodobieństwo kara, jeśli dwa sąsiednie piksele i oraz j zostaną umieszczone jeden na pierwszym planie, a drugi w tle. Celem jest znalezienie podziału ( A , B ) zbioru pikseli, który maksymalizuje następującą ilość

,

Rzeczywiście, dla pikseli w A (uważanych za pierwszy plan) otrzymujemy a i ; dla wszystkich pikseli w B (traktowanych jako tło) otrzymujemy b i . Na granicy, pomiędzy dwoma sąsiednimi pikselami i oraz j , tracimy p ij . Jest to równoważne zminimalizowaniu ilości

ponieważ

Minimalne cięcie wyświetlane w sieci (trójkąty VS okręgi).

Teraz konstruujemy sieć, której węzły to piksel plus źródło i ujście, patrz rysunek po prawej. Łączymy źródło z pikselem i krawędzią wagi a i . Łączymy piksel i ze zlewem krawędzią wagi b i . Łączymy piksel i z pikselem j o wadze p ij . Teraz pozostaje obliczyć minimalne odcięcie w tej sieci (lub równoważnie maksymalny przepływ). Ostatni rysunek pokazuje minimalne cięcie.

Rozszerzenia

1. W zagadnieniu przepływu o minimalnych kosztach każda krawędź ( u ,v) oprócz swojej pojemności ma również współczynnik kosztowy a uv . Jeżeli strumień przez krawędź jest f UV , wówczas całkowity koszt UV F UV . Wymagane jest znalezienie przepływu o danej wielkości d , przy najmniejszym koszcie. W większości wariantów współczynniki kosztów mogą być dodatnie lub ujemne. Istnieją różne algorytmy wielomianowe dla tego problemu.

2. Problem maksymalnego przepływu może być rozszerzony przez ograniczenia dysjunktywne : ujemne ograniczenie dysjunktywne mówi, że pewna para krawędzi nie może jednocześnie mieć niezerowego przepływu; A pozytywne dysjunktywny ograniczenia mówi, że w pewnej pary krawędzi, co najmniej jeden musi mieć niezerowe płynąć. Przy ujemnych ograniczeniach problem staje się silnie NP-trudny nawet w przypadku prostych sieci. Przy dodatnich ograniczeniach problem jest wielomianowy, jeśli dozwolone są przepływy ułamkowe, ale może być silnie NP-trudny, gdy przepływy muszą być integralne.


Bibliografia

Dalsza lektura