Ford-Fulkerson-tétel

1. Sablon:Label

Ford–Fulkerson-tétel

A **Ford–Fulkerson-tétel** a hálózatok áramláselméletének egyik alapvető tétele. Ez a tétel kapcsolatot teremt a maximális áramlás és a minimális vágás között egy irányított gráfban.

A tétel megfogalmazása

Legyen $G=(V,E)$ egy irányított gráf, ahol:

• $s$ az áramlás forrása,
• $t$ az áramlás nyelője,
• $c(u,v)$ az $u$ és $v$ csúcsok közötti él kapacitása.

A **Ford–Fulkerson-tétel** kimondja: $\text{A forrásból a nyelőbe vezethető maximális áramlás értéke megegyezik a gráf minimális vágásának kapacitásával.}$

Formálisan: $\max (\text{Flow})=\min (\text{Cut}),$ ahol a **vágás** ($\text{Cut}$) a gráf csúcsainak egy olyan partíciója, amely elválasztja a forrást és a nyelőt, és a vágás kapacitása az ehhez tartozó élek kapacitásainak összege.

Ford–Fulkerson-algoritmus

A tétel alapja a **Ford–Fulkerson-algoritmus**, amely iteratív módon keresi a maximális áramlást: 1. Kezdjük az áramlást nullával ($f(u,v)=0$ minden élre). 2. Keressünk egy **feljavító utat** ($s$-től $t$-ig) a reziduális gráfban, ahol az élek kapacitása nagyobb 0-nál. 3. Frissítsük az áramlást az út mentén, és állítsuk elő az új reziduális gráfot. 4. Ismételjük, amíg nem található több feljavító út.

Az algoritmus véges kapacitású élek esetén mindig konvergál a maximális áramlás értékéhez.

Példa

Legyen egy hálózat 4 csúccsal:

• $s$: forrás,
• $t$: nyelő,
• Élek és kapacitások:

 * $(s,A):10$,
 * $(s,B):5$,
 * $(A,B):15$,
 * $(A,t):10$,
 * $(B,t):10$.

1. Kezdeti reziduális gráf:

  $c(s,A)=10,c(s,B)=5,c(A,B)=15,c(A,t)=10,c(B,t)=10.$

2. Első feljavító út: $s\to A\to t$, kapacitás $10$. 3. Második feljavító út: $s\to B\to t$, kapacitás $5$. 4. A maximális áramlás értéke: $10+5=15$.

A minimális vágás az $\{s\}$ és $\{A,B,t\}$ csúcshalmazok közötti vágás, amelynek kapacitása szintén $15$.

Következmények

A Ford–Fulkerson-tétel és algoritmus alkalmazásai:

• **Hálózatok optimalizálása:** Pl. adatforgalom maximalizálása egy számítógépes hálózatban.
• **Kapacitástervezés:** Pl. energia- vagy vízellátási hálózatok tervezése.
• **Kétoldali párosítások:** Bipartit gráfok maximális párosításának meghatározása.
• **Minimális vágás probléma:** A tétel a minimális vágás gyors meghatározására is alkalmazható.

További megjegyzések

• Az algoritmus teljesítménye a kapacitások értékétől függ, mivel véges kapacitás esetén mindig terminál, de irracionális kapacitások mellett végtelen ciklusba kerülhet.
• Az Edmonds–Karp algoritmus egy hatékony implementációja a Ford–Fulkerson módszernek, amely a szélességi keresést használja feljavító utak keresésére, és garantáltan $O(V{E}^2)$ időben fut.

Sablon:Hunl