Begrenzing van het aantal iteraties in het max-flow algoritme Het oplossen van het maximum stroom probleem met behulp van stroomvermeerderende paden werkt, maar het aantal iteraties kan aardig de spuigaten uitlopen wanneer je niet uitkijkt. Indien alle capaciteiten geheeltallig zijn, dan weet je dat je in iedere iteratie de stroom met minstens ´e´en verhoogt, en dus is het aantal iteraties beperkt tot de capaciteit van de minimale snede. Dit is in het algemeen echter niet polynomiaal, zoals volgt uit het volgende voorbeeld (waarbij je niet zo slim de stroomvermeerderende paden kiest): 1j M sj e
@ R @
M
e @ @ R1 @ @
M@ @e 2j
3j
e @ RM @ @ @e tj
@ @e M 4j M
-
De maximumstroom is natuurlijk gelijk aan 2M , maar je zou kunnen beginnen met ´e´en eenheid stroom te sturen via het pad (s, 1)(1, 4)(4, t). Nu klapt de pijl (1, 4) om in de residuele graaf, waarna je het stroomvermeerderende pad (s, 2)(2, 4), (4, 1), (1, 3), (3, t) zou kunnen vinden, waarover je de stroom ´e´en eenheid kan verhogen. De pijl (1, 4) is weer leeg, zodat je het pad (s, 1)(1, 4)(4, t) weer kunt gebruiken, enz. Dan vind je na 2M iteraties eindelijk de optimale stroom. Het schijnt nog erger te zijn in geval van niet-geheeltallige capaciteiten: dan kun je bij een slechte keuze van je stroomvermeerderende paden naar een niet-optimale oplossing convergeren. Om deze problemen te voorkomen wordt er bij de keuze van het stroomvermeerderende pad niet zo maar een pad gekozen, maar een pad dat zo min mogelijk pijlen bevat. Dinic heeft bewezen dat je dan in maximaal |V | · |A| iteraties een maximale stroom vindt, ongeacht of de capaciteiten geheeltallig zijn. Stelling van Dinic Wanneer in de residuele graaf steeds een stroomvermeerderend pad wordt gekozen met een minimaal aantal pijlen, dan bedraagt het aantal iteraties ten hoogste |V | · |A|. Bewijs Definieer D1 , D2 , · · · als de reeks van residuele grafen in iteratie 1, 2, · · ·. Definieer ϕ(Di ) als de afstand van s naar t in Di (iedere pijl heeft lengte 1) en definieer ψ(Di ) als het aantal pijlen dat in tenminste ´e´en kortste pad in Di van s naar t voorkomt. Hiervoor geldt ϕ(Di ) ≤ |V | (een kortste pad bevat geen cykels) en ψ(Di ) ≤ |A| (wanneer zowel (v, w) als (w, v) in een kortste pad van s naar t in Di voorkomen, dan hebben die paden de vorm (s → v)(v, w)(w → t) en (s → w)(w, v)(v → t), waarbij s → v een pad van s naar v aangeeft. Door deze paden te combineren, kun je een korter pad van s naar t in Di vinden: Tegenspraak). Het bewijs is gebaseerd op het bewijzen van de volgende twee claims: 1. ϕ(Di+1 ) ≥ ϕ(Di ) (paden worden niet korter); 2. als ϕ(Di+1 ) = ϕ(Di ), dan geldt ψ(Di+1 ) < ψ(Di ). Uit deze beide claims en ϕ(Di ) ≤ |V | en ψ(Di ) ≤ |A| volgt dan de correctheid van de stelling. Voor het bewijs van de claims hebben we het volgende hulpresultaat nodig.
Lemma Beschouw een willekeurige iteratie i. Definieer αv als de afstand van s naar v in Di voor alle v ∈ V ; dus αs = 0 en αt = ϕ(Di ). Nu geldt voor iedere pijl (v, w) ∈ Di+1 : αw ≤ αv + 1 als (v, w) ∈ Di αw ≤ αv − 1 als (w, v) ∈ Di
)
⇒ αw − αv ≤ 1 .
Bewijs lemma. Wanneer (v, w) ∈ Di , dan is (s → v)(v, w) een pad in Di met lengte αv + 1, dus de lengte van het kortste pad van s naar w in Di heeft lengte αw ≤ αv + 1. Wanneer (w, v) ∈ Di en (v, w) 6∈ Di , dan is de pijl (v, w) in Di+1 gekomen door (w, v) in het stroomvermeerderende pad te gebruiken; dit stroomvermeerderende pad P is van de vorm (s → w)(w, v)(v → t) en heeft minimale lengte. De stukken (s → w) en (s → w)(w, v) vormen dus een pad van minimale lengte van s naar w en v, respectievelijk. Hieruit volgt αv = αw + 1. Bewijs claims. Stel (s, v1 , . . . , vk−1 , t) is een kortste pad van s naar t in Di+1 , dus ϕ(Di+1 ) = k. Aangezien (s, v1 ), . . . , (vk−1 , t) ∈ Di+1 , volgt uit het lemma dat αt − αvk−1 ≤ 1, · · · , αv1 − αs ≤ 1. Uit deze ongelijkheden volgt ϕ(Di+1 ) = k · 1 ≥ (αt − αvk−1 ) + (αvk−1 − αvk−2 ) + · · · + (αv1 − αs ) = αt − αs = ϕ(Di ); dit bewijst Claim 1. Gelijkheid van ψ(Di+1 ) en ψ(Di ) kan alleen optreden wanneer αt − αvk−1 = 1, · · · , αv1 − αs = 1, dus wanneer alle pijlen (s, v1 ), . . . , (vk−1 , t) in Di zitten. Dit moet voor ieder kortste pad van s naar t in Di+1 gelden, dus alle pijlen die in een kortste pad van s naar t in Di+1 zitten, zitten ook in een kortste pad van s naar t in Di ; hieruit volgt ψ(Di+1 ) ≤ ψ(Di ). Gelijkheid kan zich echter niet voordoen, want minstens ´e´en pijl in het gebruikte stroomvermeerderende pad in Di wordt ‘volgetankt’ en komt niet terug in Di+1 .
Min-cost max-flow Uiteraard is niets in het leven gratis, en daarom veronderstellen we vanaf nu dat je voor het transport van stroom moet betalen. We nemen aan dat er geen vaste kosten zijn; de kosten om ´e´en eenheid stroom door een pijl (i, j) te sturen bedragen kij . Het doel is nog steeds om een stroom van maximale omvang te vinden, maar uit de verzameling van stromen van maximale omvang zoeken we eentje met minimale kosten. We gebruiken de notatie dat voor een gegeven stroom x (hoeft niet maximaal te zijn) kost(x) en omvang(x) de kosten en omvang van x aangeven. We gaan in het onderstaande steeds uit van een gerichte graaf G = (V, A), waarbij de bron s en de put t zijn gegeven. De capaciteit en kosten van een pijl (i, j) ∈ A worden aangeduid met cij en kij . Definitie. Een stroom x heet een min-cost stroom wanneer kost(x) minimaal is binnen de verzameling van stromen met omvang gelijk aan omvang(x).
˜ = (V, A) ˜ op. Geef aan iedere pijl (i, j) ∈ A˜ een Gegeven een stroom x, stel de residuele graaf G lengte l(i, j), waarbij (
l(i, j) =
kij als (i, j) ∈ A −kji als (j, i) ∈ A
Wanneer zowel (i, j) als (j, i) in A zitten, dan kies je voor l(i, j) de kleinste waarde. Stelling. ˜ = (V, A) ˜ is de bij x horende residuele graaf. Bepaal in G ˜ Stel x is een min-cost stroom; stel G een stroomvermeerderend pad van minimale lengte (op basis van de afstanden l(i, j)). Verhoog x volgens dat stroomvermeerderende pad; noem de nieuwe stroom x0 . Dan is x0 ook een min-cost stroom. Bewijs. We gaan bewijzen dat voor iedere stroom y 0 met omvang(y 0 ) = omvang(x0 ) geldt dat kost(y 0 ) ≥ kost(x0 ). ˜ op basis van de afstanden l(i, j). Definieer voor alle v ∈ V φ(v) als de afstand van v naar t in G 0 0 Definieer = omvang(x ) − omvang(x). Stroom x is uit x ontstaan door x te verhogen met op de pijlen in voorwaartse richting op het stroomvermeerderende pad en door x te verlagen met op de pijlen in achterwaartse richting op het stroomvermeerderende pad, dus cost(x0 ) = cost(x) + maal de lengte van het stroomvermeerderende pad. Aangezien het pad minimale lengte heeft, geldt kost(x0 ) = kost(x) + φ(s). We gaan nu een grens afleiden voor kost(y 0 ) − kost(x). Hulpresultaat. Voor alle (i, j) ∈ A geldt 0 > x , dan k = l(i, j) ≥ φ(i) − φ(j). • Als yij ij ij 0 < x , dan k ≤ −l(j, i) ≤ φ(i) − φ(j). • Als yij ij ij
Bewijs hulpresultaat. 0 > x , dan zat de pijl (i, j) dus niet vol, en derhalve zit (i, j) in de residuele graaf. Als yij ij Vanwege de bepaling van l(i, j) geldt dan kij ≥ l(i, j) (geen gelijkheid, want (j, i) kan ook tot A behoren). Aangezien φ(i) gelijk is aan de afstand van i naar t en het pad (i, j), (j → t) een mogelijkheid is, volgt φ(i) ≤ l(i, j) + φ(j). ˜ Voor het bewijzen van de tweede ongelijkheid gebruiken we dat uit xij > 0 volgt dat (j, i) ∈ A, zodat l(j, i) ≤ −kij of te wel, kij ≤ −l(j, i). Verder geldt als boven dat φ(j) ≤ l(j, i) + φ(i), en dus −l(j, i) ≤ φ(i) − φ(j). Uit het hulpresultaat volgt 0 0 kij (yij − xij ) ≥ (φ(i) − φ(j))(yij − xij ).
Dit geeft kost(y 0 ) − kost(x) =
X (i,j)∈A
0 kij (yij − xij ) ≥
X
0 (φ(i) − φ(j))(yij − xij ).
(i,j)∈A
In deze laatste uitdrukking komt φ(i) voor met een plusteken voor iedere pijl (i, j) ∈ A en met een minteken voor iedere pijl (h, i) ∈ A. Door om te schrijven vinden we X
0 (φ(i) − φ(j))(yij − xij ) =
φ(i)
i∈V
(i,j)∈A
X
X
φ(i)
i∈V
0 yij
(i,j)∈A
−
X
0 yh,i
X
−
φ(i)
0 (yh,i − xhi ) =
(h,i)∈A
X i∈V
(h,i)∈A
0 (yij − xij ) −
(i,j)∈A
X
X
X
X
xij −
(i,j)∈A
xh,i .
(h,i)∈A
Aangezien zowel y 0 als x een stroom is, is het stuk tussen rechte haken gelijk aan de uitstroom in i minus de instroom in i, en dit is gelijk aan 0 voor alle i ∈ V \ {s, t}. Verder geldt φ(t) = 0, en het enige dat overblijft van de laatste uitdrukking is
φ(s)
X
(s,j)∈A
0 ysj −
X
0 yh,s − φ(s)
(h,s)∈A
X
(s,j)∈A
xsj −
X
xh,s .
(h,s)∈A
Aangezien het stuk tussen haken precies gelijk is aan de omvang van de betreffende stroom, vinden we dat dit laatste stuk gelijk is aan φ(s)[omvang(y 0 ) − omvang(x)] = φ(s)[omvang(x0 ) − omvang(x)] = φ(s) = kost(x0 ) − kost(x). Wanneer we dit invullen in onze oorspronkelijke afschatting, dan vinden we kost(y 0 ) − kost(x) ≥ kost(x0 ) − kost(x). Dit leidt tot het volgende algorithme: Step 1. Ga uit van de nulstroom. Step 2. Stel de residuele graaf op met lengtefunctie l(i, j). Step 3. Bepaal een stroomvermeerderend pad van minimale lengte in de residuele graaf; wanneer geen stroomvermeerderend pad kan worden gevonden, dan Stop. Step 4. Verhoog de stroom volgens het stroomvermeerderende pad; Ga naar 2. Het bepalen van een kortste pad in de residuele graaf gebeurt met behulp van Bellman-Ford, aangezien er geen negatieve cykels voor kunnen komen in de residuele graaf. Stelling ˜ = (V, A) ˜ geen cykels Als x een min-cost stroom is, dan bevat de bijbehorende residuele graaf G met negatieve lengte. Bewijs. ˜ is met negatieve lengte, dus l(v0 , v1 )+. . . , l(vk , v0 ) < 0. Stel dat (v0 , v1 , . . . , vk , v0 ) een cykel in G Bepaal de capaciteit van alle kanten in dit cykel; stel is het minimum. Pas de stroom als volgt aan: voorwaartse pijlen in het cykel krijgen er aan stroom bij; bij achterwaartse pijlen wordt de stroom met verminderd; en voor de overige kanten verandert de stroom niet. De constructie levert een stroom y op met omvang(y) = omvang(x) en cost(y) =
cost(x) + (l(v0 , v1 ) + . . . , l(vk , v0 )) < cost(x). Tegenspraak. Dit betekent dat je in polynomiale tijd kunt checken of een gegeven stroom een oplossing is van het min-cost max-flow probleem door een snede te geven met capaciteit gelijk aan de omvang van de stroom en door te checken of de bijbehorende residuele graaf een cykel bevat met negatieve lengte. Verder kun je ook nog bewijzen dat de lengte van de gevonden stroomvermeerderende paden niet afneemt; dit is een werkcollege opgave.
