Liikenneverkko

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24. joulukuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 16 muokkausta .

Graafiteoriassa siirtoverkko on suunnattu graafi , jossa jokaisella reunalla on ei-negatiivinen kapasiteetti ja virtaus . Erotetaan kaksi kärkeä: lähde ja nielu siten, että mikä tahansa verkon toinen kärki sijaitsee polulla kohteeseen , kun taas . Liikenneverkon avulla voidaan mallintaa esimerkiksi tieliikennettä. $G=(V,E)$ $(u,v)\in E$ $c(u,v)\geqslant 0$ $f(u,v)$ $s$ $t$ $s$ $t$ $s\neq t$

Kokonaislukusiirtoverkko on siirtoverkko, jossa kaikki reunakapasiteetit ovat kokonaislukuja.

Määritelmät

Virtausverkko on suunnattu graafi , jossa $G(V,E),$

jokaisella reunalla on ei-negatiivinen kapasiteetti, joka ilmaistaan funktiolla (joissakin lähteissä myös ), niin että mille tahansa funktion arvo on nolla. $\ (u,v)\in E$ ${\displaystyle c\colon V\times V\rightarrow \mathbb {R} _{+))$ ${\displaystyle c\colon E\rightarrow \mathbb {R} _{+))$ $e\not \in E$
valitaan kaksi kärkeä: lähde ( lähde ) ja nielu ( sink ) siten, että mikä tahansa verkon toinen kärki sijaitsee polulla osoitteesta kohteeseen , kun taas . $s$ $t$ $s$ $t$ $s\neq t$

Flow (virtaus) - funktio (joissakin lähteissä myös ), jolla on seuraavat ominaisuudet: ${\displaystyle f\colon V\times V\rightarrow \mathbb {R} _{+))$ ${\displaystyle f\colon E\rightarrow \mathbb {R} _{+))$

Kapasiteettirajoitukset . Minkään reunan virtausarvo ei voi ylittää sen kapasiteettia: $e\in E$ $0\leqslant f(e)\leqslant c(e).$
Vino symmetria. Virran osoitteestakohteeseenon oltava päinvastainen kuin virtauksen kohteestakohteeseen: $\u$ $\v$ $\v$ $\u$ $f(u,v)=-f(v,u).$
Virtauksen säilyttäminen: kaikille . $\sum _{v\in V}f((u,v))-\sum _{w\in V}f((w,u))={\begin{cases}|f|&, v=s\\-|f|&,v=t\\0&,v\neq s\land v\neq t\\\end{cases}}$ $\u\in V$

Virtauksen arvo on lähteestä lähtevien virtausten summa tai nielujen virtausten summa . $|f|=\sum _{v\in V}f(s,v)=\sum _{v\in V}f(v,t)$

Maksimivirtausongelmana on löytää sellainen virtaus , että virtauksen arvo on maksimi, ts. sellaista virtaa ei oleolemassa. $f$ $f^{*}$ $|f^{*}|>|f|$

Leikkaus (st cut) on pari disjoint asettaa siten, että ja ja . On myös määritelmä, jossa leikkaus on reunojen osajoukko , missä on pisteiden osajoukko siten, että ja . $(A, B)$ $V=A\ {\piste {\cup }}\ B$ $s\in A$ $t\ in B$ ${\displaystyle \delta ^{+}(X)=\{(u,v)\in E\mid u\in X,\ v\notin X\))$ $X$ $s\in X$ $t\notin X$

St -leikkauksen kapasiteetti on kaikkien leikkausreunojen kapasiteettien summa: tai . $\sum _{e\in \delta ^{+}(X)}c(e)$ ${\näyttötyyli \sum _{(u,v)\in E,u\in A,v\in B}c((u,v))}$

Leikkausvirtausarvo on kaikkien leikattujen reunojen virtausarvojen summa tai . Se ei ylitä leikkauksen läpijuoksua, koska kaikille . $\sum _{e\in \delta ^{+}(X)}f(e)$ $\sum _{(u,v)\in E,u\in A,v\in B}f((u,v))-\sum _{(u,v)\in E,u\ in A,v\in B}f((v,u))$ $f(e)\leqslant c(e)$ $e\in E$

Minimileikkaus – leikkaus, jonka läpimenoteho on pieni.

Reunan jäännöskapasiteetti (jäännöskapasiteetti) - . Se ei ole aina negatiivinen kaistanleveyden rajoitusehdon vuoksi. $c_{f}((u,v))=c((u,v))-f((u,v))+f((v,u))$

Jäännösverkko on kaavio , jossa on joukko reunoja, joilla on positiivinen jäännöskapasiteetti. Huippupisteen välinen polku voi olla olemassa jäännösverkossa , vaikka sitä ei olisi alkuperäisessä verkossa. Tämä tapahtuu, kun alkuperäisessä verkossa on paluupolku ja virtaus sitä pitkin on positiivinen. $G_{f}=(V,E_{f})$ ${\näyttötyyli E_{f))$ $u$ $v$ $(v,u)$

