Rețea în flux

În teoria graficelor , o rețea de flux este un grafic direcționat în care fiecare arc are o capacitate non-negativă și este traversat de un flux, adică un număr între 0 și capacitatea arcului.

Rețelele de curgere sunt o secțiune importantă a teoriei graficelor, deoarece pot fi utilizate pentru a modela multe situații reale: gândiți-vă, de exemplu, la o rețea rutieră și la fluxul aferent de vehicule sau la o rețea de apă. Mai general, orice sistem care include trecerea a ceva prin canale de capacitate limitată și interconectate între ele, poate fi reprezentat folosind o rețea de flux.

Definiție formală

Rețeaua este un grafic $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ căruia i se asociază o funcție $c:V^{2}\to \mathbb {R} _{\infty }$ ${\ displaystyle c: V ^ {2} \ to \ mathbb {R} _ {\ infty}}$ ${\ displaystyle c: V ^ {2} \ to \ mathbb {R} _ {\ infty}}$ , numită funcția de capacitate. Fără pierderea generalității, presupunem că dacă $(u,v)\in E$ ${\ displaystyle (u, v) \ în E}$ ${\ displaystyle (u, v) \ în E}$ , apoi și $(v,u)\in E$ ${\ displaystyle (v, u) \ în E}$ ${\ displaystyle (v, u) \ în E}$ , din moment ce $(v,u)\not \in E$ ${\ displaystyle (v, u) \ not \ în E}$ ${\ displaystyle (v, u) \ not \ în E}$ asa de $(v,u)$ ${\ displaystyle (v, u)}$ ${\ displaystyle (v, u)}$ poate fi adăugat la E și apoi aplicat $c(v,u)=0$ ${\ displaystyle c (v, u) = 0}$ ${\ displaystyle c (v, u) = 0}$ .

Având în vedere două noduri distincte s și t ale lui G , numite respectiv sursă și scufundare, atunci $(G,c,s,t)$ ${\ displaystyle (G, c, s, t)}$ ${\ displaystyle (G, c, s, t)}$ se numește rețea de flux. ^[1]

La fiecare nod $v\in V$ ${\ displaystyle v \ in V}$ $v \ în V$ se asociază un coeficient $b_{v}$ ${\ displaystyle b_ {v}}$ ${\ displaystyle b_ {v}}$ , care indică dacă $v$ ${\ displaystyle v}$ $v$ generează sau absoarbe debitul. ^[2] În primul caz, coeficientul va fi pozitiv și va fi numit întrebarea nodului; în al doilea caz coeficientul va fi negativ și va fi numit oferta nodului. De sine $b_{v}$ ${\ displaystyle b_ {v}}$ ${\ displaystyle b_ {v}}$ este nul, $v$ ${\ displaystyle v}$ $v$ se numește nod de transfer. ^[2] În cazul în care urmați să modelați o rețea de flux cu mai multe surse, este o practică obișnuită să creați o sursă , adică o nouă sursă cu arcuri de capacitate infinită care o conectează la toate celelalte surse. În acest fel, sursele anterioare devin noduri „comune” și ne găsim în cazul cu o singură sursă, fără a schimba sistemul, deoarece un flux din noua rețea corespunde unuia din original. O construcție similară este utilizată în cazul puțurilor multiple, cu introducerea unui superpuț .

Fluxuri

Există diferite tipuri de funcții de flux care pot fi definite într-o rețea de flux. Funcțiile fluxului asociază un număr cu fiecare pereche de noduri.

Exemplul de bază al unei funcții de flux este cunoscut sub numele de pseudofluor. O pseudoflux este o funcție $f:V^{2}\to \mathbb {R}$ ${\ displaystyle f: V ^ {2} \ to \ mathbb {R}}$ ${\ displaystyle f: V ^ {2} \ to \ mathbb {R}}$ care satisface următoarele două constrângeri: ^[2]

Constrângerea capacității .

f(u,v)\leq c(u,v)\forall u,v\in V

{\ displaystyle f (u, v) \ leq c (u, v) \ forall u, v \ in V}

{\ displaystyle f (u, v) \ leq c (u, v) \ forall u, v \ in V}

. Fluxul de-a lungul unui arc nu poate depăși capacitatea acestuia.

Hemimetrie . Fluxul de-a lungul unui arc

k=(u,v)

{\ displaystyle k = (u, v)}

{\ displaystyle k = (u, v)}

trebuie să aibă semnul opus dacă k este încrucișat de la v la u .

f(u,v)=-f(v,u)\forall u,v\in V

{\ displaystyle f (u, v) = - f (v, u) \ forall u, v \ in V}

{\ displaystyle f (u, v) = - f (v, u) \ forall u, v \ in V}

.

Pornind de la definiția pseudofluxului, se pot adăuga alte constrângeri pentru a obține tipuri de flux mai specifice. Un flux admisibil ^[2] (notat simplu ca „flux”) trebuie să îndeplinească următoarea regulă:

