Maximalt flödesproblem - Maximum flow problem

Flödesnätverk för problemet: Varje människa (r i ) är villig att adoptera en katt (w i 1) och/eller en hund (w i 2). Varje husdjur (p i ) har dock en preferens för endast en delmängd av människorna. Hitta någon matchning av husdjur till människor så att det maximala antalet husdjur antas av en av dess föredragna människor.

I optimeringslära , maximala problem flödes innebär att hitta en genomförbar flöde genom en flödesnätverk som erhåller maximalt möjliga flödet.

Det maximala flödesproblemet kan ses som ett specialfall av mer komplexa nätverksflödesproblem, till exempel cirkulationsproblemet . Det maximala värdet för ett st-flöde (dvs flöde från källor till sänkning t) är lika med minimikapaciteten för ett st-snitt (dvs avskärning s från t) i nätet, som anges i maxflödesmin- klippa sats .

Historia

Problemet med maximalt flöde formulerades först 1954 av TE Harris och FS Ross som en förenklad modell av sovjetiskt järnvägstrafikflöde.

År 1955 skapade Lester R. Ford, Jr. och Delbert R. Fulkerson den första kända algoritmen, Ford – Fulkerson -algoritmen . I sitt papper från 1955 skrev Ford och Fulkerson att problemet med Harris och Ross är formulerat enligt följande (se s. 5):

Tänk på ett järnvägsnät som förbinder två städer med ett antal mellanstäder, där varje länk i nätverket har ett nummer tilldelat det som representerar dess kapacitet. Antag ett steady state -tillstånd och hitta ett maximalt flöde från en stad till en annan.

I sin bok Flows in Network , 1962, skrev Ford och Fulkerson:

Den presenterades för författarna våren 1955 av TE Harris, som tillsammans med general FS Ross (Ret.) Hade formulerat en förenklad modell för järnvägstrafikflöde och identifierade detta problem som det centrala som föreslogs av modell [11].

där [11] hänvisar till 1955 års hemliga rapport Fundamentals of a Method for Evaluating Rail net Capacities av Harris och Ross (se s. 5).

Under årens lopp har olika förbättrade lösningar för det maximala flödesproblemet upptäckts, särskilt den kortaste algoritmen för förstoringsvägar för Edmonds och Karp och oberoende Dinitz; blockeringsflödesalgoritmen för Dinitz; den tryck märka om algoritmen av Goldberg och Tarjan ; och algoritmen för binärt blockerande flöde för Goldberg och Rao. Algoritmerna för Sherman och Kelner, Lee, Orecchia respektive Sidford hittar ett ungefär optimalt maximalt flöde men fungerar bara i oreglerade grafer.

År 2013 publicerade James B. Orlin ett papper som beskriver en algoritm. ${\ displaystyle O (| V || E |)}$

Definition

En flödesnätverk, med källa s och sjunker t . Siffrorna bredvid kanten är kapaciteterna.

Först upprättar vi en notation:

• Låt vara ett nätverk med att vara källan och sjunken av respektive.${\ displaystyle N = (V, E)}$${\ displaystyle s, t \ in V}$${\ displaystyle N}$
• Om är funktion på kanterna av då dess värde på betecknas med eller${\ displaystyle g}$${\ displaystyle N}$${\ displaystyle (u, v) \ i E}$${\ displaystyle g_ {uv}}$${\ displaystyle g (u, v).}$

Definition. Den kapacitet av en kant är den maximala mängden av flöde som kan passera genom en kant. Formellt är det en karta${\ displaystyle c: E \ to \ mathbb {R} ^{+}.}$

Definition. Ett flöde är en karta som uppfyller följande: ${\ displaystyle f: E \ to \ mathbb {R}}$

• Kapacitetsbegränsning . Flödet av en kant kan inte överstiga dess kapacitet, med andra ord: för alla${\ displaystyle f_ {uv} \ leq c_ {uv}}$${\ displaystyle (u, v) \ i E.}$
• Bevarande av flöden. Summan av flödena som kommer in i en nod måste vara lika med summan av flödena som lämnar den noden, förutom källan och sjunken. Eller:

