Barion Pixel Hálózati folyamok, Ford-Fulkerson algoritmus | mateking
 

Diszkrét matematika epizód tartalma:

Itt röviden és szuper-érthetően megnézheted, mik azok a hálózati folyamok, hogyan lehet megtalálni a maximális folyamot, hogyan működik a Ford-Fulkerson algoritmus, mi az a javító gráf és hogyan kell használni.

A képsor tartalma

Itt ez a vízvezeték hálózat, amin keresztül víz áramlik S-ből T-be.

A zárójelben lévő számok a csövek kapacitását jelentik.

Vagyis azt jelentik, hogy mennyi víz képes rajtuk átfolyni.

A zárójel előtti szám pedig azt mondja meg, hogy éppen mennyi víz folyik most a csőben.

Hát, vannak itt még kihasználatlan részek.

A kérdés az, hogyan tudnánk még egy kicsit növelni az átfolyó víz mennyiségét.

Kell hozzá egy kis trükk.

Ezt a csövet itt elzárjuk.

Most rosszabb…

Viszont szabaddá tettük a jobb oldali ágat.

Ahol le tudunk engedni 10 egység vizet.

És így az eddigi 10 helyett most már 15 egység víz folyik S-ből T-be.

Remek hír, de két kínzó kérdés merül föl.

Az egyik: Hogyan lehet rájönni ezekre a javítási lehetőségekre az ennél bonyolultabb esetekben?

A másik: Honnan lehetünk biztosak benne, hogy a legjobb megoldást találtuk meg?

Hát, ezekre a kérdésekre fogunk most válaszolni.

Itt van egy másik hálózat…

ez már egy kicsit bonyolultabb.

És a csőrendszert egy irányított gráffal fogjuk jelölni.

Úgy tűnik, hogy 5+2=7 egység víz indul útnak S-ből…

és 0+3+4=7 egység is érkezik meg.

Próbáljunk meg ezen javítani.

A javításhoz egy úgynevezett javító gráfot fogunk használni.

Nézzük, hogyan készül a javító gráf.

Itt van ez az él…

szabad kapacitással.

Ezt az élt így tesszük be a javító gráfba.

A zöld nyíl azt jelenti, hogy ennyivel tudjuk még a csőben növelni a vizet.

A piros nyíl pedig azt mutatja, hogy jelenleg mennyi folyik át, de szaggatott vonallal, és visszafelé mutat.

A zöld nyíl túl sok magyarázatot nem igényel.

De mire jó a piros nyíl szaggatott vonallal és visszafelé?

A piros nyíl egy zseniális terv része. És hamarosan az is kiderül, hogy mi ez a terv.

Most menjünk szépen tovább.

Ennek az élnek a szabad kapacitása .

Berakjuk ezt is a javító gráfba szépen.

A zöld nyíl azt jelenti, hogy 6-tal tudjuk még a csőben növelni a vizet.

A piros nyíl pedig azt mutatja, hogy jelenleg 2 egység folyik át ezen a csövön,

de már megint ez a rejtélyes szaggatott vonal, és megint visszafelé.

Itt van aztán az A-ból B-be vezető cső.

Ez fullon van, úgyhogy a javító gráfban ide nem rakunk zöld nyilat.

De a rejtélyes piros nyíl itt is kell.

Mivel jelenleg 2 egység víz folyik át a csövön, ezért így:

Most lássuk, mi a helyzet az A-ból C-be vezető csővel.

Ez a cső teljesen üres.

A zöld nyíl tehát megegyezik a cső teljes kapacitásával…

Piros nyíl pedig itt nincs.

Ugyanez a helyzet az A-ból D-be vezető csőnél is.

És szépen lépésről lépésre elkészítjük a javító gráfot.

Elkészült a javító gráf.

A javító gráf megmutatja nekünk, hogy milyen útvonalon tudjuk növelni a meglévő folyamot.

Ezen az útvonalon például tudjuk.

Mégpedig 3 egységgel.

De van még itt más javító út is…

Ezen az útvonalon a szűk keresztmetszet a 3…

Így aztán ennyivel tudunk javítani.

Hát, eddig megvolnánk.

A kérdés, hogy tudunk-e még ezen is javítani.

Készítsük el az ehhez tartozó új javító gráfot, és nézzük meg.

És most nézzük, van-e még itt javító út.

Olyan már nincs, ami csupa zöld éleken keresztül vezet S-ből T-be.

De itt az ideje felfedni a titkos terv részleteit.

Létezik ugyanis még egy javító út…

ami piros élen is halad.

A szűk keresztmetszet ezúttal 2, vagyis 2 egység vizet tudunk még ezen az útvonalon szállítani.

A piros élen történő szállítás pedig azt jelenti…

hogy ezt a csövet elzárjuk.

A bal oldali ágról másfelé tereljük a vizet…

és így a jobb oldali ágon tudjuk növelni 2-vel.

De az egészben az a legjobb, hogy nekünk ezen nem kell gondolkodnunk.

Minden ki fog jönni szépen magától.

Nem kell mást tennünk, csak egyszerűen alkalmazni a hálózatra a javítást.

Ahol zöld élen mentünk a javító úton, ott hozzáadunk…

ahol piros élen, ott levonunk.

Most újra elkészítjük a javító gráfot a szokásos módon.

És úgy tűnik, hogy ez már tovább nem javítható.

Azért nem, mert nincsen a javító gráfban S-ből T-be vezető út.

Szerencsére létezik egy tétel, ami végérvényesen el tudja dönteni, hogy létezik-e még további javító út vagy sem.

Ezt a tételt Ford-Fulkerson tételnek nevezzük, és ezzel fogjuk folytatni...

 

Hálózati folyamok, Ford-Fulkerson algoritmus

01
hang
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez