Matematici discrete - Secțiunea 2

Fie N = (G, a) - o rețea cu o singură sursă și una de scurgere b. Să presupunem că N este o diagramă rețea de linii de comunicație, în care nodurile corespund nodurilor de comunicație, arce - link respectiva direcție de transmitere a informațiilor. Dacă e - rețeaua arc N, valoarea unei (e) mijloace pentru a limita cantitatea de informații transmise prin intermediul unui arc e pentru o anumită perioadă de timp. Următoarea întrebare. Care este cantitatea maximă de informații pot fi transmise de la A la B, și cum se face? Răspunsul la această întrebare, iar această secțiune este dedicată.

În urma interpretării rețelei de mai sus sunt de acord valoare a (e) apel tranzitată capacitate arc e.

Conceptul central al acestei secțiuni este cea a fluxului în rețea.

Definiția. Fie N = (G, a) - rețeaua, și - sursa și b - Stock această rețea. Curgerea prin rețeaua N este o funcție

îndeplinește următoarele două condiții:

1) j (e) £ a (e) pentru orice arc e Î E,

2) în rețea (G, j) la orice nod cu excepția sursei și de scurgere outdegree indegree egale. Numărul j (f) se numește valoarea fluxului prin arc e.

Fig. 6.16 este un exemplu de flux prin rețeaua descrisă în Fig. 6.15. Valorile j sunt prezentate în paranteze.

Oferta. Să j - curgă prin rețeaua N = (G, a). Apoi, valoarea debitului prin incidentul cu arc la sursa, este suma fluxurilor prin incidentul cu arc să se scurgă.

Dovada. Fie V = 1, v2, ..., vzg>, în care v1 - sursă, v2 - scurgerile. Să considerăm o rețea de N „= (G, j). Rezultatul la jumătate suma de rețea N“din toate nodurile egale cu suma tuturor nodurilor indegree

pentru că pentru orice număr de e j arc (e) joacă exact o dată în stânga și în dreapta suma. Deoarece j - debitul, r - (vi) = r + (vi) i = 3, ..., n. Acest lucru înseamnă că r - (v1) + r - (v2) = r + (v1) + r + (v2). Din ultima egalitate obținem r - (v1) = r + (v2), deoarece

Definiția. Suma menționată în propoziția de mai sus se numește cantitate de flux dovedit. Alimentarea este maximă. în cazul în care are cea mai mare valoare (printre toate fluxurile printr-o anumită rețea).

J flux este notat cu ½ j ½. Fluxul prezentat în Fig. 6.16, are o valoare de 5. Acest flux este la maxim, deoarece valoarea sa privind incidentul arcelor la scurgere este egală cu suma capacităților acestor arce. Rețeaua poate avea mai mult decât debitul maxim, așa cum exemplul prezentat în Fig. 6,17

Atunci când studiază debitul maxim în rețea utilizează conceptul de tăiere.

Definiția. rețea Slit N, având o singură sursă și una de scurgere, S este mulțimea de arce, astfel încât orice cale de la sursa la scurgere trece printr-un arc de S.

Definiția. secțiunea Lățimea de bandă este suma capacităților individuale ale arcelor sale membre. Incizia se numește minim. în cazul în care are cea mai mică capacitate (între toate secțiunile rețelei). Capacitatea de tranzit a secțiunii S va fi notată cu (S).

De exemplu, pentru rețeaua din Fig. 6.18 Exemple incizii sunt setate S1 =, S2 =, S3 =. Aceste reduceri au lățimi de bandă, respectiv, 7.6 și 6. Fantele S2 și S3 sunt minime. Vedem că reducerile minime pot fi puține.

Se pare că, pentru orice valoare a rețelei de debit maxim coincide cu lățimea de bandă a inciziei minime. Acest rezultat a fost obținut de matematicieni americani Ford și Folkersonom în 1955. Noi da o dovadă, cu toate acestea, observăm mai întâi un număr de fapte de sprijin.

