maximum flow problem

Angol

Főnév

maximum flow problem (tsz. maximum flow problems)

1. (informatika) A maximum flow problem – magyarul: maximális áramlási probléma – egy klasszikus gráfelméleti optimalizálási feladat, amely azt vizsgálja, hogy egy irányított hálózatban mekkora az a legnagyobb mennyiségű áramlás, amely a forrás (source) csúcspontból a nyelő (sink) csúcspontba eljuttatható úgy, hogy ne lépjük túl az élek kapacitását.

---

🧠 1. Alapfogalom

Adott egy irányított gráf ${\textstyle G=(V,E)}$, ahol minden élhez ${\textstyle c(u,v)}$ kapacitás tartozik. A cél: maximalizálni az S → T közti áramlást, ahol:

• ${\textstyle S}$: forrás
• ${\textstyle T}$: nyelő
• ${\textstyle f(u,v)}$: az aktuális áramlás az élen
• ${\textstyle f(u,v)\leq c(u,v)}$: nem léphetjük túl a kapacitást

---

📐 2. Feltételek

A megoldásnak teljesítenie kell:

• Kapacitáskorlát: minden élen ${\textstyle 0\leq f(u,v)\leq c(u,v)}$
• Áramlás megmaradása: minden csúcspontban, ami nem ${\textstyle S}$ vagy ${\textstyle T}$, az összbefolyás = összkiáramlás

---

💧 3. Alkalmazások

• 📦 Szállítási és logisztikai hálózatok
• 🌐 Internetes adatforgalom modellezése
• 🧬 Biológiai hálózatok (pl. metabolizmus)
• 🧮 Képfeldolgozás (pl. szegmentálás: min-cut/max-flow)
• 🔐 Információáramlás, biztonsági rendszerek

---

⚙️ 4. Népszerű algoritmusok

A. Ford-Fulkerson algoritmus

• Alapötlet: keresni egy utat a maradékgráfban, amin még lehet „több” áramlást vinni
• Ha van ilyen út, növeljük az áramlást
• Ismételjük, amíg nincs több augmentáló út

➡️ Nem mindig hatékony végtelen pontosságú számoknál

---

B. Edmonds-Karp algoritmus

• A Ford-Fulkerson algoritmus BFS-re épülő változata
• Polinomiális idő: ${\textstyle O(VE^{2})}$
• Mindig a legrövidebb augmentáló utat keresi

---

C. Dinic algoritmus

• Többszintű BFS és blokkfolyam
• Gyorsabb: ${\textstyle O(V^{2}E)}$ vagy jobb bizonyos gráfokon

---

🔧 5. Példa

Adott egy egyszerű gráf:

  S
 / \
10  5
/     \
A       B
 \     /
  5   10
   \ /
    T

• Az S→A kapacitás: 10, S→B: 5
• A→T: 5, B→T: 10

Maximális áramlás: 10 (S→A→T = 5, S→B→T = 5)

---

🧾 6. Összefoglalás

A maximum flow problem:

• Egy alapvető gráfelméleti és hálózati optimalizálási probléma
• Megoldása segít szállítási, adat-, pénz- vagy energiaáramlási feladatokban
• Klasszikus algoritmusok: Ford-Fulkerson, Edmonds-Karp, Dinic
• Sokszor alapul szolgál min-cut, matching, cirkulációs vagy kapacitásbővítési problémákhoz

További információk

• maximum flow problem - Szótár.net (en-hu)
• maximum flow problem - Sztaki (en-hu)
• maximum flow problem - Merriam–Webster
• maximum flow problem - Cambridge
• maximum flow problem - WordNet
• maximum flow problem - Яндекс (en-ru)
• maximum flow problem - Google (en-hu)
• maximum flow problem - Wikidata
• maximum flow problem - Wikipédia (angol)