${\ displaystyle \ forall v \ in V \ setminus \ {s, t \}: \ quad \ sum _ {u: (u, v) \ in E} f_ {uv} = \ sum _ {u: (v, u) \ i E} f_ {vu}.}$

Anmärkning . Flöden är skeva symmetriska: för alla${\ displaystyle f_ {uv} =-f_ {vu}}$${\ displaystyle (u, v) \ i E.}$

Definition. Det värde på flödet är mängden av flödet som passerar från källan till sink. Formellt för ett flöde ges det av: ${\ displaystyle f: E \ to \ mathbb {R} ^{+}}$

${\ displaystyle | f | = \ sum _ {v: (s, v) \ in E} f_ {sv}.}$

Definition. Det maximala flödesproblemet är att dirigera så mycket flöde som möjligt från källan till diskbänken, med andra ord hitta flödet med maximivärde. ${\ displaystyle f _ {\ textrm {max}}}$

Observera att flera maximala flöden kan existera, och om godtyckliga verkliga (eller till och med godtyckliga rationella) flödesvärden är tillåtna (istället för bara heltal) finns det antingen exakt ett maximalt flöde, eller oändligt många, eftersom det finns oändligt många linjära kombinationer av basens maximala flöden. Med andra ord, om vi skickar flödesenheter på kanten i ett maximalt flöde och flödesenheter på i ett annat maximalt flöde, så kan vi för varje sända enheter vidare och dirigera flödet på återstående kanter i enlighet därmed för att erhålla ytterligare ett maximalt flöde. Om flödesvärden kan vara några verkliga eller rationella tal finns det oändligt många sådana värden för varje par . ${\ displaystyle x}$${\ displaystyle u}$${\ displaystyle y> x}$${\ displaystyle u}$${\ displaystyle \ Delta \ i [0, yx]}$${\ displaystyle x+\ Delta}$${\ displaystyle u}$${\ displaystyle \ Delta}$${\ displaystyle x, y}$

Algoritmer

Följande tabell visar algoritmer för att lösa problemet med maximalt flöde.