Dacă j - curge prin rețeaua N = (G, a), apoi prin G j vom nota subgraful a graficului G, care conține un arc în lungul căreia fluxul de zero (și numai acelea cu arc).

Lema 1. Pentru fiecare j flux prin rețeaua N = (G, a) flux j există prin aceeași rețea astfel încât ½ j ½ = ½ ½ y și G y - subgrafic circuit fără G j.

Dovada. Să presupunem că graficul G j conține conturul C trece de-a lungul e1 arce, e2, ... EL. Dintre numerele j (e1), j (e2), ..., j (el) pentru a alege cel mai puțin, să fie numărul de m. Luați în considerare funcția # 952 ;: E ® N È Definită după cum urmează:

Este ușor de a verifica dacă # 952; - debitul prin intermediul rețelei N, ½ j ½ = ½ # 952; ½ și G # 952; - subgraf al lui G j. Earl G # 952; nu mai conține contur C. Repetând această procedură ca de multe ori, ca rezultat vom obține fluxul de y necesar.

Lema 2. Fie j - Fluxul nenul prin N de rețea cu sursa și de scurgere și b. Apoi, există este simplu (a, b) - un traseu care trece de-a lungul arcelor cu flux nenul.

Dovada. Prin Lema 1, se poate presupune că graficul G j = (V, E j) nu conține bucle. Să Va - set de vârfuri ale Gj. realizabile din vârful A. Deoarece graficul Gj nu conține bucle, atunci setul Va conține cel puțin un nod x, care este un canal de scurgere în graficul G j. Este clar că x ¹ bine. Dacă x ¹ b, atunci graful G există arc cu flux nenul apel la x, și nu există margini cu flux nenul care provin de la x. Aceasta contrazice definiția fluxului. Prin urmare, b Î Va. și anume într-un grafic G j este accesibil din nodul b și. Aceasta înseamnă că rețeaua N este un simplu (a, b) - o cale de extindere a lungul arcelor unui flux non-zero.

Lema 3. Valoarea oricărui flux prin intermediul rețelei nu depășește capacitatea de orice secțiune a rețelei.

Dovada. Să j - curgă prin rețeaua N = (G, a), S - secțiune a rețelei. Să ne amintim că debitul este notat cu ½ j ½ productivitatea si capacitatea de taiere - printr-o (S).

Să presupunem mai întâi că funcția j este un număr întreg. Bazat pe rețeaua N și fluxul j. Noi construim un graf orientat G „cu mai multe arce. Setul de noduri ale grafului G „este mulțimea nodurilor inițiale ale lui G. Dacă e - (x, y) și arcul graficului G j (f)> 0, atunci graficul G“ zugrăvi j (f) din arce care provin de la x și intră în y. Dacă j (e) = 0 sau G nu are nici un arc de la x la y, apoi în G“, de asemenea, nu există nici un arc de la x la y. Fig. 6.20 prezintă un grafic al lui G“, construit pentru rețeaua N și fluxul (în paranteze) așa cum este prezentat în Fig. 6.19.

Lema 2 implică faptul că graficul G „există o pluralitate de R ½ j ½ simplă (a, b) -paths, oricare două dintre acestea conțin un arc totală. Vom nota cu „pluralitate de arce ale grafului G“, care este derivat din arce tăiate S. In mod clar, S S „- secțiune a graficului G“ și că numărul de muchii din S „este mai mică sau egală cu o (S). Fiecare din multitudinea de piese P cuprinde cel puțin un arc S „în care cele două căi diferite pot să nu conțină același arc S“. Aceasta înseamnă că numărul de căi în P nu depășește numărul de arce în S“, adică ½ j ½ = ½ P ½ £ ½ S „½ £ a (S).

Să considerăm acum cazul când j ia valori raționale. Să m - cel mai mic multiplu comun al numitorul funcției j. Apoi funcția m · j este rețeaua de flux (G; m · a). În mod evident, mulțimea S este tăiat și o nouă rețea cu o lățime de bandă egală cu m · a (S). În paragraful precedent, sa dovedit că ½ m · j ½ £ m · a (S). Prin urmare, inegalitatea ½ j ½ £ a (S).

