Diszkrét matematika 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.

A képsor tartalma

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.

 

Egy kis összefoglaló hálózati folyamokból

03
hang
Hopsz, úgy tűnik nem vagy belépve, pedig itt olyan érdekes dolgokat találsz, mint például:

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 jön egy fantasztikus
Diszkrét matematika epizód.
Végül is miért ne néznél meg
még egy epizódot?

Hozzászólások

Még nincs hozzászólás. Legyél Te az első!