Lisäävä (jäännös, täydentävä) polku (augmenting path) on polku jäännösverkossa, jossa ja Alla on todistettu, että virtaus on maksimaalinen silloin ja vain, jos jäännösverkossa ei ole lisättävää polkua. $(u_{1},u_{2},\dots ,u_{k})$ $u_{1}=s,$ $u_{k}=t,$ $c_{f}(u_{i},u_{i+1})>0.$

Ominaisuudet

Virtaus minkä tahansa leikkauksen läpi on yhtä suuri kuin lähteestä lähtevien virtausten summa.
Todistus : olkoon leikkaus (A,B). Tarkastellaan kaikkien A:lle kuuluvien pisteiden virtausten summaa. Se on yhtä suuri kuin

\sum _{{u\in A}}\sum _{{v\in A}}f(u,v)+\sum _{{u\in A}}\sum _{{v\in B} }f(u,v)

Ensimmäinen minkä tahansa pisteparin (u, v) summista sisältää kaksi termiä f(u, v) ja f(v, u), jotka ovat absoluuttisesti yhtä suuret ja etumerkillisesti vastakkaiset. Siksi tämä summa on nolla. Toinen summa on virtaus leikkauksen (A,B) läpi. Siksi kaikkien A:hen kuuluvien kärkien kaikkien virtausten summa on yhtä suuri kuin leikkauksen läpi kulkeva virtaus. Toisaalta virtausten summa mistä tahansa kärjestä, paitsi s ja t, on yhtä suuri kuin nolla ja . Siksi kaikkien A:hen kuuluvien kärkien kaikkien virtojen summa on yhtä suuri kuin s:stä peräisin olevien virtojen summa. Siksi virtaus leikkauksen (A,B) läpi on yhtä suuri kuin s:stä saatujen virtausten summa, mikä oli todistettava. $t\ei A$

Lähteestä lähtevien virtausten summa on yhtä suuri kuin nielujen virtausten summa.
Todiste : Harkitse leikkausta . Tämän leikkauksen läpi kulkeva virtaus on yhtä suuri kuin viemäriin virtausten summa. Toisaalta juuri todistetun mukaan virtaus tämän (ja minkä tahansa muun) leikkauksen läpi on yhtä suuri kuin lähteestä lähtevien virtausten summa. Lause on todistettu. $(V\setminus \{t\},\{t\})$

Maksimivirtaus on positiivinen, jos ja vain, jos lähteestä nieluun on reitti positiivisen kapasiteetin reunoja pitkin.
Todistus : Olkoon sellainen polku P olemassa. Olkoon c P:hen kuuluvien reunojen minimikapasiteetti. Olkoon virtaus yhtä suuri kuin c kaikilla P:n reunoilla ja nolla kaikilla muilla reunoilla. Silloin kokonaisvirtaus lähteestä on yhtä suuri kuin c, eli se on positiivinen. Oletetaan nyt, että sellaista polkua ei ole, eli t ei ole saavutettavissa pisteestä s positiivisen kapasiteetin reunoja pitkin. Olkoon A joukko pisteitä, jotka ovat saavutettavissa s:stä tällaisia reunoja pitkin, B on joukko niitä, joita ei saavuteta. Sitten, koska , , niin (A,B) on leikkaus. Ei myöskään ole reunaa (a, b), jolla on positiivinen kapasiteetti siten, että , , muuten b olisi saavutettavissa pisteestä s. Siksi osan (A,B) läpijuoksu on yhtä suuri kuin nolla, ja siten virtaus sen läpi on aina nolla. Siksi lähteestä lähtevien virtojen summa on aina nolla. $s\in A$ $t\ in B$ $a\in A$ $b\in B$

Virtaus on maksimaalinen silloin ja vain, jos jäännösverkossa ei ole lisäyspolkua. Todistus : Olkoon jäännösverkossa lisäyspolku ja olkoon jäännösverkossa kuuluvien reunojen jäännöskapasiteetin minimi . Lisää kaikkien parien kohdalla ja vähennä . Lisäsimme lähteestä tulevaa kokonaisvirtausta , joten se ei ollut maksimi. Nyt päinvastoin oletetaan, ettei sellaista polkua ole. Osoittakaamme ristiriitaisesti, että virtaus alkuperäisessä verkossa tarjoaa suurimman kokonaisvirtauksen kohteesta . Jos näin ei ole, on olemassa virtaus , joka tarjoaa suuremman kokonaisvirtauksen kohteesta . On helppo nähdä, että se on virtaus jäännösverkossa, joka tarjoaa positiivisen kokonaisvirtauksen kohteesta . Siksi jäännösverkossa on polku lähteestä nieluon, eli lisäyspolku. Meillä on ristiriita. $P$ $c$ $P$ $(u,v)\in P$ $f(u,v)$ $c$ $f(v,u)$ $c$ $c$ $f$ $s$ $f'$ $s$ $f'-f$ $s$

