calea reziduală Rezumat al cutiei de transport

introducere

• 1 Definiții
• 2 proprietăți
• EXEMPLUL 3
• 4 Referințe Aplicație
  

In teoria grafurilor, rețeaua de transport - un graf orientat G = (V, E). în care fiecare nervură are o capacitate de non-negativ și potokf (u, v). Identifică două vârfuri: istochniks și stokt astfel încât orice alt nod de minciuni pe drumul de la s la t. Rețeaua de transport poate fi utilizat pentru a simula, de exemplu, traficul rutier.

Integer rețea de transport - rețea de transport, toate capacitățile de margini care - numere întregi.

1. Definiții

Rețeaua de transport (rețea de flux) - un grafic direcționat în care

• fiecare muchie este atribuită o lățime de bandă non-negativ. În cazul în care, atunci.
• alocate două vârfuri: o sursă (sursă) s și de scurgere (chiuveta) t. astfel încât orice alt nod de rețea se află pe drumul de la s la t.

Stream (debit) - funcția cu următoarele proprietăți pentru toate nodurile:

• Limitarea lățimii de bandă (constrângeri de capacitate). Fluxul nu poate depăși capacitatea de:
• Antisimetrie (simetrie oblic). Fluxul de trebuie să fie opusă fluxului de:
• Menținerea debitului (de conservare a fluxului): pentru toate, dar sursa și de scurgere.

„Cantitatea de flux (valoarea debitului) este suma sursei de flux. În viitor, vom dovedi că este egală cu valoarea debitului în scurgere.

problemă maximă de curgere (problemă de curgere maximă): găsiți fluxul f astfel încât debitul este maxim.

Incizia (s-t cut) - partiționare multimea tuturor nodurilor din V în două subseturi, A și B, astfel încât.

secțiunea Capacitatea Throughput (A, B) (capacitatea unui s-t cut (A, B)) - suma capacităților tuturor muchiilor A în B.

Curgerea prin incizie (A, B) - suma tuturor fluxurilor de la A la B. Aceasta nu depășește capacitatea de lățime de bandă de tăiere, deoarece.

Minimă tăiat - taie capacitatea minimă.

Capacitatea reziduală (capacitate reziduală) Este întotdeauna marginile non-negative ale condiției de a limita latimea de banda.

rețea reziduală (rețea reziduală) aici - o mulțime de coaste cu lățime de bandă reziduală non-negativ. Nervura poate fi rețeaua reziduală de la, chiar dacă nu este în rețeaua de domiciliu. Acest lucru se face atunci când în rețeaua de domiciliu are o margine inversă (v, u) și fluxul este pozitiv.

Creșteri (rezidual adiționale) modul (augmentarea cale) - o cale în rețeaua reziduală, în cazul în care se poate demonstra că debitul este maxim dacă și numai dacă nu există nici o modalitate de a consolida rețeaua reziduală.

2. proprietăţi

Fluxul prin fiecare secțiune este suma fluxurilor de la sursa.
Dovada. lasa o tăietură (A, B). Luați în considerare suma tuturor fluxurilor de la toate nodurile care aparțin A. Este

In primele sume pentru orice pereche de noduri (u, v) are doi termeni f (u, v) și f (v, u), egale în mărime și opuse în semn. Prin urmare, această sumă este egală cu zero. A doua sumă este fluxul prin secțiunea (A, B). În consecință, suma tuturor fluxurilor de toate nodurile care aparțin A, este egal cu debitul prin incizie. Pe de altă parte, suma fluxurilor de la orice nod, cu excepția s și t, este egal cu zero. Prin urmare, suma tuturor fluxurilor de la toate nodurile care aparțin A, este suma fluxurilor din s. În consecință, fluxul prin secțiunea (A, B) este egal cu suma fluxurilor s, QED.

Cantitatea de fluxuri sursă este suma debitului la scurgere.
Dovada. ia în considerare reducerea. Fluxul prin această secțiune de curgere este suma de scurgere. Pe de altă parte, tocmai a fost demonstrat, fluxul prin aceasta (sau orice alt) secțiune este suma fluxurilor de la sursa. Acest lucru dovedește teorema.