Cazul general, adică când orice valori permise ale capacităților și a fluxului este redus la cele de mai sus cu următoarele afirmații. Pentru orice rețea N = (G, a) cu un curent de j și o fantă S și orice număr e> 0, există un flux rațional j 0 prin aceeași rețea, astfel încât - e <½ j ½ – ½ j 0 ½

Pentru a introduce în continuare unele notație. Fie N = (G, a) - o rețea având o sursă și un canal de scurgere b, D - o multitudine de noduri de rețea, astfel încât o Î D, b Ï D. Apoi setul de muchii

notat cu SD. Este ușor de verificat că setul de SD este o vedere în secțiune a rețelei. Această secțiune va fi numit-D tăiat. Dacă X și Y - seturi nevide de noduri și j - curg prin rețea,

Lema 4. Fie N = (G, a) - o rețea având o sursă și un canal de scurgere b, j - curge prin rețea, D - o multitudine de noduri de rețea care cuprinde un conținut și b. atunci

Dovada. Prin definiție flux pentru x ¹ a și x ¹ b avem egale

și determinarea cantității de curgere - egal

j (a, V) - j (V, a) = ½ j ½.

Din aceste ecuații rezultă că

½ j ½ = (j (x, V) - j (V, x)) = j (D, V) - j (V, D).

Teorema. În orice rețea este valoarea capacității de curgere maximă a tăieturii minime.

Dovada. Să j - debitul maxim într-o rețea N = (G, a). Prin Lema 3, demonstrează existența tăieturii suficient S astfel încât o (S) = ½ j ½.

Putem presupune că G j - grafic liber (a se vedea Lema 1.).

Arc e se numește saturată dacă j (e) = a (e). Litera D denota multimea de noduri, care cuprinde: un canal de scurgere și nodurile u, pentru care există o secvență

astfel încât arc (xi. xi + 1) nesaturat sau prin intermediul arcului (xi + 1. xi) se extinde fluxul de non-zero. De exemplu, rețeaua prezentată în Fig. 6.21. = D. Rețineți că z Î D, deși arcul (y, z) în rețeaua nu.

Pretindem că b Ï D. Presupunem că acest lucru nu este adevărat, și anume, b Î D. Apoi, există o secvență de noduri

forma de mai sus (și anume, fie un arc (yi, yi + 1) nesaturat sau printr-un arc (yi + 1, yi) se extinde fluxul de non-zero). Să e - un număr pozitiv, care este mai mică decât diferența a (e) - j (e) pentru orice e arc nesaturat și mai puțin orice zero, non-flux net prin arc.

Modificarea valorii j fluxului pe arcuri urmează lanț. Dacă arcul (yi, yi + 1) nesaturat, am stabilit j „(yi + 1, yi + 1) = j (yi, yi + 1) + e. Dacă acest arc este saturată, apoi lăsați-j „(yi + 1, yi) = j (yi + 1, yi) - e. Pentru alte valori de curgere arce e lăsați nemodificat: j „(e) = j (e).

Este ușor de a verifica dacă j „- flux prin N. rețea De fapt, restrictionarea j“ (e) £ a (e) este valabil pentru orice e arc de cerc pentru a construi un j“. În cazul în care v nod nu trece lanț (*), debitul total prin v este zero, din moment ce acest lucru este valabil și pentru j. Fie v = yi pentru unii i Î . Există patru cazuri determinate de saturație sau arce de nesaturare (yi-1, yi) și (yi, yi + 1). (Acesta va fi convenabil să ia în considerare arcul lipsă saturat) Luați în considerare doar una dintre ele: arcul (yi-1, yi) nesaturat și arcul (yi, yi + 1) este saturată. Vom nota cu A multimea de noduri din care trec cu vederea arcului, care intră în yi. set B scrisoare de noduri ale rețelei, care primește arcul iese din yi. atunci

