Barion Pixel Egy kis összefoglaló hálózati folyamokból | mateking
 

Számítástudomány alapjai 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 lépésre vagy attól, hogy a matek melléd álljon és ne eléd.
  • Nem találsz külön tanárt? Ne is keress! Irány a mateking!!!!

    Bori, 19
  • Felsőbb éves egyetemisták ajánlották, "kötelező" címszóval.
    Ricsi, 19
  • Konkrétan a hetedikes öcsém megtanult deriválni, ez elég bizonyíték, hogy az oldal érthetően magyaráz.

    Gábor, 18
  • A mateking miatt sikerült az érettségi és az összes egyetemi matekos tárgyam.

    Míra, 21
BelépekvagyRegisztrálok Back arrow Ugrás az
összeshez