Fluxul maxim este pozitiv dacă și numai dacă există o cale de la sursa la scurgere, nervurile ce se extind pe lățimea de bandă pozitivă.
Dovada. Lăsați această cale P există. Fie c - throughputs minime de margini aparținând P. Fie c fluxul este la toate marginile P, și zero la toate celelalte margini. Apoi, fluxul total de sursă este egal cu c, atunci este pozitiv. Acum, să spunem că acest lucru este nici o cale care este inaccesibil din tS în coaste cu o lățime de bandă pozitivă. Fie A - o multitudine de noduri accesibile prin e către astfel coaste, B - imposibil de atins. Apoi, de atunci (A, B) este tăiată. În plus, există nervuri (a, b) cu o lățime de bandă pozitivă, astfel încât, sau b ar fi realizabile din s. Prin urmare, capacitatea de tranzit a secțiunii (A, B) este zero și astfel este întotdeauna curgerii zero. Prin urmare, cantitatea de curgere de la sursă este întotdeauna zero.

Fluxul este maxim dacă și numai dacă nu există nici o modalitate de a spori seti.Dokazatelstvo reziduale. lasa o astfel de cale de P este. Fie C - minimum capacitățile marginilor care aparțin P, în rețeaua reziduală. Pentru toate perechile cresc f (u, v) pentru a reduce c și f (v, u) prin c. Am mărit fluxul total de la o sursă s, de aceea, el nu a fost maximă. Acum, dimpotrivă, spun că acest lucru este nici o cale. Să dovedească prin contradicție că fluxul de f în rețeaua de domiciliu asigură un debit maxim total de s. Să presupunem că acest lucru nu este cazul, atunci există un flux f“, care asigură un debit total mai mare de s. Este ușor de a verifica dacă f'-f - debitul în rețeaua reziduală, oferind un flux pozitiv de suma s. Prin urmare, rețeaua reziduală este o cale de la sursa la chiuveta, adică calea crește. Am obținut o contradicție.

Ford-Fulkerson teorema. Valoarea debitului maxim este capacitatea minimă de tăiere.
Dovada. valoarea debitului de e întotdeauna egală cu fluxul prin orice, inclusiv minim, tăiate, prin urmare, nu depășesc capacitatea de suportabilitate a tăieturii minime. În consecință, capacitatea maximă de curgere de cel mult o incizie minimă. Rămâne să dovedească faptul că el nu este mai mică decât aceasta. Lăsați fluxul este maxim. Apoi, rețeaua de flux rezidual nu este accesibil de la sursa. Fie A - o multitudine de noduri accesibil de la sursă la rețeaua reziduală B - imposibil de atins. Apoi, de atunci (A, B) este tăiată. În plus, există nervuri (a, b) într-o lățime de bandă de net pozitiv rezidual, astfel încât ar fi fost atinse b de s. Prin urmare, în rețeaua sursă în conformitate cu orice flux astfel de margine este egală cu capacitatea sa, și, prin urmare, fluxul prin secțiunea (A, B) este egală cu lățime de bandă. Dar fluxul prin orice incizie este fluxul total de la sursa, care în acest caz este egal cu debitul maxim. Pe de altă parte, capacitatea de orice reducere nu este mai mică decât reducerea capacității minime. Prin combinarea acestor trei afirmații, constatăm că capacitatea maximă de curgere de cel puțin tăiat minim. Acest lucru dovedește teorema.

Rețeaua de transport cu indicarea debitului și a lățimii de bandă.

Aici se arată rețeaua de transport la sursa, scurgere, și patru unități suplimentare. Hrana pentru animale și lățime de bandă, respectiv, notat. Fluxul de la sursa la scurgere este de 5, care este ușor de văzut, deoarece fluxul este de la 5, care este de asemenea disponibil.

vedere reziduale planul de rețea a unui flux care prezintă o capacitate reziduală.

Mai jos este rezidualul pentru fluxul de rețea de mai sus. Vă rugăm să rețineți că există limita capacitatea unor coaste, în timp ce în rețeaua de domiciliu, este egal cu zero. De exemplu, o margine. Acest flux nu este maxim. Există modalități de a crește și. Capacitatea reziduală a primei căi. Creșterea calea nu există în rețeaua de domiciliu, dar o puteți sări pentru fluxul corect.

4. Aplicații

Cel mai frecvent exemplu de utilizare a rețelelor de transport - găsirea debitul maxim. ceea ce înseamnă că debitul total maxim de la s la t. Fulkerson, Edmonds algoritm - - Pentru a găsi debitul maxim în rețeaua Ford algoritmul poate fi utilizat Karp și altele.

Problema fluxului de cost minim, fiecare muchie (u, v) este mapat la k preț (u, v). Costuri de expediere flux f (u, v) printr-o nervură. Sarcina - pentru a trimite o cantitate predeterminată de curgere de la s la t cu cel mai mic pret.

literatură