A feladat meghatározása a maximális áramlási
Úgy véljük, egy hálózat, egy bemeneti csomópontot (forrás) és egy kimeneti csomópont (drain). Mi az a maximális sebesség (a gépek számát, az üzenetek, folyadék, stb), ami megköti a villamosenergia-rendszer és a belőle egy adott ideig? Ebben az esetben feltételezzük, hogy a szennyvíz a csomópont megegyezik a fluxus áramlik a csomópont.
Az sávszélesség (kapacitás) az ív alatt azt értjük, felső határa az áramlás az ív. Áramfolyás függhet annak irányát. sematikus hálózat
Ez azt jelenti, hogy a teljesítmény áramlás 1 csomópont a 2 csomópontra egyenlő 6, és a vastagsága 2 és 1 értéke 0.
Az algoritmus meghatározására a maximális áramlási:
- Megtalálja az utat a forrástól a lefolyó, amely által alkotott ívek, amelyek mindegyike egy nem nulla teljesítményt áramlási irány. Ha egy ilyen utat nincs jelen, akkor az optimális megoldást nem találnak.
- Keresse meg a legkisebb érték az ív P teljesítmény a kiválasztott útvonalon 1. lépésben növeli az áramlás a hálózaton keresztül az értéke R.
- Az úton a 1. lépésben, hogy csökkentsék az erőfolyamban P egyáltalán az íveket az áramlás irányában, és növeli a villamosenergia-áramlás P egyáltalán az íveket az ellenkező irányba. Ugorjon 1.
Példa. A rendszer az utak „Észak-Dél” áthaladó Pskov régió rendelkezhetnek sávszélességeket látható az alábbi reakcióvázlat (th. Cars per óra).
Mi az a maximális áramlás a rendszerben (ezer. Autók óránként)? Hány autó kell vezetni az úton 5-6 biztosítja a maximális áramlás?
A kívánt érték a maximális áramlás értékét nullára.
Útját válassza 1-3-6. P = min (6,2) = 2. Ezért, az energiaáramlásokra az utat 1-3-6 ben az áramlás irányában csökken a mennyisége a P = 2, és a teljesítmény áramlik a fordított irányban az útvonalon 1-3-6 növekedése F = 2. A teljes áramlási válik 0 + 2 = 2. kapjuk:
Útját válassza 1-4-6. P = min (3,3) = 3. Minden áramlások az útvonal 1-4-6 az általános áramlási irány csökken 3, és az ellenkező irányba gyel növekszik 3. A teljes áramlási növekszik 3. Összesen 2 + 3 = 5. kapjuk:
Útját válassza 1-2-5-6. R = min (2,4,6) = 2. Minden áramlások az útvonal 1-2-5-6 az általános áramlási irány csökken 2 növelésére az ellenkező 2. A teljes áramlási növekszik is a 2. Összesen 5 + 2 = 7. kapjuk:
Útját válassza 1-3-4-5-6. P = min (4,3,1,4) = 1. Minden áramlások az útvonal 1-3-4-5-6 az általános áramlási irány (4,3,1,4), hogy csökkentse az értéket P = 1, és az összes áramlás ilyen módon a fordított irányban növekszik a P = 1. Összesen teljes áramlási 7 + 1 = 8. kapjuk:
Útját válassza 1-3-4-2-5-6. P = min (3,2,1,2,3) = 1. Az előre irányuló csökken 1, a fordított értéke 1 -gyei növekszik A teljes áramlási 8 + 1 = 9. kapjuk:
Létezik többé utak csomópontból 1 6 csomópont kapacitást meghaladó 0 egészen (P = 0). Következésképpen 9000 -. A maximális folyam a hálózaton keresztül.
Most határozza meg a mértékét és az áramlás irányát minden ív eléri a maximális áramlás 9-én. Car. A légáram áthalad egy íven keresztül, amelynek értéke egyenlő a különbség a kezdeti és a végső áramlási kapacitását. Így a kezdeti ív teljesítmény 1-2 2, és a végén - 0. Ekkor egy olyan irányban a csomópontot 1 2 csomópontra adatfolyam kapacitása 2-0 = 2. Összehasonlítva a végső és kezdeti áramlási kapacitás az összes hálózati ívek, megkapjuk a végleges modell folyik.
Mi az a maximális áramlás járművek közúti rendszerek? Az a lehetőség, a bevezetése szakasz 3-4, amelynek kapacitása 3000. Cars óránként. Mennyit növeli az értékét a maximális áramlási járművek?
táblázat RR Állítsa. Logic. Axiomatikus elméletek. - M. Oktatási 1968.