De la Wikimanuale
12. Rețele, fluxuri în rețele. Teorema lui Ford-Falkerson
Fluxul în rețea între vârf t (sursa) și s (de scurgere) este un set de numere Sij, (de exemplu, numărul de „încărcare“ condiționată, efectuate cu vârful i trece prin punctul număr cu numărul j ..), satisfăcând cele patru condiții:
1) numerele cij Ј 0 și dacă cij> 0, atunci cji = 0 (nu există contratransportări);
2) numerele cij Ј qij (corespunzătoare capacității marginilor);
3) dacă vârful cu numărul i este intermediar (nu coincide cu sursa și scurge), atunci
adică, cantitatea de "încărcătură" exportată de la punctul i este egală cu cantitatea de "încărcătură" care este importată în acest vârf;
4) cantitatea de "încărcătură" exportată din sursa t ar trebui să fie egală cu cantitatea de marfă importată în chiuveta s:
Numărul A se numește valoarea unui flux dat sau pur și simplu un flux între t și s.
Pentru următoarele avem nevoie de următoarea definiție:
Să fie o secțiune între vârfurile t și s. Apoi, valoarea secțiunii transversale este suma sumelor de trecere ale marginilor care intră în această secțiune. O secțiune este numită minimă (maximală) dacă valoarea acesteia este minimă (maximă).
Teorema lui Ford-Falkerson (1955). Debitul maxim între noduri s și t este egală cu secțiunea transversală minimă între aceste noduri.
Dovada acestei teoreme este constructivă (adică arată modul în care se găsește fluxul maxim maxim necesar), așa că este dată mai jos.
Mai exact, mulțimea de vârfuri etichetate ale lui Y se formează după cum urmează:
sursa t aparține lui Y și etichetei sale (0,)); al doilea număr, relativ vorbind, este egal cu infinitul - care pentru matematica discretă înseamnă că este un număr cât mai mare de care avem nevoie;
dacă vârful i aparține lui Y și cij
în cazul în care nodul k aparține Y și SJK> 0 (arc invers), atunci nodul cu numărul j trebuie să aparțină Y și notarea sa este (- a, dj), unde semnul minus indică faptul că vertex j asociat cu vertexul deja etichetate cu arc invers , dj = min, și este evident că dj, de asemenea, strict mai mare decât zero. Astfel, construcția setului Y este inductiv, t. E. nod nou se adaugă la Y, în cazul în care acesta este asociat cu unele vertex deja incluse în Y sau nesaturat liniar arc sau feedback-arc.
După finalizarea construcției setului Y (nu se mai pot adăuga noduri noi), sunt posibile două cazuri.
1. Stoc (t. E. Vârful cu numărul s) nu este inclus în setul de nodurile Y. Apoi multimea de vârfuri în afara Y de Z. este conectat graficul nostru de condiție, prin urmare, Y, sunt unele margini în Z. În conformitate cu regulile de construcție a lui Y, toate aceste margini sunt arce drepte saturate (figura 7).
Marginile de la setul Y la Z formează o secțiune între vârfurile t și s. Se observă, de asemenea, că suma capacității marginilor acestei secțiuni (și toate aceste margini sunt drepte, saturate) este egală cu debitul de la t la s. Aceasta înseamnă că fluxul dat este maxim (deoarece este egal cu valoarea unei secțiuni), iar această secțiune transversală este minimă.
S 2. Partea superioară este inclusă și în Y, și lăsați al doilea număr este sa tagging d s> 0. Apoi, este evident că între vârfurile s și t are un lant (format din muchii dirijate - arce directe și inverse) care leagă aceste noduri
Schematic acest lucru este arătat în Fig. 8. t ® · ® · β · β · · · · · · · · · · · · · · ®s
Rețineți că arcul care iese din sursă și arcul care intră în scurgere trebuie neapărat să fie drept. Adăugați DS CJI Îndreptarea arce lanțului (de construcție se poate observa că numărul rezultat este mai mic sau qij egal) și scade acest DS de CJI pentru arce inverse (se poate obține un număr negativ, dar este în mod necesar în valoare absolută mai puțin qij, deoarece pentru a construi un DS £ CJI + qij. ceea ce înseamnă că arcul invers își schimbă direcția, ea devine un arc drept și a „sarcină“ va fi egal cu modulul de numere, apoi noi pentru arce din lanțul nostru, precum și „vechi“ CJI pentru toate arcele care nu sunt incluse în circuitul nostru, formează un flux nou de la vârful la vârf T s (le verifica blând argument simplu că noile numere ale următoarelor condiții (1) - (4).) În plus, valoarea noul flux comparativ cu vechiul crescut DS> 0. Pentru un nou fir din nou să efectueze aceeași procedură, și așa mai departe ..
Din moment ce de fiecare dată când debitul este crescut cu cel puțin 1 (lățimi de bandă coaste sunt numere întregi), iar debitul maxim este limitat (valoare minimă secțiune), această procedură nu poate continua la nesfârșit, și, prin urmare, la un pas obținem un flux pentru care vârful s nu intră în Y, adică fluxul este maxim și valoarea sa este egală cu valoarea secțiunii minime. Teorema este dovedită.
Motivarea teoremei Ford-Falkerson este, de fapt, un algoritm pentru găsirea fluxului maxim între două vârfuri (sau dovedind că acest flux este maxim). Un exemplu detaliat pe această temă este prezentat în sec. 15 "Rezolvarea problemelor tipice".
Notă. Dacă în acest grafic cu capacitatea marginilor (adică a rețelei) există mai multe surse și mai multe canale de scurgere, atunci algoritmul descris mai sus poate fi aplicat după cum urmează. Să introducă o nouă sursă și o nouă chiuvetă, și nouă sursă conectate printr-o margine cu toate sursele, și o nouă chiuvetă - cu toate chiuvete, și capacitățile noilor muchii cred numere arbitrar de mare, astfel încât arcul în orice flux posibil ar fi nesaturat (rechemare că marginile care vin de la sursă și marginile care intră în scurgere sunt întotdeauna arce drepte). După aceea, pentru noul grafic, rezolvăm problema debitului maxim (de la o sursă nouă la o nouă chiuvetă). După ce l-am rezolvat, ștergem toate margini și vârfuri introduse.
Să luăm în considerare și alte întrebări (de natură mai degrabă generale) din teoria graficelor. Menționăm că în secțiunile următoare vom da doar cele mai simple dovezi, iar dovezile principale sunt date în cartea lui R. Wilson [6].
Articole similare
-
Povești de succes, Rive Gauche - o rețea de magazine de cosmetice și parfumerie
-
Configurarea routerelor pentru linia kinetică zyxel pentru o rețea multinoculară
Trimiteți-le prietenilor: