Jump to navigation

Belépés
  • Elfelejtettem a jelszavam
Regisztráció
 
  • Hogyan működik a mateking?
  • Mire jó a matek?
  • Matek érettségi
  • Képletgyűjtemény
  • Feladatgyűjtemény
  • Rólunk
  • Matek 5. osztály próbaüzem
  • Matek 6. osztály próbaüzem
  • Matek 7. osztály próbaüzem
  • Matek 8. osztály próbaüzem
  • Matek 9. osztály
  • Matek 10. osztály
  • Matek 11. osztály
  • Matek 12. osztály
  • Középiskolai matek (teljes)
  • Középszintű matek érettségi
  • Emelt szintű matek érettségi
  • Egyetemi matek alapozó
Összes egyetemi tantárgy
Legnépszerűbb tantárgyak:
  • Analízis 1
  • Analízis 2
  • Analízis 3
  • Valószínűségszámítás
  • Lineáris algebra
  • Diszkrét matematika
  • Statisztika

mateking

Login
 

Diszkrét matematika

Kategóriák
  • Kombinatorika
  • Halmazok, rendezett párok, leképezések
  • Matematikai logika, ítéletkalkulus
  • Gráfelméleti alapok
  • Gráfok izomorfiája és síkbarajzolhatósága
  • Gráfok bejárása és gráfalgoritmusok
  • Kromatikus szám, klikk, perfekt gráfok
  • Gráfparaméterek, párosítások
  • Hálózatok
  • Irányított gráfok, gráfalgoritmusok irányított gráfokban
  • Menger tételei, többszörös összefüggőség
  • Páros gráfok, párosítások
  • Teljes indukció
  • Oszthatóság
  • Euklideszi algoritmus & Diofantoszi egyenletek
  • Kongruenciák
  • Mátrixok
  • Lineáris egyenletrendszerek
  • Determinánsok
  • Komplex számok
  • Polinomok
  • Interpolációs polinomok
  • Csoportok, gyűrűk, testek

Hálózatok

  • Epizódok
  • Képletek
01
 
Hálózati folyamok, Ford-Fulkerson algoritmus
02
 
A maximális folyam és a minimális vágás, Ford-Fulkerson tétel
03
 
Egy kis összefoglaló hálózati folyamokból
04
 
CPM és PERT, kritikus út
05
 
FELADAT | Maximális folyam, minimális vágás
06
 
FELADAT | Maximális folyam, minimális vágás
07
 
FELADAT | Maximális folyam, minimális vágás
08
 
FELADAT | Maximális folyam, minimális vágás
09
 
FELADAT | Maximális folyam, minimális vágás
10
 
FELADAT | Maximális folyam, minimális vágás
12
 
FELADAT | CPM, kritikus út
13
 
FELADAT | CPM, kritikus út
14
 
FELADAT | CPM, kritikus út
15
 
FELADAT | CPM, kritikus út
16
 
FELADAT | CPM, kritikus út
17
 
FELADAT | CPM, kritikus út

Ford-Fulkerson algoritmus

A Ford-Fulkerson algoritmus egy olyan algoritmus, amit a maximális folyam megkeresésére használunk. Az algoritmus lényege pedig az a javító gráf, amit az eredeti hálózat alapján készítünk el. A javító gráf megmutatja nekünk, hogy milyen útvonalon tudjuk növelni a meglévő folyamot.

Megnézem a kapcsolódó epizódot

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.

Megnézem a kapcsolódó epizódot

Vágás kapacitása

Egy $(S,T)$ vágás kapacitása, a vágásban szereplő élek kapacitásainak összege.

Megnézem a kapcsolódó epizódot

Él kapacitása

Legyen $G$ egy irányított gráf és értelmezzünk a gráf élein egy $E \rightarrow R^{+}_0 $ függvényt, ami minden élhez hozzárendeli a $c(e)$ nem negatív számot, amit az él kapacitásának nevezünk.

Megnézem a kapcsolódó epizódot

Folyam

A hálózatban folyamnak nevezünk egy olyan $ f(e) \; E \rightarrow R^{+}_0$ függvényt, amire teljesül, hogy bármely $e$ élre $0 \leq f(e) \leq c(e)$ és bármely $T$-től és $S$-től különböző $V$ csúcsra:

\( \sum_{Vbe} f(e) - \sum_{Vki} f(e) = 0 \)

Megnézem a kapcsolódó epizódot

Folyam értéke

Egy folyam értékének az

\( m_f = \sum_{Ski} f(e) - \sum_{Sbe} f(e) \)

számot nevezzük.

Megnézem a kapcsolódó epizódot

Ford-Fulkerson tétel

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.

Megnézem a kapcsolódó epizódot

Hálozat

Legyen $G$ egy irányított gráf és értelmezzünk a gráf élein egy $E \rightarrow R^{+}_0 $ függvényt, ami minden élhez hozzárendeli a $c(e)$ 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.

Megnézem a kapcsolódó epizódot

Kritikus út

Mindig létezik egy olyan út, ami csak azokon a pontokon halad át, ahol a tartalékidő nulla, és az út hossza megegyezik a teljes folyamat hosszával. Ezt az utat kritikus útnak nevezzük.

Megnézem a kapcsolódó epizódot

A témakör 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. Hogyan lehet megtalálni a maximális folyamot és a minimális vágást. Megnézzük a Ford-Fulkerson tételt. 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. Végezetül pedig elmeséljük, hogy mi az a kritikus út, mi a CPM módszer és a PERT módszer. Példák kritikus út keresésére, legkorábbi és legkésőbbi bekövetkezések, tartalékidő.



Hálózati folyamok, Ford-Fulkerson algoritmus

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...


A maximális folyam és a minimális vágás, Ford-Fulkerson tétel

