Avancerad

Nätverksflöden

Maximala flöden, min-cut max-flow teoremet och Ford-Fulkerson.

nätverksflöde kapacitet Ford-Fulkerson min-cut max-flow

Tänk dig ett vattenledningssystem där vatten ska transporteras från en källa till en destination genom ett nätverk av rör med olika kapaciteter. Hur mycket vatten kan maximalt transporteras? Detta är essensen av nätverksflöden - ett kraftfullt verktyg som används för allt från internetroutning till logistikoptimering och ekonomiska modeller.

Fördjupning

Ett flödesnätverk är en riktad graf med kapaciteter på kanter och utpekade käll- och sänknoder. Ett flöde måste respektera kapacitetsrestriktioner och flödeskonservering (in = ut för alla noder utom källa/sänk). Max-flöde/min-snitt-satsen ger en fundamental dualitet mellan maximala flöden och minimala snitt. Ford-Fulkerson-algoritmen och dess varianter löser max-flöde-problemet effektivt.

Grundläggande definitioner

Ett flödesnätverk G = (V,E) är en riktad graf med kapacitetsfunktion c: E → ℝ⁺, källnod s och sänknod t. Ett flöde f assignerar ett flödesvärde f(e) till varje kant e så att 0 ≤ f(e) ≤ c(e) och flödeskonservering gäller för alla noder utom s och t.

Flödeskonservering: Σᵢₙ f(e) = Σₒᵤₜ f(e) för alla v ∈ V\{s,t}

Flödesekvationer

För flödesnätverk med noder {s,a,b,t}:

Kapacitetsrestriktioner:

· 0 ≤ f(s,a) ≤ c(s,a)

· 0 ≤ f(s,b) ≤ c(s,b)

· 0 ≤ f(a,t) ≤ c(a,t)

· 0 ≤ f(b,t) ≤ c(b,t)

Flödeskonservering:

· Nod a: f(s,a) = f(a,t)

· Nod b: f(s,b) = f(b,t)

Flödesvärde: |f| = f(s,a) + f(s,b) = f(a,t) + f(b,t)

Max-flöde/min-snitt satsen

Ett snitt (S,T) partitionerar noderna så att s ∈ S och t ∈ T. Snittets kapacitet är summan av kapaciteter för kanter från S till T. Max-flöde/min-snitt-satsen säger att värdet av maximalt flöde equals kapaciteten av minimalt snitt.

Max-flöde/min-snitt: max|f| = min c(S,T)

Bevis av max-flöde/min-snitt (skiss)

Låt f* vara maximalt flöde, (S*,T*) minimalt snitt

≤-riktning: |f*| ≤ c(S*,T*)

· Flöde från S* till T* ≤ kapacitet från S* till T*

· Allt flöde från s till t måste passera snittet

· Därför |f*| ≤ c(S*,T*)

≥-riktning: c(S*,T*) ≤ |f*|

· Konstruera snitt från maximalt flöde

· S = {noder nåbara från s i residualnätverk}

· T = V \ S

· Detta snitt är mättat (full kapacitet används)

· Därför c(S,T) = |f*|

Ford-Fulkerson algoritm

Ford-Fulkerson-algoritmen hittar maximalt flöde genom att iterativt hitta augmenterande vägar i residualnätverket. Residualnätverket innehåller 'bakåtkanter' med kapacitet lika med nuvarande flöde, vilket tillåter 'ångrande' av tidigare flödesbeslut.

Ford-Fulkerson algoritm

Algoritm FordFulkerson(G, s, t):

1. Initiera flöde f(e) = 0 för alla kanter e

2. Medan det finns augmenterande väg P från s till t i Gf:

a. Hitta bottleneck bf = min{cf(e) : e ∈ P}

b. För varje kant e ∈ P:

i. Om e är framåtkant: f(e) += bf

ii. Om e är bakåtkant: f(e) -= bf

c. Uppdatera residualnätverk Gf

3. Returnera f

Tidskomplexitet: O(E × |f*|) för heltaliga kapaciteter

Residualnätverk

Residualnätverk Gf konstrueras från original G och flöde f:

För varje kant (u,v) i G:

· Om f(u,v) < c(u,v): lägg till framåtkant (u,v) med kapacitet c(u,v) - f(u,v)

· Om f(u,v) > 0: lägg till bakåtkant (v,u) med kapacitet f(u,v)

Interpretation:

· Framåtkant: kan skicka mer flöde

· Bakåtkant: kan minska befintligt flöde

· Augmenterande väg = väg från s till t i Gf

Edmonds-Karp algoritm

Edmonds-Karp är en implementation av Ford-Fulkerson som använder BFS för att hitta augmenterande vägar. Detta garanterar kortaste augmenterande väg i varje iteration och ger polynomiell tidskomplexitet O(VE²), oberoende av kapaciteternas storlek.

Varför BFS ger polynomiell tid?

Edmonds-Karp använder BFS för att välja kortaste augmenterande väg:

Nyckel-observation:

· Avstånd från s till noder kan endast öka

· Varje kant kan vara bottleneck i högst E augmenteringar

· Total antal augmenteringar: O(VE)

· Varje BFS tar O(E) tid

Resultat: O(VE²) total tid

Fördel över naiv Ford-Fulkerson:

· Ingen beroende av kapacitetsstorlek

· Garanterat polynomiell även för irrationella kapaciteter

