Számítástudomány epizód tartalma:
Készítettünk egy kis összefoglalót a hálózati folyamokról, a minimális vágásról és maximális folyamról, a Ford-Fulkerson algoritmus működéséről és a javító gráfok használatáról.
Itt az ideje, hogy egy kicsit precízebbé tegyük a hálózatokkal kapcsolatos fogalmakat.
Legyen G egy irányított gráf és értelmezzünk a gráf élein egy függvényt, ami minden élhez hozzárendeli a nem negatív számot, amit az él kapacitásának nevezünk.
Van továbbá két kitüntetett pont a gráfban, S (source=forrás) és T (target=cél).
Ekkor a (G, S, T, c) egy hálózat.
A hálózatban folyamnak nevezünk egy olyan függvényt, amire teljesül, hogy bármely e élre és bármely T-től és S-től különböző V csúcsra
Vagyis egy csúcsba befolyó mennyiség…
mindig megegyezik a csúcsból kifolyóval.
A két kivétel S és T. S-ből csak kifelé folyik…
T-be csak befelé.
Egy folyam értékének az
számot nevezzük.
Most éppen…
Végül még egy fontos definíció: a vágás.
Legyen X a V(G)-nek egy olyan részhalmaza, ami S-t tartalmazza.
Ekkor az X-ből a V(G)\X-be vezető éleket (S,T) vágásnak nevezzük.
Egy (S,T) vágás kapacitása, a vágásban szereplő élek kapacitásainak összege.
A Ford-Fulkerson tétel azt mondja ki, hogy egy hálózatban a maximális folyam mindig megegyezik a minimális vágással.
És most pedig lássunk egy mindent összefoglaló példát.
Itt van ez a hálózat, benne egy folyammal.
Készítsük el a javító gráfot.
Most nézzük, lehet-e még javítani…
Úgy tűnik, igen.
Ezen az ágon a szűk keresztmetszet 1…
és a másik ágon hozzájön még plusz 3.
Nézzük, tudjuk-e ezt még javítani…
Megint elkészítjük a javító gráfot.
És úgy tűnik, már nem lehet tovább javítani.
Találtunk egy minimális vágást.
Ennek a vágásnak a kapacitása 14.
Ez azt jelenti, hogy minden folyam értéke maximum 14 lehet.
Ennek a folyamnak az értéke szintén 14.
Ez azt jelenti, hogy minden vágás kapacitása minimum 14 kell, hogy legyen.
A minimális folyam értéke és a maximális vágás kapacitása tehát 14.