Metod	Komplexitet	Beskrivning
Linjär programmering		Begränsningar som ges av definitionen av ett rättsligt flöde . Se det linjära programmet här.
Ford – Fulkerson algoritm	${\ displaystyle O (E \ vert f_ {max} \ vert)}$	Så länge det finns en öppen väg genom restdiagrammet, skicka minsta möjliga restkapacitet på banan. Algoritmen slutar bara garanteras om alla vikter är rationella , i vilket fall mängden som läggs till flödet i varje steg är åtminstone den största gemensamma delaren av vikterna. Annars är det möjligt att algoritmen inte kommer att konvergera till det maximala värdet. Men om algoritmen avslutas är det garanterat att hitta det maximala värdet.
Edmonds – Karp algoritm	${\ displaystyle O (VE^{2})}$	En specialisering av Ford – Fulkerson, att hitta förstoringsvägar med den första sökningen i bredd .
Dinics algoritm	${\ displaystyle O (V^{2} E)}$	I varje fas bygger algoritmerna upp ett lager med en bredd-första sökning på restgrafen . Det maximala flödet i ett skiktat diagram kan beräknas i tid, och det maximala antalet faser är . I nätverk med enhetskapacitet avslutas Dinics algoritm i tid. ${\ displaystyle O (VE)}$${\ displaystyle V-1}$${\ displaystyle O (\ min \ {V^{2/3}, E^{1/2} \} E)}$
MKM (Malhotra, Kumar, Maheshwari) algoritm	${\ displaystyle O (V^{3})}$	En modifiering av Dinics algoritm med ett annat tillvägagångssätt för att konstruera blockeringsflöden. Se originalpapperet .
Dinics algoritm med dynamiska träd	${\ displaystyle O (VE \ log V)}$	Den dynamiska trädens datastruktur påskyndar den maximala flödesberäkningen i det lagrade diagrammet till . ${\ displaystyle O (VE \ log V)}$
Allmän push -relabel -algoritm	${\ displaystyle O (V^{2} E)}$	Push -relabel -algoritmen upprätthåller ett förflöde, dvs en flödesfunktion med möjlighet till överskott i hörnen. Algoritmen körs medan det finns en toppunkt med positivt överskott, dvs en aktiv toppunkt i grafen. Pushoperationen ökar flödet på en kvarvarande kant och en höjdfunktion på hörnen styr genom vilka resterande kanter kan flöda skjutas. Höjdfunktionen ändras genom ommärkning. De korrekta definitionerna av dessa operationer garanterar att den resulterande flödesfunktionen är ett maximalt flöde.
Push -relabel -algoritm med FIFO -toppunktsvalregel	${\ displaystyle O (V^{3})}$	Push-relabel algoritmvariant som alltid väljer den senast aktiva vertexen och utför push-operationer medan överskottet är positivt och det finns tillåtna kvarvarande kanter från denna vertex.
Push -relabel -algoritm med regel för maximalt avstånd för toppunkt	${\ displaystyle O (V^{2} {\ sqrt {E}})}$	Push-relabel algoritmvariant som alltid väljer den mest avlägsna hörnpunkten från eller (dvs den högsta etikettpunkten) men annars fortsätter som FIFO-algoritmen. ${\ displaystyle s}$${\ displaystyle t}$
Push-relabel algoritm med dynamiska träd	${\ displaystyle O \ vänster (VE \ log {\ frac {V^{2}} {E}} \ höger)}$	Algoritmen bygger träd med begränsad storlek på restgrafen angående höjdfunktionen. Dessa träd ger push -operationer på flera nivåer, det vill säga att skjuta längs en hel mättande väg istället för en enda kant.
KRT (King, Rao, Tarjan) algoritm	${\ displaystyle O \ vänster (VE \ log _ {\ frac {E} {V \ log V}} V \ höger)}$
Binär blockeringsflödesalgoritm	${\ displaystyle O \ vänster (E \ cdot \ min \ {V^{2/3}, E^{1/2} \} \ cdot \ log {\ frac {V^{2}} {E}} \ cdot \ log U \ höger)}$	Värdet U motsvarar nätets maximala kapacitet.
James B Orlins + KRT (King, Rao, Tarjan) algoritm	${\ displaystyle O (VE)}$	Orlins algoritm löser maxflöde i tid för medan KRT löser det för . ${\ displaystyle O (VE)}$${\ displaystyle E \ leq O (V^{{\ frac {16} {15}}-\ epsilon})}$${\ displaystyle O (VE)}$${\ displaystyle E> V^{1+ \ epsilon}}$
Kathuria-Liu-Sidford algoritm	${\ displaystyle E^{4/3+o (1)} U^{1/3}}$	Inre punktmetoder och kantförstärkning med -normflöden. Byggs på tidigare algoritm för Madry, som uppnådde körtid . ${\ displaystyle \ ell _ {p}}$${\ displaystyle {\ tilde {O}} (E^{10/7} U^{1/7})}$
BLNPSSSW / BLLSSSW -algoritm	${\ displaystyle {\ tilde {O}} ((E+V^{3/2}) \ log U)}$	Interiörpunktsmetoder och dynamiskt underhåll av elektriska flöden med expander -sönderdelningar.
Gao-Liu-Peng-algoritm	${\ displaystyle {\ tilde {O}} (E^{{\ frac {3} {2}}-{\ frac {1} {328}}} \ log U)}$	Gao, Liu och Pengs algoritm kretsar kring att dynamiskt bibehålla de förstärkande elektriska flödena i kärnan i den inre punktmetodbaserade algoritmen från [Mądry JACM '16]. Detta innebär att designa datastrukturer som i begränsade inställningar returnerar kanter med stor elektrisk energi i en graf som genomgår motståndsuppdateringar.

För ytterligare algoritmer, se Goldberg & Tarjan (1988) .

Integrerad flödesats

Integral flödesatsen säger att

Om varje kant i ett flödesnät har integrerad kapacitet finns det ett integrerat maximalt flöde.

Påståendet är inte bara att värdet på flödet är ett heltal, vilket följer direkt från maxflödet min-cut sats , utan att flödet på varje kant är integrerat. Detta är avgörande för många kombinatoriska applikationer (se nedan), där flödet över en kant kan koda om objektet som motsvarar den kanten ska ingå i den uppsatta uppsättningen eller inte.

Ansökan

Multi-source multi-sink maximalt flödesproblem

Fig. 4.1.1. Omvandling av ett flerkällas problem med maximalt flöde till ett flöde med ett enda flöde med ett enda flöde

Med tanke på ett nätverk med en uppsättning källor och en uppsättning sänkor istället för endast en källa och en diskbänk, ska vi hitta det maximala flödet över . Vi kan omvandla multi-source multi-sink-problemet till ett problem med maximalt flöde genom att lägga till en konsoliderad källa som ansluter till varje hörn i och en konsoliderad sink som är ansluten av varje hörn i (även känd som supersource och supersink ) med oändlig kapacitet på varje kant ( Se fig. 4.1.1.). ${\ displaystyle N = (V, E)}$${\ displaystyle S = \ {s_ {1}, \ ldots, s_ {n} \}}$${\ displaystyle T = \ {t_ {1}, \ ldots, t_ {m} \}}$${\ displaystyle N}$${\ displaystyle S}$${\ displaystyle T}$

Maximal kardinalitet tvåpartsmatchning

Fig. 4.3.1. Omvandling av ett maximalt tvåpartsmatchningsproblem till ett problem med maximalt flöde

Med tanke på en tvåpartig graf ska vi hitta en maximal kardinalitetsmatchning i , det vill säga en matchning som innehåller det största möjliga antalet kanter. Detta problem kan omvandlas till ett problem med maximalt flöde genom att bygga ett nätverk , där ${\ displaystyle G = (X \ cup Y, E)}$${\ displaystyle G}$${\ displaystyle N = (X \ cup Y \ cup \ {s, t \}, E ')}$

1. ${\ displaystyle E '}$innehåller kanterna i riktade från till .${\ displaystyle G}$${\ displaystyle X}$${\ displaystyle Y}$
2. ${\ displaystyle (s, x) \ in E '}$för var och en för varje .${\ displaystyle x \ i X}$${\ displaystyle (y, t) \ i E '}$${\ displaystyle y \ i Y}$
3. ${\ displaystyle c (e) = 1}$för varje (Se bild 4.3.1).${\ displaystyle e \ i E '}$

Då är värdet på det maximala flödet in lika med storleken på det maximala matchningsvärdet , och en maximal kardinalitetsmatchning kan hittas genom att ta de kanter som har flöde i ett integrerat maxflöde. ${\ displaystyle N}$${\ displaystyle G}$${\ displaystyle 1}$

Minsta sökväg i riktad acyklisk graf

Med tanke på en riktad acyklisk graf ska vi hitta det minsta antalet vertex-disjoint-vägar för att täcka varje toppunkt i . Vi kan konstruera en tvåpartig graf från , var ${\ displaystyle G = (V, E)}$${\ displaystyle V}$${\ displaystyle G '= (V _ {\ textrm {out}} \ cup V _ {\ textrm {in}}, E')}$${\ displaystyle G}$

1. ${\ displaystyle V _ {\ textrm {out}} = \ {v _ {\ textrm {out}} \ mid v \ i V \ land v {\ text {har utgående kant (er)}} \}}$
2. ${\ displaystyle V _ {\ textrm {in}} = \ {v _ {\ textrm {in}} \ mid v \ i V \ land v {\ text {har inkommande kant (er)}} \}}$
3. ${\ displaystyle E '= \ {(u _ {\ textrm {out}}, v _ {\ textrm {in}}) \ in V_ {out} \ gånger V_ {in} \ mid (u, v) \ i E \ }}$.

Då kan det visas som har en matchning av storlek om och endast om det har ett hörn-oskarvigt banöverdrag med innehållande kanter och banor, var är antalet hörn i . Därför kan problemet lösas genom att hitta den maximala kardinalitetsmatchningen i stället. ${\ displaystyle G '}$${\ displaystyle M}$${\ displaystyle m}$${\ displaystyle G}$${\ displaystyle C}$${\ displaystyle m}$${\ displaystyle nm}$${\ displaystyle n}$${\ displaystyle G}$${\ displaystyle G '}$

Intuitivt, om två hörn matchas in , så finns kanten i . Tydligt antalet kanter i är . För att se att det är vertex-disjoint, överväg följande: ${\ displaystyle u _ {\ mathrm {out}}, v _ {\ mathrm {in}}}$${\ displaystyle M}$${\ displaystyle (u, v)}$${\ displaystyle C}$${\ displaystyle C}$${\ displaystyle m}$${\ displaystyle C}$

1. Varje hörn i kan antingen inte matchas in , i vilket fall finns det inga kanter som lämnar in ; eller det kan matchas , i så fall är det exakt en kant som lämnar in . I båda fallen inte mer än en kant lämnar någon vertex i .${\ displaystyle v _ {\ textrm {out}}}$${\ displaystyle G '}$${\ displaystyle M}$${\ displaystyle v}$${\ displaystyle C}$${\ displaystyle v}$${\ displaystyle C}$${\ displaystyle v}$${\ displaystyle C}$
2. På samma sätt för varje hörn i - om det matchas finns det en enda inkommande kant in i ; har annars inga inkommande kanter i .${\ displaystyle v _ {\ textrm {i}}}$${\ displaystyle G '}$${\ displaystyle v}$${\ displaystyle C}$${\ displaystyle v}$${\ displaystyle C}$

Således har ingen hörn två inkommande eller två utgående kanter in , vilket betyder att alla vägar in är vertex-disjoint. ${\ displaystyle C}$${\ displaystyle C}$

För att visa att omslaget har storlek börjar vi med ett tomt omslag och bygger det stegvis. För att lägga till en toppunkt på omslaget kan vi antingen lägga till det i en befintlig sökväg eller skapa en ny väg med längd noll som börjar vid den punkten. Det tidigare fallet är tillämpligt när som helst och någon väg i omslaget börjar vid , eller och någon väg slutar vid . Det senare fallet är alltid tillämpligt. I det förra fallet ökas det totala antalet kanter i omslaget med 1 och antalet vägar förblir detsamma; i det senare fallet ökas antalet vägar och antalet kanter förblir detsamma. Det är nu klart att efter att ha täckt alla hörn är summan av antalet banor och kanter i omslaget . Därför, om antalet kanter i omslaget är , är antalet sökvägar . ${\ displaystyle C}$${\ displaystyle nm}$${\ displaystyle u}$${\ displaystyle (u, v) \ i E}$${\ displaystyle v}$${\ displaystyle (v, u) \ i E}$${\ displaystyle v}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle nm}$

Maximalt flöde med toppunktskapacitet

Fig. 4.4.1. Transformation av ett problem med maximalt flöde med vertexkapacitetsbegränsning till det ursprungliga maximala flödesproblemet genom noddelning

Låt vara ett nätverk. Antag att det finns kapacitet vid varje nod utöver kantkapacitet, det vill säga en kartläggning så att flödet måste uppfylla inte bara kapacitetsbegränsningen och bevarandet av flöden, utan också toppunktskapacitetsbegränsningen ${\ displaystyle N = (V, E)}$${\ displaystyle c: V \ to \ mathbb {R} ^{+},}$${\ displaystyle f}$

${\ displaystyle \ sum _ {i \ i V} f_ {iv} \ leq c (v) \ qquad \ forall v \ i V \ backslash \ {s, t \}.}$

Med andra ord kan mängden flöde som passerar genom en toppunkt inte överstiga dess kapacitet. För att hitta det maximala flödet över kan vi omvandla problemet till det maximala flödesproblemet i ursprunglig mening genom att expandera . Först ersätts var och en med och , där är ansluten av kanter som går in i och är anslutna till kanter som kommer ut från , tilldelar sedan kapacitet till kantanslutningen och (se fig. 4.4.1). I detta utvidgade nätverk tas vertex -kapacitetsbegränsningen bort och därför kan problemet behandlas som det ursprungliga maximala flödesproblemet. ${\ displaystyle N}$${\ displaystyle N}$${\ displaystyle v \ i V}$${\ displaystyle v _ {\ text {i}}}$${\ displaystyle v _ {\ text {out}}}$${\ displaystyle v _ {\ text {i}}}$${\ displaystyle v}$${\ displaystyle v _ {\ text {out}}}$${\ displaystyle v}$${\ displaystyle c (v)}$${\ displaystyle v _ {\ text {i}}}$${\ displaystyle v _ {\ text {out}}}$

Maximalt antal vägar från s till t

Med tanke på en riktad graf och två hörn och ska vi hitta det maximala antalet vägar från till . Detta problem har flera varianter: ${\ displaystyle G = (V, E)}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle t}$

1. Banorna måste vara kantlösa. Detta problem kan omvandlas till ett problem med maximalt flöde genom att konstruera ett nätverk från , med respektive vara källan och sinken för respektive, och tilldela varje kant en kapacitet på . I detta nätverk är det maximala flödet om det finns kant-disjoint-vägar. ${\ displaystyle N = (V, E)}$${\ displaystyle G}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle N}$${\ displaystyle 1}$${\ displaystyle k}$${\ displaystyle k}$

2. Banorna måste vara oberoende, dvs vertex-disjoint (förutom och ). Vi kan bygga ett nätverk från med toppunktskapacitet, där kapaciteten hos alla hörn och alla kanter är . Då är värdet på det maximala flödet lika med det maximala antalet oberoende vägar från till . ${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle N = (V, E)}$${\ displaystyle G}$${\ displaystyle 1}$${\ displaystyle s}$${\ displaystyle t}$

3. Förutom att vägarna är kantskilda och/eller hörnskilda har vägarna också en längdbegränsning: vi räknar bara vägar vars längd är exakt , eller högst . De flesta varianter av detta problem är NP-kompletta, förutom små värden på . ${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$

Stängningsproblem

En tillslutning av en riktad graf är en uppsättning hörn C , så att inga kanter lämnar C . Den förslutnings problem är uppgiften att hitta den maximala-vikt eller minimum-viktförslutning i en vertex vägda riktad graf. Det kan lösas på polynomtid med hjälp av en minskning till det maximala flödesproblemet.

Verkliga applikationer

Eliminering av baseboll

Konstruktion av nätverksflöde för elimineringsproblem med baseball

I basebollelimineringsproblemet finns det n lag som tävlar i en liga. I ett specifikt skede av ligasäsongen är w _i antalet vinster och r _i är antalet matcher kvar att spela för lag i och r _ij är antalet matcher kvar mot lag j . Ett lag elimineras om det inte har någon chans att avsluta säsongen i första hand. Uppgiften med basebollelimineringsproblemet är att avgöra vilka lag som elimineras vid varje punkt under säsongen. Schwartz föreslog en metod som reducerar detta problem till maximalt nätverksflöde. I denna metod skapas ett nätverk för att avgöra om lag k elimineras.

Låt G = ( V , E ) vara ett nätverk med s , t ∈ V är källan respektive sinken. Man lägger till en spelenod _ij - som representerar antalet spel mellan dessa två lag. Vi lägger också till en lagnod för varje lag och ansluter varje spelnod { i , j } med i < j till V , och ansluter var och en av dem från s med en kant med kapacitet r _ij - vilket representerar antalet spel mellan dessa två lag. Vi lägger också till en lagnod för varje lag och ansluter varje spelnod { i , j } med två lagnoder i och j för att säkerställa att en av dem vinner. Man behöver inte begränsa flödesvärdet på dessa kanter. Slutligen görs kanterna från lagnod i till disknoden t och kapaciteten för w _k + r _k - w _i är inställd på att förhindra att lag i vinner mer än w _k + r _k . Låt S vara uppsättningen för alla lag som deltar i ligan och låt

${\ displaystyle r (S-\ {k \}) = \ sum _ {i, j \ in \ {S-\ {k \} \} \ ovanpå i <j} r_ {ij}}$.

I denna metod det påstås laget k elimineras inte om och endast om en flödesvärde på storleken r ( S - { k }) existerar i nätet G . I den nämnda artikeln är det bevisat att detta flödesvärde är det maximala flödesvärdet från s till t .

Schemaläggning av flygbolag

Inom flygindustrin är ett stort problem schemaläggningen av flygbesättningarna. Flygbolagets schemaläggningsproblem kan betraktas som en tillämpning av utökat maximalt nätverksflöde. Ingången till detta problem är en uppsättning flygningar F som innehåller information om var och när varje flygning avgår och anländer. I en version av flygplansschemaläggning är målet att ta fram ett genomförbart schema med högst k besättningar.

För att lösa detta problem använder man en variation av cirkulationsproblemet som kallas begränsad cirkulation som är generaliseringen av nätverksflödesproblem , med den extra begränsningen av en nedre gräns för kantflöden.

Låt G = ( V , E ) vara ett nätverk med s , t ∈ V som källa och sink -noder. För källan och destinationen för varje flygning i lägger man till två noder till V , nod s _i som källa och nod d _i som destinationsnod för flygning i . Man lägger också till följande kanter till E :

1. En kant med kapacitet [0, 1] mellan s och varje s _i .
2. En kant med kapacitet [0, 1] mellan varje d _i och t .
3. En kant med kapacitet [1, 1] mellan varje par av s _i och d _i .
4. En kant med kapacitet [0, 1] mellan varje d _i och s _j , om källan s _j kan nås med en rimlig mängd tid och kostnad från destinationen av flyg i .
5. En kant med kapacitet [0, ∞ ] mellan s och t .

I den nämnda metoden påstås och bevisas att att hitta ett flödesvärde av k i G mellan s och t är lika med att hitta ett genomförbart schema för flyguppsättning F med högst k besättningar.

En annan version av flygplanering är att hitta de lägsta besättningar som behövs för att utföra alla flygningar. I syfte att hitta ett svar på detta problem, en tvådelad graf G' = ( A ∪ B , E ) skapas där varje flygning har en kopia i uppsättning A och uppsättning B . Om samma plan kan utföra flygningen j efter flygning i , i ∈ A är ansluten till j ∈ B . En matchning i G ' inducerar ett schema för F och uppenbarligen maximal bipartitmatchning i denna graf ger ett flygplansschema med minimalt antal besättningar. Som det nämns i applikationsdelen av denna artikel är den maximala kardinalitetsbipartitmatchningen en tillämpning av problem med maximalt flöde.

Problem med cirkulation - efterfrågan

Det finns några fabriker som producerar varor och vissa byar där varorna måste levereras. De är anslutna med ett nätverk av vägar där varje väg har kapacitet c för maximalt gods som kan flöda genom den. Problemet är att hitta om det finns en upplaga som tillgodoser efterfrågan. Detta problem kan omvandlas till ett problem med maximalt flöde.

1. Lägga till en källnod s och lägga kanter från den till varje fabrik nod f _jag med kapacitet p _jag där p _i är produktionshastigheten för fabriken f _i .
2. Lägg till en disknod t och lägg till kanter från alla byar v _i till t med kapacitet d _i där d _i är efterfrågan på byn v _i .

Låt G = ( V , E ) vara detta nya nätverk. Det finns en upplaga som tillgodoser efterfrågan om och endast om:

Maximalt flödesvärde ( G ) .${\ displaystyle = \ sum _ {i \ in v} d_ {i}}$

Om det finns en cirkulation, skulle titta på maxflödeslösningen ge svaret på hur mycket varor som måste skickas på en viss väg för att uppfylla kraven.

Problemet kan utökas genom att lägga till en nedre gräns för flödet på vissa kanter.

Bildsegmentering

Källbild i storlek 8x8.

Nätverk byggt från bitmappen. Källan är till vänster, diskbänken till höger. Ju mörkare en kant är, desto större är dess kapacitet. a _i är hög när pixeln är grön, b _i när pixeln inte är grön. Straffen p _ij är alla lika.

I sin bok presenterar Kleinberg och Tardos en algoritm för att segmentera en bild. De presenterar en algoritm för att hitta bakgrunden och förgrunden i en bild. Mer exakt tar algoritmen en bitmapp som en ingång modellerad enligt följande: a _i ≥ 0 är sannolikheten för att pixel i tillhör förgrunden, b _i ≥ 0 med sannolikhet att pixel i tillhör bakgrunden och p _ij är straff om två intilliggande pixlar i och j placeras en i förgrunden och den andra i bakgrunden. Målet är att hitta en partition ( A , B ) av uppsättningen pixlar som maximerar följande kvantitet

${\ displaystyle q (A, B) = \ sum _ {i \ i A} a_ {i}+\ sum _ {i \ i B} b_ {i}-\ sum _ {\ begin {matris} i, j {\ text {intilliggande}} \\ | A \ cap \ {i, j \} | = 1 \ end {matris}} p_ {ij}}$,

För pixlar i A (betraktas som förgrunden) får vi faktiskt ett _i ; för alla pixlar i B (betraktas som bakgrunden) får vi b _i . På gränsen, mellan två intilliggande pixlar i och j , tappar vi p _ij . Det motsvarar att minimera mängden

${\ displaystyle q '(A, B) = \ sum _ {i \ i A} b_ {i}+\ sum _ {i \ i B} a_ {i}+\ sum _ {\ begin {matris} i, j {\ text {intilliggande}} \\ | A \ cap \ {i, j \} | = 1 \ end {matris}} p_ {ij}}$

eftersom

${\ displaystyle q (A, B) = \ sum _ {i \ i A \ cup B} a_ {i}+\ sum _ {i \ i A \ cup B} b_ {i} -q '(A, B ).}$

Minsta nedskärning som visas på nätverket (trianglar VS cirklar).

Vi konstruerar nu nätverket vars noder är pixeln, plus en källa och en sink, se figur till höger. Vi ansluter källan till pixel i med en viktkant a _i . Vi ansluter pixeln i till diskbänken med en viktkant b _i . Vi ansluter pixel i till pixel j med vikten p _ij . Nu återstår att beräkna en minsta nedskärning i det nätverket (eller motsvarande ett maximalt flöde). Den sista siffran visar en minimiskärning.

Tillägg

1. I minimikostnadsflödesproblemet har varje kant ( u , v) också en kostnadskoefficient a _uv utöver dess kapacitet. Om flödet genom kanten är f _uv , är den totala kostnaden en _uv f _uv . Det krävs för att hitta ett flöde av en given storlek d , med den minsta kostnaden. I de flesta varianter kan kostnadskoefficienterna vara antingen positiva eller negativa. Det finns olika algoritmer för polynom-tid för detta problem.

2. Problemet med maximal flöde kan förstärkas med disjunktiva begränsningar : en negativ disjunktiv begränsning säger att ett visst par kanter samtidigt inte kan ha ett flöde utan noll; en positiv disjunktiv begränsning säger att i ett visst par kanter måste åtminstone en ha ett flöde utan noll. Med negativa begränsningar blir problemet starkt NP-hårt även för enkla nätverk. Med positiva begränsningar är problemet polynom om fraktionsflöden tillåts, men kan vara starkt NP-hårda när flödena måste vara integrerade.

Referenser

Vidare läsning

• Joseph Cheriyan och Kurt Mehlhorn (1999). "En analys av urvalsregeln på högsta nivå i algoritmen för preflow-push-maxflöde". Informationsbehandlingsbrev . 69 (5): 239–242. CiteSeerX  10.1.1.42.8563 . doi : 10.1016/S0020-0190 (99) 00019-8 .
• Daniel D. Sleator och Robert E. Tarjan (1983). "En datastruktur för dynamiska träd" (PDF) . Journal of Computer and System Sciences . 26 (3): 362–391. doi : 10.1016/0022-0000 (83) 90006-5 . ISSN  0022-0000 .
• Eugene Lawler (2001). "4. Nätverksflöden". Kombinerande optimering: Nätverk och Matroids . Dover. s. 109–177. ISBN 978-0-486-41453-9.