· Praktiskt effektiv för många tillämpningar

Push-relabel algoritmer

Push-relabel algoritmer (Goldberg-Tarjan) arbetar med preflow istället för flöde. De underhåller höjdfunktion och 'pushar' överskottsflöde till högre noder eller 'relablar' noder när push inte är möjlig. Detta ger O(V²E) tid för basic-versionen och O(V³) för FIFO-versionen.

Push-relabel intuition

Preflow: tillåter överskott (in > ut) i noder

Höjdfunktion: h(v) uppskattar avstånd till t

Push-operation:

· Skicka överskott från u till v om h(u) = h(v) + 1

· Minska överskott i u, öka i v

Relabel-operation:

· Öka h(u) när ingen giltig push möjlig

· h(u) = 1 + min{h(v) : (u,v) ∈ Ef}

Terminering:

· När inget överskott finns utom möjligen i s

· Preflow är då maximalt flöde

Tillämpningar

Nätverksflöden har enormt brett tillämpningsområde: transportnätverk, kommunikationsnätverk, produktionssystem, ekonomiska modeller, och kombinatoriska optimeringsproblem. Många problem kan reduceras till max-flöde genom kreativ modellering.

Tillämpning: Maximum bipartite matching

Problem: Hitta maximum matchning i bipartit graf G = (A ∪ B, E)

Reduktion till max-flöde:

1. Lägg till källa s och sänk t

2. Kanter från s till alla noder i A (kapacitet 1)

3. Kanter från alla noder i B till t (kapacitet 1)

4. Originalkanter A → B (kapacitet 1)

Resultat:

· Max-flöde = storlek av maximum matching

· Heltaliga kapaciteter ⟹ heltalsflöde

· Flöde 1 på kant ⟺ kant i matchning

Tillämpning: Edge-disjoint paths

Problem: Hitta maximalt antal kant-disjunkta vägar från s till t

Lösning:

· Sätt alla kapaciteter = 1

· Max-flöde = antal kant-disjunkta vägar

· Konstruera vägar från flödesdekomposition

Generalisering: Node-disjoint paths

· Dela varje nod v i v_in och v_out

· Kant (v_in, v_out) med kapacitet 1

· Originalkanter (u_out, v_in) med kapacitet 1

Vanliga misstag

❌ Glömma flödeskonservering

Inflöde måste equal utflöde för alla noder utom källa och sänk

Exempel: Anta att en melannod 'förbrukar' eller 'producerar' flöde

❌ Förväxla snittkapacitet med flöde över snitt

Snittkapacitet är summa av kapaciteter S→T, flöde kan gå båda hållen

Exempel: Snittkapacitet räknar endast framåtkanter S→T

❌ Missförstå residualnätverk

Bakåtkanter representerar möjlighet att minska flöde, inte öka baklänges

Exempel: Tro att bakåtkant betyder flöde i motsatt riktning

Tillämpningar

Transport och logistik

Optimering av transport- och distributionsnätverk

Exempel: Paketleveranser, järnvägstrafik, flygruttsoptimering

Kommunikationsnätverk

Bandbreddsallokering och routing i nätverk

Exempel: Internet backbone, telekommunikation, datacenters

Kombinatorisk optimering

Många matchnings- och täckningsproblem reduceras till flöden

Exempel: Bipartite matching, vertex covers, edge connectivity

Övningar

1 Medel

Hitta maximalt flöde från s till t i nätverk med kanter: s→a(10), s→b(8), a→b(5), a→t(10), b→t(8).

Tips

Använd Ford-Fulkerson och hitta augmenterande vägar

Visa facit

Väg s→a→t: flöde 10, bottleneck a→t
Väg s→b→t: flöde 8, bottleneck s→b och b→t
Total flöde: 10 + 8 = 18... Fel!
Korrekt: s→a(10), a→t(10) ger flöde 10
s→b(8), b→t(8) ger flöde 8
Men bottleneck vid t är 10+8=18 > kapaciteter
Korrekt max flöde: 16 (begränsat av sänkkapacitet)

Svar: Maximalt flöde = 16

2 Medel

Bevisa att värdet av vilket flöde som helst är ≤ kapaciteten av vilket snitt som helst.

Tips

Använd att allt flöde från s till t måste passera snittet

Visa facit

Svar: Flöde genom snitt ≤ snittkapacitet

Förklaring: För snitt (S,T): flöde från S till T ≤ kapacitet från S till T (inga negativa flöden). Allt s→t flöde måste passera snittet.

3 Svår

Reducer problemet att hitta maximum matching i bipartit graf till max-flöde.

Tips

Lägg till källa och sänk med kapacitet 1

Visa facit

Svar: Källa→A (kap 1), B→sänk (kap 1), originalkanter (kap 1)

Förklaring: Heltaliga kapaciteter ger heltalsflöde. Flöde 1 på originalkant motsvarar matchningskant. Max-flödesvärde = matchningsstorlek.

Sammanfattning

Nätverksflöden modellerar transport av resurser genom kapacitetsbegränsade nätverk. Max-flöde/min-snitt-satsen ger fundamental dualitet. Ford-Fulkerson och Edmonds-Karp använder augmenterande vägar. Push-relabel algoritmer arbetar med preflow. Tillämpningar inkluderar transport, kommunikation och kombinatorisk optimering. Många problem reduceras elegant till max-flöde genom kreativ modellering av kapaciteter och flödeskonservering.