Síť toku
V teorii grafů je síť toku (nazývaná také dopravní síť ) směrovaný graf, kde každá hrana má kapacitu a může přijímat tok (nebo tok). Akumulace vln na okraji nemůže překročit jeho kapacitu. Směrovaný graf se v operačním výzkumu často nazývá síť . Vrcholy se pak nazývají uzly a hrany oblouky . Aby byl tok platný, musí se součet toků dosahujících uzlu rovnat součtu toků opouštějících tento uzel, pokud se nejedná o zdroj (který nemá žádný příchozí tok) nebo studnu (která nemá žádný odchozí tok) ). Síť lze použít k modelování provozu v silniční síti, oběhu tekutin v potrubí, distribuce elektřiny v elektrické síti nebo jakýchkoli dalších dat procházejících sítí uzlů.
Definice
Nechť je konečný orientovaný graf , ve kterém každý okraj je spojen s kladnou reálnou hodnotou . Ano , předpokládáme to . Existují 2 konkrétní vrcholy: zdroj a studna . Tok v síti je funkce se skutečnou hodnotou, která pro všechny vrcholy a splňuje 3 následující vlastnosti:
G=(PROTI,E){\ displaystyle G = (V, E)} vs.(u,proti){\ displaystyle \ c (u, v)} (u,proti)∉E{\ displaystyle \ (u, v) \ ne \ v E} vs.(u,proti)=0{\ displaystyle \ c (u, v) = 0} s{\ displaystyle \ s} t{\ displaystyle \ t} F:PROTI×PROTI→R{\ displaystyle \ f: V \ krát V \ rightarrow \ mathbb {R}} u{\ displaystyle \ u} proti{\ displaystyle \ v}
Omezení kapacity
F(u,proti)≤vs.(u,proti){\ Displaystyle \ f (u, v) \ leq c (u, v)}. Tok na okraji nesmí překročit jeho kapacitu.
Anti-symetrie
F(u,proti)=-F(proti,u){\ displaystyle \ f (u, v) = - f (v, u)}. Průtok shora dolů by měl být opakem průtoku šneku (viz příklad).
u{\ displaystyle \ u} proti{\ displaystyle \ v} proti{\ displaystyle \ v} u{\ displaystyle \ u}Zachování toku
∑w∈PROTIF(u,w)=0{\ displaystyle \ \ součet _ {w \ ve V} f (u, w) = 0}, pokud nebo . Podepsaná kumulace toků vstupujících a vystupujících z uzlu je nulová, s výjimkou zdroje, který jej produkuje , nebo jímky, která jej spotřebovává .
u=s{\ displaystyle \ u = s} u=t{\ displaystyle \ u = t}Jinými slovy, zachování toku vede k:
∑u∈PROTIF(u,proti)=∑z∈PROTIF(proti,z){\ displaystyle \ \ součet _ {u \ v V} f (u, v) = \ součet _ {z \ ve V} f (v, z)},
na jakýkoli summit proti∈PROTI∖{s,t}{\ displaystyle \ {v \ ve V \ setminus \ {s, t \}}}
Všimněte si, že jde o podepsaný tok z do . Pokud graf představuje fyzickou síť a pokud se jedná o skutečný tok například 4 červových jednotek a skutečný tok 3 červových jednotek , máme a .
F(u,proti){\ displaystyle \ f (u, v)} u{\ displaystyle \ u} proti{\ displaystyle \ v} u{\ displaystyle \ u} proti{\ displaystyle \ v} proti{\ displaystyle \ v} u{\ displaystyle \ u} F(u,proti)=1{\ displaystyle \ f (u, v) = 1} F(proti,u)=-1{\ displaystyle \ f (v, u) = - 1}
Říkáme, že tok (v obecném smyslu) fyzické sítě je tok vycházející ze zdroje s, to znamená
∑(s,proti)∈EF(s,proti){\ displaystyle \ \ součet _ {(s, v) \ v E} f (s, v)}.
Zbytková kapacita z hrany . Můžeme tedy definovat zaznamenanou zbytkovou síť , která udává množství dostupné kapacity . Všimněte si, že ve zbytkové síti může být cesta červa , i když tato cesta v původní síti neexistuje. Jelikož se 2 toky z opačných směrů navzájem ruší, snížení průtoku červů je ekvivalentní zvýšení průtoku červů . Rostoucí cesta je cesta ve zbytkové síti, kde , , a . Síť je plná toku tehdy a jen tehdy, pokud je ve zbytkové síti žádná cesta .
vs.F(u,proti)=vs.(u,proti)-F(u,proti){\ displaystyle \ c_ {f} (u, v) = c (u, v) -f (u, v)} GF=(PROTI,EF){\ displaystyle \ G_ {f} = (V, E_ {f})} u{\ displaystyle \ u} proti{\ displaystyle \ v} proti{\ displaystyle \ v} u{\ displaystyle \ u} u{\ displaystyle \ u} proti{\ displaystyle \ v} (u1,u2,...,uk){\ displaystyle \ (u_ {1}, u_ {2}, \ tečky, u_ {k})} u1=s{\ displaystyle \ u_ {1} = s} uk=t{\ displaystyle \ u_ {k} = t} vs.F(ui,ui+1)>0{\ displaystyle \ c_ {f} (u_ {i}, u_ {i + 1})> 0} GF{\ displaystyle \ G_ {f}}
Přesněji řečeno, hrany z jsou konstruovány následujícím způsobem: pro každou hranu :
EF{\ displaystyle \ E_ {f}} GF{\ displaystyle \ G_ {f}} (X,y)∈E{\ displaystyle \ (x, y) \ v E}
- pokud , vytvořte hranu v kladném směru s kapacitou rovnou . F(X,y)<vs.(X,y),{\ displaystyle \ f (x, y) <c (x, y),} (X,y)∈EF{\ displaystyle \ (x, y) \ v E_ {f}} vs.F=vs.(X,y)-F(X,y){\ displaystyle \ c_ {f} = c (x, y) -f (x, y)}
- pokud , vytvořte hranu v záporném směru s kapacitou rovnou . F(X,y)>0,{\ displaystyle \ f (x, y)> 0,} (y,X)∈EF{\ displaystyle \ (y, x) \ v E_ {f}} vs.F=F(X,y){\ displaystyle \ c_ {f} = f (x, y)}
Tento typ konstrukce se používá zejména v algoritmu Ford-Fulkerson, který vypočítává maximální průtok v síti toku.
Někdy je nutné modelovat síť s více než jedním zdrojem. Poté je do grafu vložen zdroj . Skládá se z vrcholu připojeného ke každému zdroji s okraji nekonečné kapacity, aby se choval jako jediný a globální zdroj. Podobná konstrukce pro studny se nazývá superwell .
Příklad
Vpravo je znázorněna síť toku se známým zdrojem , jímkou a čtyřmi dalšími uzly. Je zaznamenán průtok a kapacita . Je možné poznamenat, že síť je anti-symetrická kvůli kapacitním omezením a zachování toku. Celkový součet průtoku od do je 5, což lze jednoduše ověřit vzhledem k tomu, že součet průtoku od je 5, což je také množství průtoku přicházejícího . Navíc víme, že pro ostatní uzly je součet příchozího toku roven odchozímu.
s{\ displaystyle s}t{\ displaystyle t}F/vs.{\ displaystyle f / c}s{\ displaystyle s}t{\ displaystyle t}s{\ displaystyle s}t{\ displaystyle t}
Následující diagram ukazuje zbytkovou síť. Všimněte si, že na určitých hranách, kde je původní kapacita nulová, můžeme najít kladnou kapacitu, například hranu . Tento průtok není maximálním průtokem . Ve skutečnosti, tam je ještě volná kapacita podél cest , a . Zbytková kapacita první cesty se rovná
. Všimněte si, že pokud existuje cesta s kladnou zbytkovou kapacitou, tok nemůže být maximální. Zbytková kapacita cesty je minimální zbytková kapacita okrajů, které tvoří cestu.
(d,vs.){\ displaystyle (d, c)}(s,na,vs.,t){\ displaystyle (s, a, c, t)}(s,na,b,d,t){\ displaystyle (s, a, b, d, t)}(s,na,b,d,vs.,t){\ displaystyle (s, a, b, d, c, t)}min(vs.(s,na)-F(s,na),vs.(na,vs.)-F(na,vs.),vs.(vs.,t)-F(vs.,t)){\ displaystyle \ 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{\ displaystyle = \ min (5-3,3-2,2-1) = \ min (2,1,1) = 1}
Podívejte se také
Reference
-
(in) Paul E. Black, „ Supersource “ , Slovník algoritmů a datových struktur , Národní institut pro standardy a technologie .
-
(in) Paul E. Black, „ Supersink “ , Slovník algoritmů a datových struktur , Národní institut pro standardy a technologie .
Bibliografie
- (en) George T. Heineman, Gary Pollice a Stanley Selkow, Algorithms in a Nutshell , O'Reilly Media ,2008, 343 s. ( ISBN 978-0-596-51624-6 ) , kapitola 8: „Algoritmy toku sítě“, s. 226–250
- (en) Ravindra K. Ahuja , Thomas L. Magnanti a James B. Orlin , Network Flows: Theory, Algorithms and Applications , Prentice Hall ,1993, 846 str. ( ISBN 0-13-617549-X )
- (en) Bollobás, Béla , Teorie grafů: Úvodní kurz , Heidelberg, Springer-Verlag ,1979( ISBN 3-540-90399-2 )
- (en) Chartrand, Gary & Oellermann, Ortrud R., Applied and Algorithmic Graph Theory , New York, McGraw-Hill,1993, 295 s. ( ISBN 0-07-557101-3 )
- (en) Shimon Even , Graph Algorithms , Rockville, Maryland, Computer Science Press,1979( ISBN 0-914894-21-8 )
- (en) Alan Gibbons, Algorithmic Graph Theory , Cambridge, Cambridge University Press ,1985, 259 s. ( ISBN 0-521-28881-9 , číst online )
- (en) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest a Clifford Stein , Introduction to Algorithms , Cambridge (Mass.), MIT Press a McGraw-Hill,2001, 2 nd ed. ( 1 st ed. 1990), 1180 str. ( ISBN 0-262-03293-7 ) , kapitola 26, s. 696–697
externí odkazy
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">