Hálózati folyamok Definíció: Legyen G = (V,E) egy irányított gráf, adott egy c: E→R+∪{0} ún. kapacitásfüggvény, amely minden (u,v) 𝜖 E élhez hozzárendel egy nem negatív c(u,v) kapacitást. A gráfnak van két kitüntetett pontja a termelő (forrás) s, és a fogyasztó (nyelő) t. Ekkor a (G,c,s,t) négyest hálózatnak nevezzük. Definíció: Legyen adott egy (G,c,s,t) hálózatunk. Ekkor az f: E→R+∪{0} függvényt hálózati folyamnak nevezzük, ha a következő tulajdonságokkal rendelkezik: -
kapacitás megszorítás f(u,v) ≤ c(u,v)
∀ (u,v) 𝜖 E -re
-
megmaradási szabály 𝑣𝜖𝑉 𝑓(𝑢, 𝑣)=0 ferde szimmetria f(u,v) = -f(v,u)
∀ v 𝜖 V\{s,t}-re ∀ u,v 𝜖 V -re
A folyam értéke a forrásból kilépő éleken f értéke. Definíció: Vágásnak nevezzük az X ⊂ V pontok halmazát, ahol s 𝜖 V, de t 𝜖/ V. A vágás értékét az X - ből kilépő élek kapacitásainak összege. Tétel: A maximális folyam értéke megegyezik a minimális vágás értékével. Javító út: ha egy út minden e előre élén f(e) < c(e) és minden hátra élén f(e) > 0, akkor ezt az utat javítóútnak nevezzük. Ha létezik ilyen javítóút, akkor a folyam értékét itt növelhetjük: az előre éleken növeljük a folyam értékét, a hátra éleken pedig csökkentjük ugyanazzal a mennyiséggel, DE az előre éleken nem mehetünk a kapacitás értéke fölé és a hátra éleken nem mehetünk nulla alá. Ford - Fulkerson algoritmus: - kezdetben legyen minden élre a folyam értéke nulla - amíg létezik javítóút, addig azon növeljük a folyam értékét - ha már nem létezik új javítóút, akkor megkaptuk a maximális folyamot
Feladatok: Maximális folyam minimális vágás meghatározása. 1. (A: termelő, D: fogyasztó)
0/6
0/2
0/7
0/3 0/4
0/5 0/4 0/8
0/7 0/2
A folyam értéke kezdetben minden élre nulla, most minden lépésben keresünk egy javító utat és a javítóút mentén növeljük a folyam értékét. Válasszuk az A,B,C,D javító utat. Itt 2vel tudunk javítani.
2/6 2/3
2/2 0/7 0/5
0/8
0/4 0/4 0/7 0/2
Válasszuk az A,E,C,D utat javító útnak, itt a (C,D) él miatt 1-el tudunk javítani.
2/6 2/2
3/3 0/7 0/5
0/4 1/4
1/8
0/7 0/2
Válasszuk az A,E,F,D javító utat. Az (E,F) él miatt 2-vel tudunk javítani.
2/6 2/2
3/3 0/7 0/5
3/8
0/4 1/4 2/7 2/2
Az A,E,C,B,F,D út is javítóút. Itt viszont van egy hátra él; mivel a hátra élre f(hátra él) > 0 és az előre élekre is teljesül, hogy c(előre él) > f(előre él), ezért ez valóban jó javító út lesz. Az (B,C) él miatt 2-vel tudunk javítani.
0/6 2/2
3/3
2/7 0/5
0/4 3/4
5/8
4/7 2/2
Látható, hogy többet nem tudunk javítani: az (A,B) élre f(A,B) = c(A,B), tehát innen indulva nem tudunk javító utat keresni. Az (A,E) élen tudnánk javítani és az (E,C) élen is, viszont innen nem tudunk tovább haladni. A maximális folyam meghatározásához meg kell néznünk, hogy a termelőből (A) kilépő éleken mekkora a folyam étéke: MAX FOLYAM = 5 + 2 = 7 Minimális vágás: Látható, hogy A-ból B-be el tudunk jutni, hiszen az (A,E) él előre él és telítetlen, E-ből B-be nem tudunk eljutni, mivel ez egy olyan hátra él, ahol a folyamérték 0, az E-ből F-be sem tudunk eljutni, mivel ez olyan előre él, amely telített, az E-ből C-be el tudunk jutni, mivel ez olyan előre él, amely nem telített, a C-ből a D-be nem tudunk el jutni, mert telített, a C-ből az F-be és a B-be nem tudunk eljutni, mert ezek olyan hátra élek, amelyeken a folyam értéke nulla. A minimális vágás tehát {A, E, C}. A minimális vágás értéke pedig a kilépő éleken a kapacitások összege: MIN VÁGÁS = 7. Ez pedig meg kell, hogy egyezzen a maximális folyam értékével, ami szintén 7. 2. 0/8 0/9 0/10 0
0/10 00
0/1 0/8
0/9
0/7 0/3
Minden élre a folyamérték nulla. Válasszuk az S,A,B,T utat javító útnak. 8-al tudunk javítani. 8/8 8/9 0/10 0
8/10 00
0/1 0/8
0/9
0/7 0/3
Válasszuk az S,C,D,T utat. 3-mal tudunk javítani. 8/8 8/9
8/10 00 0/10 0
0/1
0/8
3/9
3/7 3/3
Legyen a következő javító út az S,C,B,T. A (C,B) él miatt 1-el tudunk javítani. 8/8 8/9 0/10 0
1/1
4/9
0/8 3/7
3/3 Nincs több javító út. MAX FOLYAM = 12, MIN VÁGÁS = {S, A, C}
9/10 00
3. (csak a kapacitás értékeket tüntettük fel)
7 8
1
4
3 2
2
12
1
6
5
2
MAX FOLYAM = 11 MIN VÁGÁS = {S, C} 4. (csak a kapacitás értékeket tüntettük fel) 4
3
2
2
3
MAX FOLYAM = 5 MIN VÁGÁS = {S, A, B, C, D}
1
1
1
1
2
5. A T és az F is egy fogyasztót jelöl 18
20
8
12 6
3
11
2
9 4
12
Mivel két fogyasztónk is van, ezért bevezetünk egy új pontot (G-t), amelyet az F és a T fogyasztókkal kapcsolunk össze. Az (F,G) és a (T,G) élek kapacitását végtelenre állítjuk be.
0/18
0/20
0/8
0/12 0/6
0/3
0/11
0/∞
0/2
0/9 0/4
0/12
0/∞
Innentől pedig a feladat olyan, mintha egyetlen nyelőnk lenne. Az (F,G) és a (T,G) élek kapacitását azért választottuk végtelennek, hogy az utólagosan bevezetett G csúcs az eredményt ne befolyásolja majd. MAX FOLYAM = 19 MIN VÁGÁS = {S, D}
6. Az A.B pontok források, az F,G pontok nyelők.
0/2
0/3 0/3
0/6
0/2
0/1
0/4 0/2
0/5
0/2
Az előző példához hasonlóan vezessünk be egy új csúcsot, amelyet a két nyelővel kötünk össze és állítsuk a kapacitásukat végtelenre. Az A,B forrásokhoz is vezessünk be egy új pontot, amelyet a két forrással kötünk össze és a kapacitásukat ezeknek is végtelenre állítjuk. MAX FOLYAM = 11 MIN VÁGÁS = {A, B, C, D, E} 7. 0/3 0/5 0/2 0/6
0/3
0/3 0/5
0/3
0/1
0/7 0/7