ca j - flux. În tranziția de la j la j „termeni în partea dreaptă nu se schimbă, iar cei doi termeni pe schimbarea din stânga: j (yi-1, yi) se înlocuiesc cu j (yi-1, yi) + e. și j (yi + 1, yi) - pentru j (yi + 1, yi) - e. dar întreaga sumă va rămâne aceeași. Prin urmare, ecuația (**) continuă în tranziția de la j la j“. Noi am demonstrat că j „- curge prin N. rețelei Cu toate acestea, valoarea sa este egală cu ½ j ½ + e. ceea ce contrazice maximal j curgere. Astfel, b Ï D.

În cazul în care u Î D și există un arc de la intrarea nodurile u v, cu nenulă curgere, atunci v Î D. Aceasta înseamnă că j (D) = 0. Luați în considerare SD incizie. Apoi Lema 4 care ½ j ½ = a (SD), ca (SD) = j (D).

La fel ca în desen a rețelei pentru a construi mai ușor decât găsirea unui flux prin rețea, teorema Ford-Folkersona pentru rețele simple pot fi utilizate pentru a determina debitul maxim în rețea. Cu toate acestea, pentru o rețea mai mult sau mai puțin complexe, chiar dacă valoarea debitului maxim găsit el însuși greu pentru a construi fluxul. Prin urmare, vom prezenta un algoritm de rezolvare a problemei de construire a fluxului maxim pentru rețele cu lățimi de bandă întregi. Rețineți că, în timpul unui algoritm poate apărea în cazul în care rețelele fără sursă sau scurgere.

Algoritmul pentru identificarea debitului maxim

rețea Dana (G, a), a - sursă, b - rețea de stoc, a: E ® N.

Pasul 1. În cazul în care nu există nici o cale de la sursa la scurgere, apoi pune J = 0 și mergeți la pasul 4, sau selectați un non-gol arce set T disjuncte de trasee de la a la b. Dacă e1, e2, ..., ek - calea T, care este o secvență de arce, apoi pune j (e1) = j (e2) = ... = j (ek) = min. Pentru arce e, după care nu merg pe calea T, a pus j (e) = 0. Rezultatul este nenul flux j prin intermediul rețelei (G, a).

Pasul 2. Pe rețea (G, a) și fluxul j pentru a construi o rețea (G 'o'), după cum urmează. G Earl 'va avea aceleași ca nodurile grafului G. Dacă e - grafic arc G și (e) - j (e) ¹ 0, e - Graficul arc G' și a „(e) = a (e ) - j (e). Dacă e - Count Arc și G j (e) ¹ 0, atunci vom introduce un arc de orientare inversă decât e, și să își asume o „() = j (e). În cazul în care există și e1 e2 arce multiple. apoi le introducem într-un singur arc, în loc de e și să își asume o '(e) = a' (e1) + o „(e2).

Etapa 3, apoi mergeți la pasul 4, în caz contrar rețeaua (G 'o') pentru a construi un non-zero flux j 'Dacă rețeaua (G', o „), nu există nici o cale de la a la b prescrise în 1. pentru o rețea (G, a) set j = j + j „și mergeți la pasul 2.

Etapa 4. Pentru a elibera j. Sfârșitul algoritmului.

Pe exemplul rețelei prezentată în Figura 6.22 ilustrează algoritmul. Deoarece setul T în prima etapă a algoritmului este selectat dintr-o multitudine de două moduri: a, v1, v4, b și, v2, v5 b,.

Fig. 6.23 arată rețea (G „o“) obținută după etapa 2 a rețelei din fig. 6.22 cu un j flux specificat (în paranteze).“ Deoarece T setat pentru a construi fluxul de j „luat un set format dintr-o singură cale: a, v3, v5, v2, v6, b. Hrană j + j „pentru rețea (G, a) în Fig. 6,24. Acest algoritm-o singură trecere este finalizată. Menționăm că pentru e = (v2, v5) (j + j ') (e) = j (e) - j' () = 1.

Rețeaua construită în etapa 2 din a doua trecere a algoritmului deja (a, b) - căi (vezi Figura 6.25.). De aceea, în fig. 6.24 arată debitul maxim.