A kommunikációs hálózatok kapacitásának meghatározása
5.3.1. A maximális áramlás meghatározásának feladata a kommunikációs hálózatban
Engedje meg a kommunikációs hálózat kiszámítását. A tervezés során egy S információs forráskészletet és egy T információvevõkészletet adnak meg, ezek általában egymással metszenek vagy azonosak lehetnek S = T. azaz a forrás csomópont lehet egy cél csomópont is. Minden egyes csomópont az S halmaznak egy olyan adatfolyamot információt kell továbbítani a csomópontok a beállított T. Az ágak a grafikon lehet egy előre meghatározott sávszélesség az (u, v), és minden pár között csomópontok u és v. vagy szükség lehet az egyes ágak áteresztőképességének meghatározására. Az ág (perem) áteresztőképessége az adott ágon belüli maximális információátviteli sebességnek tekinthető.
Adott hálózati topológia, azaz megfelelő sor csomópontok és ágak, az ágak adott súlyozási mátrixot [u, v], ahol a súlyozó végez sávszélessége minden ág.
Milyen feladatok megoldhatók ezekkel a kezdeti adatokkal? Nyilvánvaló, hogy ki lehet választani egy sor kapcsolódó csomópontot. A csúcspontok között megtalálhatóak a legrövidebb utak. Végül megtalálhatjuk az s és t csúcsok közötti útvonalakat. Ebben az esetben minden útvonalnak különböznie kell a másiktól, legalább egy ágnak vagy csomópontnak. Mindazonáltal egyik ilyen feladat megoldása sem teszi lehetővé számunkra, hogy megválaszoljuk a kérdést - mi az egységnyi időegységre jutó maximális adat átvihető a csomópontokról a t csomópontra. vagy az S készlet csomópontjaitól a csomópontok csoportjáig. T. megoldja a fent említett problémákat nem segítenek, és megoldani az inverz probléma -, hogy mennyi és milyen sávszélesség szükséges ágak, hogy kihagyja az összes közötti információáramlás a beállított S csomópontok és több csomópontot T. ilyen probléma, ahogy a valódi hálózatokban, és nem működik (nem engedi dimenzió feladatok és a bemeneti adatok bizonytalansága).
A probléma megfogalmazása érdekében bizonyos fogalmakat formalizálunk. Minden egyes ághoz (u, v) hozzárendelünk egy bizonyos f (u, v) súlyt, amit u-v-nek nevezünk. Az ágban lévő áramlás (u, v) értéke akkor tekinthető a sebességnek, amikor az információ továbbításra kerül ebben az ágban.
Aztán egy mennyiséget, amit az "f" áramlás d-beli eltérésnek nevezünk
ahol Σf (v, u) a v csúcsot elhagyó áramlás. Σf (u, v) - a v csúcson belépő áramlás határozza meg az u csúcsot elhagyó áram mennyiségét.
Ez az érték lehet negatív (ha v nagyobb része, ami kijön), pozitív (ha ki v nagyobb részben) és a 0. Az utóbbi eset akkor érdekelnek minket leginkább. Ez azt jelenti, hogy az áram nem halmozódik fel, és nem következik be egyik csúcson sem, kivéve s és t.
Az s-től t-ig terjedő áramlásnál egy olyan funkciót értünk, amelyre a feltételek vonatkoznak
Milyen áramlást lehet átvinni s-ről t-re ezeken az ágakon keresztül? Nyilvánvaló, hogy az ágak orientáltak
vagyis egyenlő lesz a szekcióba lépő fióktelepek kapacitásának összegével.
Az R (A) hálózat szakaszában a megfelelő AV (A részhalmaz), A ≠ V. A ≠ 0. (u, v) olyan íveket, amelyek (u, v) W. uA és vV \ A.
A hálózat tetszőleges áramlásához f a nyíláson keresztül történő áramlást nyilvánvaló módon határozzák meg
Aztán, ha feltételezzük, hogy sA. és tV \ A. akkor az s-ből t-re történő átfolyást a következőképpen határozzuk meg:
Bevezetjük a minimális vágás fogalmát. A minimális levágás alatt s és t választja el. egy tetszőleges R (A), sA és tV \ A vágást értünk, minimális kapacitással.
Egy példa. Megfogalmazzuk a hálózatok áramlásának elméletének klasszikus tételét. Ez a maximális áramlási és minimális vágási tétel:
Az egyes streamek értéke az s-től t-ig. nem haladja meg a minimális vágás áteresztőképességét, és van olyan áramlás, amely eléri ezt az értéket.
Maximális hálózati áramlás
Minden ismert algoritmusok építésére maximális áramlás alapján egymást követő növeli az áramlási, az áramlás, amely növeli az értékét, leggyakrabban alapuló növelésének módszerével a lánc (vagy a mellék utak).
Bemutatunk néhány fogalmat, amelyekre szükségünk lesz az anyag további bemutatásában.
Azt mondjuk, hogy a G hálózat íve m egy megengedett ív az u-től v-ig az áramlásig. ha