Maximális folyam-minimális vágás tétele

1. Sablon:Label A Maximális folyam – Minimális vágás tétele egy alapvető eredmény a hálózatáramlás elméletében. A tétel kimondja:

 Egy hálózatban a forrásból a nyelőbe irányuló maximális folyam értéke megegyezik az összes minimális vágás kapacitásával.

Fogalmak

Hálózat

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

 * $V$: csúcsok halmaza.
 * $E$: élek halmaza.

- Minden élhez tartozik egy nemnegatív kapacitás $c(u,v)$, amely az $u$-ból $v$-be szállítható maximális mennyiséget jelöli.

Folyam

- Egy hozzárendelés $f(u,v)$ minden élhez, amely teljesíti:

 * **Kapacitáskorlát:** $0\le f(u,v)\le c(u,v)$.
 * **Folytonosság:** Minden csúcson kívül a forrás ($s$) és nyelő ($t$) esetén a bejövő és kimenő folyam összege egyenlő:
   $\sum _{w\in V}f(w,v)=\sum _{w\in V}f(v,w),\mathrm{\forall }v\in V\setminus \{s,t\}.$

Maximális folyam

- A folyam értéke:

 $|f|=\sum _{v\in V}f(s,v),$
 amely a forrásból kilépő összes folyam mennyisége. A maximális folyam a $|f|$-et maximalizáló $f$.

Vágás

- Egy vágás a gráf csúcsainak $S$ és $T$ ($S\cup T=V$, $S\cap T=\mathrm{\varnothing }$) particionálása, ahol $s\in S$ és $t\in T$. - A vágás kapacitása:

 $c(S,T)=\sum _{u\in S,v\in T}c(u,v),$
 amely az $S$-ből $T$-be vezető élek kapacitásainak összege.

Minimális vágás

- Az összes lehetséges vágás közül a legkisebb $c(S,T)$-vel rendelkező vágás.

A Tétel Bizonyítása

1. Maximális folyam felső korlátja

- Minden folyam $f$ értéke ($|f|$) korlátozott a vágás kapacitása által:

 $|f|\le c(S,T),\mathrm{\forall }S,T.$

2. Ford-Fulkerson algoritmus és reziduális hálózat

- A maximális folyamot **Ford-Fulkerson algoritmus** vagy más iteratív módszer számítja ki. - A reziduális hálózat az aktuális folyam alapján meghatározza azokat az éleket, amelyeken további folyamot lehet növelni. - Amikor a reziduális hálózatban nincs több növelő út, a folyam eléri a maximumát.

3. Vágás és folyam összefüggése

- A végső reziduális hálózatban nincs növelő út. - Az $S$-hez tartozó csúcsok azok, amelyeket a forrásból el lehet érni, míg $T$-hez azok tartoznak, amelyeket nem. - A $c(S,T)$ minimális, mert a folyam minden növelő lehetőségét kihasználtuk.

4. Egyenlőség

- Az $|f|=c(S,T)$ egyenlőség teljesül, mert a maximális folyam teljesen kitölti a minimális vágás kapacitását.

Példa

Hálózat

Legyen a hálózat: $V=\{s,A,B,t\},E=\{(s,A),(s,B),(A,t),(B,t),(A,B)\}.$

Kapacitások: $c(s,A)=10,c(s,B)=5,c(A,t)=10,c(B,t)=5,c(A,B)=15.$

Maximális folyam

A Ford-Fulkerson algoritmussal: $f(s,A)=10,f(s,B)=5,f(A,t)=10,f(B,t)=5.$

A maximális folyam értéke: $|f|=15.$

Minimális vágás

A $S=\{s,A\},T=\{B,t\}$ vágás kapacitása: $c(S,T)=c(s,B)+c(A,t)=5+10=15.$

Eredmény: $\text{Maximális folyam: }15,\text{Minimális vágás kapacitása: }15.$

Python Implementáció

import networkx as nx

# Gráf definiálása
G = nx.DiGraph()
G.add_edge('s', 'A', capacity=10)
G.add_edge('s', 'B', capacity=5)
G.add_edge('A', 't', capacity=10)
G.add_edge('B', 't', capacity=5)
G.add_edge('A', 'B', capacity=15)

# Maximális folyam számítása
flow_value, flow_dict = nx.maximum_flow(G, 's', 't')
print("Maximális folyam értéke:", flow_value)
print("Folyam eloszlás:", flow_dict)

# Minimális vágás számítása
cut_value, partition = nx.minimum_cut(G, 's', 't')
print("Minimális vágás kapacitása:", cut_value)
print("Vágás particionálása:", partition)

Kimenet

Maximális folyam értéke: 15
Folyam eloszlás: {'s': {'A': 10, 'B': 5}, 'A': {'t': 10, 'B': 0}, 'B': {'t': 5}, 't': {}}
Minimális vágás kapacitása: 15
Vágás particionálása: ({'s', 'A'}, {'B', 't'})

Alkalmazások

1. Hálózattervezés: Kapacitás-optimalizálás adatátviteli hálózatokban.
2. Közlekedési rendszerek: Úthálózatokon áthaladó járművek optimális útvonalának meghatározása.
3. Ellátási láncok: Maximális szállítási kapacitás meghatározása.
4. Bioinformatika: Fehérjehálózatok és genetikai kapcsolatok optimalizálása.

Összegzés

A **Maximális folyam – Minimális vágás tétele** az egyik legfontosabb eredmény a hálózatáramlás elméletében. A tétel gyakorlati jelentőséggel bír számos területen, beleértve a logisztikát, a közlekedési hálózatokat és a kommunikációs rendszereket. Az algoritmusok, például a Ford-Fulkerson, hatékonyan alkalmazhatók a maximális folyam és minimális vágás kiszámítására. A Python egyszerű eszközöket biztosít ezek megvalósítására és ellenőrzésére.

• Sablon:En: Sablon:T