Ford-Fulkersonin lause . Maksimivirtauksen arvo on yhtä suuri kuin minimiosan kapasiteetti.
Todiste : virtausten summa kohteestaon yhtä suuri kuin virtaus minkä tahansa leikkauksen läpi, mukaan lukien pienin, joten se ei ylitä minimileikkauksen läpimenoa. Siksi maksimivirtaus ei ole suurempi kuin minimileikkauksen läpimeno. On vielä todistettava, että hän ei ole vähemmän kuin hän. Anna virtauksen olla maksimi. Sitten jäännösverkossa nielu ei ole tavoitettavissa lähteestä. Antaa olla joukko pisteitä, jotka ovat tavoitettavissa lähteestä jäännösverkossa ja jotka eivät ole tavoitettavissa. Sitten, koska,,on leikkaus. Lisäksi jäännösverkossa ei ole reunaapositiivisella kapasiteetilla, jolla,, muuten se olisitavoitettavissa kohteesta. Siksi alkuperäisessä verkossa virtaus mitä tahansa tällaista reunaa pitkin on yhtä suuri kuin sen kapasiteetti, ja näin ollen virtaus leikkauksen läpion yhtä suuri kuin sen kapasiteetti. Mutta virtaus minkä tahansa leikkauksen läpi on yhtä suuri kuin lähteestä tuleva kokonaisvirtaus, joka tässä tapauksessa on yhtä suuri kuin suurin virtaus. Tämä tarkoittaa, että suurin virtaus on yhtä suuri kuin leikkauksen läpimeno, joka ei ole pienempi kuin minimileikkauksen läpimeno. Lause on todistettu. $s$ $A$ $B$ $s\in A$ $t\ in B$ ${\näyttötyyli (A,B)}$ $(a, b)$ $a\in A$ $b\in B$ $b$ $s$ $(A, B)$ ${\näyttötyyli (A,B)}$

Esimerkki

Tässä näkyy siirtoverkko, jossa on lähde , nielu ja neljä lisäsolmua. Virtaus ja suorituskyky on merkitty vastaavasti . Kaistanleveys lähteestä nieluun on 5, mikä on helppo nähdä, koska kaistanleveys lähteestä on 5, joka on myös . $\s$ $\t$ $\f/c$ $\s$ $\t$

Yllä olevan virtauksen jäännösverkko on esitetty alla. Huomaa, että joissakin reunoissa on rajoitettu kapasiteetti, kun taas alkuperäisessä verkossa se on nolla. Esimerkiksi kylkiluu . Tämä virtaus ei ole maksimi. On olemassa kasvavia polkuja ja . Ensimmäisen raidan jäännöskapasiteetti . Lisäyspolkua ei ole lähdeverkossa, mutta sen läpi on mahdollista ohjata oikea virtaus. $\(DC)$ $\(s,a,c,t)$ $\(s,a,b,d,t)$ $\(s,a,b,d,c,t)$ $\min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))=\min(5 -3,3-2,2-1)=\min(2,1,1)=1$ $\(s,a,b,d,c,t)$

Sovellus

Yleisin esimerkki kuljetusverkkojen käytöstä on löytää maksimivirtaus , mikä tarkoittaa maksimaalista kokonaisvirtausta kohteesta - Verkon suurimman virtauksen löytämiseksi voidaan käyttää Ford-Fulkerson-algoritmia , Edmonds-Karp- algoritmia ja muita. $s$ $t.$

Vähimmäiskustannuksissa virtausongelmassa kullekin reunalle on määritetty kustannukset , kustannukset, jotka aiheutuvat virtauksen lähettämisestä reunan läpi . Tehtävänä on lähettää tietty määrä virtausta kohteesta kohteeseen alhaisin kustannuksin. $(u,v)$ $k(u,v)$ $f(u,v)$ $f(u,v)\cdot k(u,v)$ $s$ $t$

Katso myös

Kirjallisuus

Thomas H. Kormen ym. Algoritmit: rakentaminen ja analyysi = ALGORITMEIN JOHDANTO. - 2. painos - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Linkit (englanniksi)

Suurin virtausongelma
Suurin virtaus
Todelliset graafin esiintymät
Ohjelmistot, paperit, testikaaviot jne.
Ratkaisuja verkon virtausongelmiin (linkki ei käytettävissä)
Ohjelmistot ja paperit verkkovirtaongelmiin
Lemon C++ -kirjasto, jossa on useita maksimivirtaus- ja minimikustannuskiertoalgoritmeja