Conservarea fluxului .

\sum _{v\in V}f(v,u)=\sum _{v\in V}f(u,v),\quad \forall u\in V\setminus \{s,t\}

{\ displaystyle \ sum _ {v \ in V} f (v, u) = \ sum _ {v \ in V} f (u, v), \ quad \ forall u \ in V \ setminus \ {s, t \}}

{\ displaystyle \ sum _ {v \ in V} f (v, u) = \ sum _ {v \ in V} f (u, v), \ quad \ forall u \ in V \ setminus \ {s, t \}}

. Pentru fiecare nod fluxul de intrare trebuie să fie egal cu cel de ieșire. ^[2]

Concepte utile pentru probleme de flux

Grafic rezidual

Având în vedere un flux $X$ ${\ displaystyle x}$ $X$ admisibil, graficul rezidual (relativ la $X$ ${\ displaystyle x}$ $X$ ) este un grafic $G(x)=(V,E(x))$ ${\ displaystyle G (x) = (V, E (x))}$ ${\ displaystyle G (x) = (V, E (x))}$ cu aceleași noduri ca și graficul $G.,$ ${\ displaystyle G,}$ ${\ displaystyle G,}$ în timp ce arcurile și capacitățile lor $r_{ij},$ ${\ displaystyle r_ {ij},}$ ${\ displaystyle r_ {ij},}$ numite reziduuri, sunt definite după cum urmează:

{\begin{aligned}(i,j)&\in E,\quad x_{ij}<u_{ij}\;\Longrightarrow (i,j)\in E(x),\quad r_{ij}=u_{ij}-x_{ij}\\(i,j)&\in E,\quad x_{ij}>0\quad \Longrightarrow (j,i)\in E(x),\quad r_{ji}=x_{ij}\end{aligned}}

{\ displaystyle {\ begin {align} (i, j) & \ în E, \ quad x_ {ij} <u_ {ij} \; \ Longrightarrow (i, j) \ in E (x), \ quad r_ { ij} = u_ {ij} -x_ {ij} \\ (i, j) & \ in E, \ quad x_ {ij}> 0 \ quad \ Longrightarrow (j, i) \ in E (x), \ quad r_ {ji} = x_ {ij} \ end {align}}}

{\ displaystyle {\ begin {align} (i, j) & \ în E, \ quad x_ {ij} <u_ {ij} \; \ Longrightarrow (i, j) \ in E (x), \ quad r_ { ij} = u_ {ij} -x_ {ij} \\ (i, j) & \ in E, \ quad x_ {ij}> 0 \ quad \ Longrightarrow (j, i) \ in E (x), \ quad r_ {ji} = x_ {ij} \ end {align}}}

În creștere

Având în vedere un flux $X$ ${\ displaystyle x}$ $X$ admisibil, o cale de mărire (cu privire la $X$ ${\ displaystyle x}$ $X$ ) este o cale orientată de $s$ ${\ displaystyle s}$ $s$ la $t$ ${\ displaystyle t}$ $t$ în graficul rezidual $G(x)$ ${\ displaystyle G (x)}$ $G (x)$ , unde este $s$ ${\ displaystyle s}$ $s$ este nodul de origine (sau sursă) e $t$ ${\ displaystyle t}$ $t$ este nodul de destinație (sau bine).

Aplicații

Rețelele de flux au multe aplicații practice, deoarece permit reprezentarea situațiilor reale cu un model matematic relativ simplu. Problema cea mai frecvent asociată cu rețelele de curgere este cea a debitului maxim , adică a găsi valoarea debitului maxim care poate fi „generată” de sursă și a ajunge la fântână fără a depăși capacitățile arcurilor individuale. Problema poate fi rezolvată eficient cu ajutorul algoritmului Ford-Fulkerson . O altă problemă tipică acestui subiect este cea a fluxului de cost minim .

Notă

^(RO) AV Goldberg, É. Tardos și RE Tarjan, Algoritmi de flux de rețea, Tech. Raport STAN-CS-89-1252, Universitatea Stanford CS Dept., 1989
^ ^a ^b ^c ^d ^și Domenico Cantone, Grafice și rețele de flux ( PDF ), pe dmi.unict.it , Universitatea din Catania , Departamentul de matematică și informatică. Adus la 30 august 2016 ( arhivat la 30 august 2016) .

Bibliografie

Passacantando M .; Pappalardo M. (2013). " Cercetări operaționale" Pisa University Press ISBN 9788867410736

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere din rețeaua de flux

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] (RO) AV Goldberg, É. Tardos și RE Tarjan, Algoritmi de flux de rețea, Tech. Raport STAN-CS-89-1252, Universitatea Stanford CS Dept., 1989

[cantone-2] și Domenico Cantone, Grafice și rețele de flux ( PDF ), pe dmi.unict.it , Universitatea din Catania , Departamentul de matematică și informatică. Adus la 30 august 2016 ( arhivat la 30 august 2016) .

[1]

[2]