Számítástudomány alapjai 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.
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...
Számítástudomány alapjai epizód.