Ford-Fulkerson-tétel

Magyar

Kiejtés

• IPA: [ ˈfortfulkɛrʃonteːtɛl]

Főnév

Ford-Fulkerson-tétel

1. (matematika)

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(VE^{2})$ időben fut.

További információk

• Ford-Fulkerson-tétel - Értelmező szótár (MEK)
• Ford-Fulkerson-tétel - Etimológiai szótár (UMIL)
• Ford-Fulkerson-tétel - Szótár.net (hu-hu)
• Ford-Fulkerson-tétel - DeepL (hu-de)
• Ford-Fulkerson-tétel - Яндекс (hu-ru)
• Ford-Fulkerson-tétel - Google (hu-en)
• Ford-Fulkerson-tétel - Helyesírási szótár (MTA)
• Ford-Fulkerson-tétel - Wikidata
• Ford-Fulkerson-tétel - Wikipédia (magyar)