Áramlik a hálózatok
tól wikiznanie
12. Hálózati hálózati forgalmat. Tétel Ford - Fulkerson
Áramlását a hálózat között, a vertex t (forrás) és s (drain) egy sor számok Sij, (azaz a számot a feltételes „terhelés”, végezzük a vertex I. vertex a számát a j ..), kielégítve a négy feltétel:
1) Sij a J 0, és ha Sij> 0, sji = 0 (nincs szembejövő forgalom);
2) száma CIJ J qij (megfelelő bordák keresztező képességek);
3) ha a csomópont a i index - közbenső (nem esik egybe a forrás és a lefolyó), a
.. Ez a száma, „áru” exportált felülről i, az a szám, az „áruk” importált ez a csúcs;
4) az összeg a „terhelés”, exportált a forrás t, meg kell egyeznie a száma rakomány importált a lefolyóba s:
A szám A jelentése a nagyságát a fluxus, vagy egyszerűen fluxus közötti t és s.
A következőkben szükségünk van a következő definíciót:
Tegyük fel, hogy egy rész közötti csomópontok s és t. Ezután a keresztmetszet az összege az átkelés bordák képességek ebbe a szakaszba. A keresztmetszet az úgynevezett minimum (maximum), ha annak értéke a minimális (maximális).
Tétel Ford - Fulkerson (1955). Maximális áramlás csomópontok közötti s és t megegyezik a minimális keresztmetszet ezek között csúcsokat.
Ennek bizonyítéka tétel konstruktív (m. E. Megmutatja, hogyan kell megtalálni a kívánt maximális áramlás), azonban az alábbiakban közöljük.
Pontosabban, több Y jelölt csúcsok a következőképpen képződik:
Y t tartozik forrás és annak flag (0, ∞); A második szám, viszonylag szerény, végtelen - ami azt jelenti, hogy ez olyan nagy szám, mint mi szükség van a diszkrét matematika;
ha a csomópont tartozik, Y i és CIJ
ha a csomópont k tartozik Y és SJK> 0 (fordított ív), majd a csúcs a száma j kell tartozniuk Y és jelöléssel (- a, dj), ahol a jel pedig azt, hogy a csúcs j társított a már jelzett csúcsot, hogy az inverz ív , dj = min, és nyilvánvaló, hogy a dj is szigorúan nagyobb, mint nulla. Így, az építőiparban a beállított Y jelentése induktív, t. E. új csomópontot adunk az Y, ha ez jár a néhány csúcs már szereplő Y vagy telítetlen, egyenes ív vagy visszajelzést ív.
Az építési Y befejeződött (lehetetlen, hogy új csúcsok), van 2 esetben.
1. Készlet (t. E. A hegyét az s szám) nem szerepel a csúcsok halmaza Y. Ezután a csúcsok halmaza kívül Y Z. A grafikon az állapot van kötve, ezért, Y, néhány élek a Z. A szabályok szerint a építési Y mindezen élek egyenes és telített ívek (ábra. 7).
A bordák nyúlnak ki több Y be Z, alkotnak közötti szakasz csomópontok s és t. Az is látható, hogy az összeg az egyes kapacitások az élek ezen keresztmetszet (és az összes ezek a szélek egyenesek, telített) az áramlás t s. Ennélfogva, az áramlás maximális (mivel egyenlő a keresztmetszetét a), és ez a szakasz minimális.
S 2. A felső is benne van az Y, és hagyja, hogy a második szám annak tagging d s> 0. Ekkor, nyilvánvaló, hogy között a tetejét s és t egy láncot (álló irányított élek - direkt és inverz ívek) ezeket összekötő csúcsok
Vázlatosan ez ábrán látható. 8. t ® ® · · · ¬ ¬ · ® ® · · · ¬ ¬ · ® · ®s
Megjegyezzük, hogy az ív, hogy megy a forrást és egy ív, részben a lefolyó kell feltétlenül egyenes. Hozzáadás ds a CIJ kiegyenesítése íveket a lánc (a konstrukció látható, hogy a kapott szám kisebb, mint vagy egyenlő qij) és vonjuk ezt a DS a CIJ reverz ívek (is kap egy negatív szám, de ez szükségszerűen abszolút értéke kisebb qij, hiszen építeni egy dS £ CIJ + qij., ami azt jelenti, hogy az inverz ív megváltoztatja az irányát, akkor lesz egy egyenes ív és a „terhelés” egyenlő lesz a modulus, akkor az új számok íveket a lánc, valamint a „régi” CIJ minden ívek nem szerepel a áramkörben, így egy új áramlási a vertex a vertex t s (Le Óvatosan ellenőrizze egyszerű érv, hogy az új számokat az alábbi feltételek (1) -. (4)) Ezen túlmenően, az értéke az új áramlási összehasonlítva a régi rózsa DS> 0. Egy új szál ismét elvégzi ugyanezt az eljárást, és így tovább ..
Mivel minden egyes alkalommal az áramlási sebesség megnő legalább 1 (sávszélesség bordák egész számok), és a maximális áramlási sebesség korlátozott (minimális keresztmetszet-érték), ez az eljárás nem tudja folytatni a végtelenségig, és így, néhány lépésben kapjunk egy patak, amelynek csúcsa s nem tartalmazza Y, m. e. az áramlás maximális és egyenlő értékét a minimális keresztmetszet. Ez azt bizonyítja, a tétel.
Érvelés Ford tétel - Fulkerson algoritmus valóban megtalálja a maximális áramlási két csomópont között (vagy bizonyítja, hogy ez az áramlás a maximum). Részletes példa e tárgyban van megadva Sec. 15 „A döntés tipikus probléma.”
Megjegyzés. Ha ez a grafikon a sávszélességek bordák (t. E. A hálózat) több forrásból, és a csatornába, a fenti algoritmusnak lehet alkalmazni az alábbiak szerint. Vezessenek be egy új forrás és egy új mosogató, és az új forrás él köt össze minden forrással, és egy új mosogató - minden mosdó és kapacitásait új éleket úgy vélik, tetszőlegesen nagy számban, hogy az ív az esetleges áramlás lenne telítetlen (visszahívás bordákkal a forrás és a bordák futó lefolyás mindig egyenes ívű). Ezt követően az új grafikus megoldjuk a problémát, a maximális áramlás (egy új forrás egy új mosogató). Döntés lépett törli az összes éleket és csúcsokat.
Nézzünk néhány a kérdések (elég általános) Gráfelméleti. Vegye figyelembe, hogy a következő részekben, itt csak a legalapvetőbb bizonyítékok és kulcsfontosságú bizonyítékokat idézett könyvében R. Wilson [6].