Teorema debitului maxim și a forfecării minime

Teorema debitului maxim și a tăierii minime (cunoscută și sub denumirea de debit maxim ) spune că, într-o rețea de curgere , debitul maxim care trece de la sursă (nodul inițial) la fântână (nodul final) este egal cu suma greutăților arcurilor în tăietura minimă .

Este o generalizare a problemei primare standard , tipică programării liniare .

Teorema a fost dovedită de P. Elias , A. Feinstein și CE Shannon în 1956 și în mod independent și de LR Ford Jr. și DR Fulkerson în același an. ^[1]

Definiții și formulare

Este $N=(V,E)$ ${\ displaystyle N = (V, E)}$ ${\ displaystyle N = (V, E)}$ o rețea de curgere, cu s și t respectiv sursă și chiuvetă de N.

Debit maxim

Același subiect în detaliu: problema debitului maxim .

Definiție. Un flux este o funcție $f:E\to R^{+}$ ${\ displaystyle f: E \ to R ^ {+}}$ ${\ displaystyle f: E \ to R ^ {+}}$ pe care le atribuie fiecărui arc $(u,v)\in E$ ${\ displaystyle (u, v) \ în E}$ ${\ displaystyle (u, v) \ în E}$ o valoare notată cu $f_{uv}$ ${\ displaystyle f_ {uv}}$ ${\ displaystyle f_ {uv}}$ sau $f(u,v)$ ${\ displaystyle f (u, v)}$ ${\ displaystyle f (u, v)}$ . Fluxul este supus a două constrângeri:

Constrângerea capacității:
$\forall (u,v)\in E:\qquad f_{uv}\leq c_{uv}$ ${\ displaystyle \ forall (u, v) \ în E: \ qquad f_ {uv} \ leq c_ {uv}}$ ${\ displaystyle \ forall (u, v) \ în E: \ qquad f_ {uv} \ leq c_ {uv}}$
Conservarea debitului:
$\forall v\in V\setminus \{s,t\}:\qquad \sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{u:(v,u)\in E\}}f_{vu}.$ ${\ displaystyle \ forall v \ in V \ setminus \ {s, t \}: \ qquad \ sum \ nolimits _ {\ {u: (u, v) \ in E \}} f_ {uv} = \ sum \ nolimits _ {\ {u: (v, u) \ in E \}} f_ {vu}.}$ ${\ displaystyle \ forall v \ in V \ setminus \ {s, t \}: \ qquad \ sum \ nolimits _ {\ {u: (u, v) \ in E \}} f_ {uv} = \ sum \ nolimits _ {\ {u: (v, u) \ in E \}} f_ {vu}.}$

Definiție. Capacitatea este o funcție $c:E\to R^{+}$ ${\ displaystyle c: E \ to R ^ {+}}$ ${\ displaystyle c: E \ to R ^ {+}}$ pe care le atribuie fiecărui arc $(u,v)\in E$ ${\ displaystyle (u, v) \ în E}$ ${\ displaystyle (u, v) \ în E}$ o valoare notată cu $c_{uv}$ ${\ displaystyle c_ {uv}}$ ${\ displaystyle c_ {uv}}$ sau $c(u,v)$ ${\ displaystyle c (u, v)}$ ${\ displaystyle c (u, v)}$ . Reprezintă debitul maxim care poate trece printr-un arc.

Definiție. Valoarea fluxului constă din:

|f|=\sum \nolimits _{v\in V}f_{sv},

{\ displaystyle | f | = \ sum \ nolimits _ {v \ in V} f_ {sv},}

{\ displaystyle | f | = \ sum \ nolimits _ {v \ in V} f_ {sv},}

și reprezintă cantitatea de curgere de la sursă la fântână.

Tăiere minimă

Definiție. Un sf. Tăiat $C=(S,T)$ ${\ displaystyle C = (S, T)}$ ${\ displaystyle C = (S, T)}$ este partiția lui V astfel încât $s\in S$ ${\ displaystyle s \ în S}$ $s \ în S$ Și $t\in T$ ${\ displaystyle t \ in T}$ $t \ in T$ . Setul tăiat de C este:

\{(u,v)\in E\ :\ u\in S,v\in T\}.

{\ displaystyle \ {(u, v) \ in E \: \ u \ in S, v \ in T \}.}

{\ displaystyle \ {(u, v) \ in E \: \ u \ in S, v \ in T \}.}

Rețineți că, dacă marginile lui C au fost eliminate, | f | = 0.

Definiție. Capacitatea unui punct tăiat este definită ca

c(S,T)=\sum \nolimits _{(u,v)\in S\times T}c_{uv}=\sum \nolimits _{(i,j)\in E}c_{ij}d_{ij},

{\ displaystyle c (S, T) = \ sum \ nolimits _ {(u, v) \ in S \ times T} c_ {uv} = \ sum \ nolimits _ {(i, j) \ in E} c_ { ij} d_ {ij},}

{\ displaystyle c (S, T) = \ sum \ nolimits _ {(u, v) \ in S \ times T} c_ {uv} = \ sum \ nolimits _ {(i, j) \ in E} c_ { ij} d_ {ij},}

unde este $d_{ij}=1$ ${\ displaystyle d_ {ij} = 1}$ ${\ displaystyle d_ {ij} = 1}$ de sine $i\in S$ ${\ displaystyle i \ in S}$ $i \ în S$ Și $j\in T$ ${\ displaystyle j \ in T}$ ${\ displaystyle j \ in T}$ , 0 altfel.

Problemă minimă de tăiere. Determinați S și T astfel încât capacitatea de tăiere st să fie minimă.

Formularea teoremei

Valoarea maximă a unui debit st este egală cu capacitatea minimă dintre toate tăieturile de st.

Demonstrație

Aplicații

Notă

^ P. Elias, A. Feinstein și CE Shannon, O notă privind fluxul maxim printr-o rețea , IRE. Tranzacții privind teoria informației, 2, 4 (1956), 117-119

Bibliografie

( EN ) Jon Kleinberg, Éva Tardos, Algorithm Design , Addison-Wesley, 2005, ISBN 978-0-321-29535-4 .

Elemente conexe

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

[1] P. Elias, A. Feinstein și CE Shannon, O notă privind fluxul maxim printr-o rețea , IRE. Tranzacții privind teoria informației, 2, 4 (1956), 117-119

[1]