Van itt ez a hálózat az élek kapacitásaival…

és egy hálózatban futó folyammal.

Ebből a folyamból kiindulva keressük meg az S-ből T-be vezető maximális folyamot.

A módszert, amit a maximális folyam megkeresésére fogunk használni, Ford-Fulkerson algoritmusnak hívják.

Az algoritmus lényege pedig az a javító gráf, amit az eredeti hálózat alapján készítünk el.

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

A szűk keresztmetszet pedig 2, vagyis maximum 2-vel tudunk növelni.

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, hátha még mindig lehet a folyamon javítani.

De, nem úgy néz ki.

Itt nem jutunk át…

Ezeknél a csúcsoknál ugyanis a javító út elakad.

A piros csúcsokból most már lehetetlen átjutni…

a sárga csúcsokba.

A problémát egy kicsit precízebben a Ford-Fulkerson tétel fogalmazza meg.

Ehhez be kell vezetnünk egy új fogalmat, amit vágásnak fogunk hívni.

Már jön is.

A hálózat csúcsainak halmazát V(G)-vel jelöljük.

Legyen X a V(G)-nek egy olyan részhalmaza, ami S-t tartalmazza.

A többi csúcs pedig, amik nincsenek benne az X-ben a V(G)\X halmazt alkotják.

Az X és a V(G)\X halmazok közötti éleket vágásnak nevezzük.

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.

A vágás szemléletes jelentése ez…

elvág minden utat S és T között.

A vágás kapacitása pedig azt mondja meg, hogy hány sávot robbantottak föl a terroristák.

Most éppen egy 10 sávos utat és két 4 sávos utat robbantottak föl.

Tehát a vágás kapacitása 10+4+4=18.

Vágás kapacitása:

Egy (S,T) vágás kapacitása, a vágásban szereplő élek kapacitásainak összege.

Vagy éppen ennek a másik vágásnak itt…

ennek a kapacitása 11+4+4=19.

És ennek pedig…

Hát, ennek még több: 4+16=20.

Maximális folyam, minimális vágás, Ford-Fulkerson algoritmus

Vagyis keressük meg azt a vágást, amihez a lehető legkevesebb sávot kell felrobbantani, de mégis teljesen megszűnik az összeköttetés S és T között.

Ezt a vágást minimális vágásnak nevezzük.

Lássuk, mekkora a kapacitása például ennek a vágásnak itt.

Na, ez éppen egy trükkös eset.

Az egyik él ugyanis visszafelé megy.

Amikor egy vágás kapacitását számoljuk, csak az X-ből V(G)\X-be vezető élek számítanak…

ha van olyan él, ami V(G)\X-ből X-be vezet, az nem.

Így aztán ennek a vágásnak a kapacitása 10+9+5=24.

Ami biztosan nem minimális, mert volt már az előbb olyan vágás is, aminek a kapacitása 18.

Ez volt az.

Kérdés: van-e még ennél is kisebb?

És itt kerül képbe a Ford-Fulkerson tétel.

Ha találunk egy tetszőleges folyamot a hálózatban, akkor a folyam értéke egészen biztosan kisebb bármely vágás kapacitásánál.

És fordítva, egy tetszőleges vágás kapacitása biztosan nagyobb, mint bármely folyam értéke.

A Ford-Fulkerson tétel azt mondja, hogy a maximális folyam mindig megegyezik a minimális vágással.

Lássuk, hogyan használhatnánk ezt a tételt a mi kis hálózatunkra.

Az biztos, hogy találtunk egy olyan vágást, aminek a kapacitása 18.

És az is biztos, hogy van egy olyan folyam, aminek az értéke 18.

Hiszen 18 egység indul S-ből…

és annyi is érkezik T-be.

Mivel van 18 kapacitású vágás, nem lehet 18-nál nagyobb értékű folyam.

Vagyis a maximális folyam értéke 18.

És mivel van 18 értékű folyam, nem lehet 18-nál kisebb kapacitású vágás.

Tehát a minimális vágás kapacitása 18.


Egy kis összefoglaló hálózati folyamokbó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.


FELADAT | Maximális folyam, minimális vágás

FELADAT | Maximális folyam, minimális vágás

FELADAT | Maximális folyam, minimális vágás

FELADAT | Maximális folyam, minimális vágás

FELADAT | Maximális folyam, minimális vágás

FELADAT | Maximális folyam, minimális vágás

FELADAT | CPM, kritikus út

FELADAT | CPM, kritikus út

FELADAT | CPM, kritikus út

FELADAT | CPM, kritikus út

FELADAT | CPM, kritikus út

FELADAT | CPM, kritikus út

CPM és PERT, kritikus út

Kapcsolatfelvétel
  • Segítségnyújtás
  • Hibabejelentés
  • Kapcsolatfelvétel
  • Mateking torrent bejelentés
Rólunk
  • A projektről
  • Médiamegjelenések
  • Legyen élmény a matek
  • Mire jó a matek?
Tartalomjegyzék
  • Középiskolai matek
  • Analízis 1
  • Analízis 2
  • Analízis 3
  • Lineáris algebra
  • Valószínűségszámítás
  • Diszkrét matematika
  • Statisztika
  • További tantárgyak
  • Egyetemi tematikák
  • Matek érettségi
GYIK Általános szerződési feltételek Adatkezelési tájékoztató Felhasználás oktatási célra

Cookie-használat módosítása

© Minden jog fenntartva!

Az oldalon található tartalmak részének vagy egészének másolása, elektronikus úton történő tárolása vagy továbbítása, harmadik fél számára nyújtott oktatási célra való hasznosítása kizárólag az üzemeltető írásos engedélyével történhet. Ennek hiányában a felsorolt tevékenységek űzése büntetést von maga után!

barion
macroweb
  • Tantárgyaim