Algoritmo di Ford-Fulkerson
In informatica , l' algoritmo di Ford-Fulkerson è un algoritmo per il problema del flusso massimo , un classico problema di ottimizzazione nella ricerca operativa . È di Lester Randolph Ford junior e DR Fulkerson ed è una variante dell'algoritmo di Busacker e Gowen .
Problema di flusso massimo
Definizione del problema
Questo problema di ottimizzazione può essere rappresentato da un grafico comprendente un ingresso (a sinistra) e un'uscita (a destra). Il flusso rappresenta il flusso dall'input all'output quindi l'uso di questo algoritmo nei problemi di rete. Ci sono molte applicazioni: problemi informatici, stradali, ferroviari, ecc. Vale anche per tutti gli altri problemi di trasferimento come import/export, flussi migratori e demografici, ma anche per flussi puramente digitali come i trasferimenti finanziari. Per dati molto grandi, esistono diversi algoritmi più efficienti per risolvere il problema del flusso massimo .
Esempio di applicazione
Una compagnia di trasporti ha tre centri: uno a Parigi, il secondo a Lione, il terzo a Marsiglia.
Sono possibili tre destinazioni: Polonia, Svezia, Grecia.
Ciascuno dei centri merci ha una capacità di trasporto massima e uno stock iniziale di merci. Allo stesso modo, ogni paese di arrivo ha una domanda massima di importazioni.
L'algoritmo di Ford-Fulkerson consentirà di ottimizzare questi flussi utilizzando uno strumento di modellazione matematica. La struttura sottostante è rappresentata da un grafo orientato il cui vertice sinistro simboleggia il titolo iniziale. Questo è collegato a ciascuno dei primi archi o bordi .
Nel presente esempio, la matrice di adiacenza riporta quindi nella sua prima colonna i valori di detti titoli. Viceversa, alla fine della catena, la matrice associata includerà nella sua ultima colonna le rispettive richieste dei paesi citati. I vertici centrali includeranno le diverse combinazioni di merci massime da punto a punto.
Il problema può essere generalizzato ad una circolazione in una rete (veicoli, fluidi, denaro, ecc.), le quantità matematiche che sostituiscono indistintamente i fatti reali che dovrebbero rappresentare.
Formalizzazione
Rete
Una rete con:
G=(S,A,vs,S,t){\ displaystyle G = (S, A, c, s, t)}![{\ displaystyle G = (S, A, c, s, t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89286d0aefc117b5d005baca65f8076b72750a19)
-
(S,A){\ stile di visualizzazione (S, A)}
un grafo diretto irriflessivo
- una capacità con la convenzione: se il bordo non esiste,vs:A→NON⋆{\ displaystyle c: A \ freccia destra \ mathbb {N} ^ {\ stella}}
(tu,v){\ stile di visualizzazione (u, v)}
vs(tu,v)=0{\ stile di visualizzazione c (u, v) = 0}
- un vertice sorgente s senza archi entranti
- un vertice bene t senza archi uscenti
Assumiamo che non ci sono archi anti-parallelo, vale a dire che non ci sono archi da u a v e da v a u .
Flusso
Il flusso di una rete è una funzione che verifica:
f:S2→R+{\ displaystyle f: S ^ {2} \ freccia destra \ mathbb {R} ^ {+}}![{\ displaystyle f: S ^ {2} \ freccia destra \ mathbb {R} ^ {+}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13672939b1446668c2c8938b88e959eeda5e17df)
- per tutte le vette , abbiamo (tu,v)∈S×S{\ displaystyle (u, v) \ in S \ volte S}
0≤f(tu,v)≤vs(tu,v){\ displaystyle 0 \ leq f (u, v) \ leq c (u, v)}
- per ogni vertice come e : (il flusso in entrata è uguale al flusso in uscita).tu∈S{\ displaystyle u \ in S}
tu≠S{\ displaystyle u \ neq s}
tu≠t{\ displaystyle u \ neq t}
Σv∈Sf(v,tu)=Σw∈Sf(tu,w){\ displaystyle \ sum _ {v \ in S} f (v, u) = \ sum _ {w \ in S} f (u, w)}![{\ displaystyle \ sum _ {v \ in S} f (v, u) = \ sum _ {w \ in S} f (u, w)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1862499f6305987a1cf6b4ca790d836c2c6c18d5)
Il valore di un flusso f è .
|f|=Σv∈Sf(S,v){\ displaystyle | f | = \ sum _ {v \ in S} f (s, v)}![{\ displaystyle | f | = \ sum _ {v \ in S} f (s, v)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/593fd927154700dc7e7e98c17facbbed1a83d38d)
Algoritmo
È un algoritmo iterativo. Ad ogni iterazione, la soluzione corrente è un flusso che soddisfa i vincoli di capacità (è quindi un flusso ammissibile) e l'algoritmo cerca di aumentare il valore di questo flusso. Ciò potrebbe richiedere l'annullamento di scelte sbagliate. Per fare ciò definiamo il grafo residuo di G e di f che indica le possibili modifiche (addizione o cancellazione): si tratta di un grafo pesato dove abbiamo
Rf=(S,Af,rf){\ displaystyle R_ {f} = (S, A_ {f}, r_ {f})}![{\ displaystyle R_ {f} = (S, A_ {f}, r_ {f})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ca90f233776d7a4f38fc545e768b28d858cc3d5)
rf(tu,v)={vs(tu,v)-f(tu,v)Sio (tu,v)∈A(ajotut)f(v,tu)Sio (v,tu)∈A(anonnontulatioonon)0Sionononon {\ displaystyle r_ {f} (u, v) = \ left \ {{\ begin {array} {cl} c (u, v) -f (u, v) & \ mathrm {si} \ (u, v ) \ in A & \ mathrm {(addizione)} \\ f (v, u) & \ mathrm {si} \ (v, u) \ in A & \ mathrm {(cancellazione)} \\ 0 & \ mathrm { altrimenti} \ \ fine {array}} \ destra.}
e .
Af={(tu,v)∈S×S|rf(tu,v)>0}{\ displaystyle A_ {f} = \ {(u, v) \ in S \ volte S | r_ {f} (u, v)> 0 \}}![{\ displaystyle A_ {f} = \ {(u, v) \ in S \ volte S | r_ {f} (u, v)> 0 \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/324453bc6dd1a573aad9cd74c54a91c56345523c)
Pseudo-codice
Entrée Un réseau
G=(S,A,c,s,t){\displaystyle G=(S,A,c,s,t)}![{\displaystyle G=(S,A,c,s,t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89286d0aefc117b5d005baca65f8076b72750a19)
Sortie Un flot maximal
f
Fonction Ford_Fulkerson(
G{\displaystyle G}![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
)
f←{\displaystyle f\leftarrow }![{\displaystyle f\leftarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8098f48409dbd6d0941d61022243255945cc7af)
flot nul
Tant que il y a un chemin simple
γ{\displaystyle \gamma }![\gamma](https://wikimedia.org/api/rest_v1/media/math/render/svg/a223c880b0ce3da8f64ee33c4f0010beee400b1a)
de s à t dans le graphe résiduel
Rf{\displaystyle R_{f}}![R_{f}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eabfb117bfefaaad341b75ad3966e68c90469967)
faire:
Δ=min{rf(u,v):(u,v)∈γ}{\displaystyle \Delta =\min\{r_{f}(u,v):(u,v)\in \gamma \}}![{\displaystyle \Delta =\min\{r_{f}(u,v):(u,v)\in \gamma \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9671540d31c2d5f309afe95db3f28e8db2db2f97)
pour toute arête
(u,v)∈γ{\displaystyle (u,v)\in \gamma }![{\displaystyle (u,v)\in \gamma }](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a71cf3a6bffac0f7f7b4333b0ad5bd4078681f4)
si
(u,v)∈A{\displaystyle (u,v)\in A}![{\displaystyle (u,v)\in A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a0f785aaf5da940e8f5dabe771743e3c907ca03)
:
f(u,v):=f(u,v)+Δ{\displaystyle f(u,v):=f(u,v)+\Delta }![{\displaystyle f(u,v):=f(u,v)+\Delta }](https://wikimedia.org/api/rest_v1/media/math/render/svg/65670197fcfa03a723aac4c76c9946cacb249448)
sinon :
f(v,u):=f(v,u)−Δ{\displaystyle f(v,u):=f(v,u)-\Delta }![{\displaystyle f(v,u):=f(v,u)-\Delta }](https://wikimedia.org/api/rest_v1/media/math/render/svg/1eb7628c4ac026910b864537e26872ad076339d8)
renvoyer
f
Esempio di esecuzione
Descrizione
|
Grafico (con capacità )
G{\ stile di visualizzazione G}![G](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b) vs{\ stile di visualizzazione c}![vs](https://wikimedia.org/api/rest_v1/media/math/render/svg/86a67b81c2de995bd608d5b2df50cd8cd7d92455) |
Flusso f{\ stile di visualizzazione f}
|
Grafico residuo (con portata residua )
Gf{\ displaystyle G_ {f}}![G_f](https://wikimedia.org/api/rest_v1/media/math/render/svg/86fb9e8d359d1eacb9be564288c4f2f64ce44ab2) rf{\ displaystyle r_ {f}}![{\ displaystyle r_ {f}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c87b228b9a0db910ffa622d7f417de3fa64258a) |
Consideriamo la rete di flusso , costituita dal grafo con quattro vertici e cinque spigoli , la sorgente , il pozzo e la funzione di capacità .
G=(S,A,vs,S,t){\ displaystyle G = (S, A, c, s, t)} (S,A){\ stile di visualizzazione (S, A)} S={S,t,tu,v}{\ displaystyle S = \ {s, t, u, v \}} A={(S,tu),(tu,t),(S,v),(v,t),(tu,v)}{\ displaystyle A = \ {(s, u), (u, t), (s, v), (v, t), (u, v) \}} S∈S{\ displaystyle s \ in S} t∈S{\ stile di visualizzazione t \ in S} vs:A→R≥0{\ displaystyle c \ due punti A \ a \ mathbb {R} _ {\ geq 0}}![{\ displaystyle c \ due punti A \ a \ mathbb {R} _ {\ geq 0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f134decb34fe181743758ac5b9c82a7a88a50515) Iniziamo con il flusso vuoto che assegna il valore a ciascun bordo. Inizialmente, il grafico residuo e le capacità residue corrispondono poi esattamente alla rete con le capacità .
f{\ stile di visualizzazione f} 0{\ stile di visualizzazione 0} Gf{\ displaystyle G_ {f}} rf{\ displaystyle r_ {f}} G{\ stile di visualizzazione G} vs{\ stile di visualizzazione c}![vs](https://wikimedia.org/api/rest_v1/media/math/render/svg/86a67b81c2de995bd608d5b2df50cd8cd7d92455)
|
e∈S{\ displaystyle e \ in S}
|
vs(e){\ stile di visualizzazione c (e)}
|
(s, tu)
|
4
|
(u, t)
|
1
|
(s, v)
|
2
|
(v, t)
|
6
|
(u, v)
|
3
|
|
e∈S{\ displaystyle e \ in S}
|
f(e){\ stile di visualizzazione f (e)}
|
(s, tu)
|
0
|
(u, t)
|
0
|
(s, v)
|
0
|
(v, t)
|
0
|
(u, v)
|
0
|
|
e∈S{\ displaystyle e \ in S}
|
rf(e){\ displaystyle r_ {f} (e)}
|
rf(e←){\ displaystyle r_ {f} ({\ overleftarrow {e}})}
|
(s, tu)
|
4
|
|
(u, t)
|
1
|
|
(s, v)
|
2
|
|
(v, t)
|
6
|
|
(u, v)
|
3
|
|
|
Descrizione
|
Percorso di miglioramento (con capacità residue )
γ{\ displaystyle \ gamma}![\gamma](https://wikimedia.org/api/rest_v1/media/math/render/svg/a223c880b0ce3da8f64ee33c4f0010beee400b1a) rf{\ displaystyle r_ {f}}![{\ displaystyle r_ {f}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c87b228b9a0db910ffa622d7f417de3fa64258a) |
Flusso f{\ stile di visualizzazione f}
|
Grafico residuo risultante (con nuove capacità residue )
Gf{\ displaystyle G_ {f}}![G_f](https://wikimedia.org/api/rest_v1/media/math/render/svg/86fb9e8d359d1eacb9be564288c4f2f64ce44ab2) rf{\ displaystyle r_ {f}}![{\ displaystyle r_ {f}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c87b228b9a0db910ffa622d7f417de3fa64258a) |
Supponiamo che l'algoritmo scelga prima il percorso (blu). Lungo questo percorso, il flusso può essere aumentato al massimo di poiché il bordo è limitante ( ). Ciò si traduce in un nuovo flusso (che chiameremo sempre ) con .
γ=((S,tu),(tu,v),(v,t)){\ displaystyle \ gamma = \ sinistra ((s, u), (u, v), (v, t) \ destra)} 3{\ stile di visualizzazione 3} (tu,v){\ stile di visualizzazione (u, v)} rf((tu,v))=3{\ displaystyle r_ {f} ((u, v)) = 3} f{\ stile di visualizzazione f} f((S,tu))=f((tu,v))=f((v,t))=3{\ displaystyle f ((s, u)) = f ((u, v)) = f ((v, t)) = 3}![{\ displaystyle f ((s, u)) = f ((u, v)) = f ((v, t)) = 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/743924b731c2bc33b294d6198fba0ebe82ab3b91) La cresta ha una capacità di . È usato nel diluvio: . Nel grafico residuo, la sua capacità residua sarà quindi . Allo stesso modo e .
(S,tu){\ stile di visualizzazione (s, u)} vs((S,tu))=4{\ stile di visualizzazione c ((s, u)) = 4} f((S,tu))=3{\ stile di visualizzazione f ((s, u)) = 3} rf((S,tu))=vs((S,tu))-f((S,tu))=1{\ displaystyle r_ {f} ((s, u)) = c ((s, u)) - f ((s, u)) = 1} rf((tu,v))=vs((tu,v))-f((tu,v))=3-3=0{\ displaystyle r_ {f} ((u, v)) = c ((u, v)) - f ((u, v)) = 3-3 = 0} rf((v,t))=vs((v,t))-f((v,t))=6-3=3{\ displaystyle r_ {f} ((v, t)) = c ((v, t)) - f ((v, t)) = 6-3 = 3}![{\ displaystyle r_ {f} ((v, t)) = c ((v, t)) - f ((v, t)) = 6-3 = 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8ae20d840a832b285620c5649497e9f72fd77f5)
I tre fronti sono strettamente positivi nel flusso. Questi pesi in acqua potrebbero non essere i più ottimali. I nuovi bordi posteriori (in rosso) nel grafico residuo indicano quindi il fatto che possiamo sempre ridurre il flusso su questi bordi.
(S,tu),(tu,v),(v,t){\ displaystyle (s, u), (u, v), (v, t)} (t,v),(v,tu),(tu,S){\ displaystyle (t, v), (v, u), (u, s)}![{\ displaystyle (t, v), (v, u), (u, s)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/572c4af63f694f1160340bff4d0082e9b592365e)
|
|
e∈S{\ displaystyle e \ in S}
|
f(e){\ stile di visualizzazione f (e)}
|
(s, tu)
|
3
|
(u, t)
|
0
|
(s, v)
|
0
|
(v, t)
|
3
|
(u, v)
|
3
|
|
e∈S{\ displaystyle e \ in S}
|
rf(e){\ displaystyle r_ {f} (e)}
|
rf(e←){\ displaystyle r_ {f} ({\ overleftarrow {e}})}
|
(s, tu)
|
1
|
3
|
(u, t)
|
1
|
|
(s, v)
|
2
|
|
(v, t)
|
3
|
3
|
(u, v)
|
|
3
|
|
Supponiamo che l'algoritmo selezioni il percorso di miglioramento . L'aumento massimo della produttività è limitato dalla capacità residua . Per la prima volta, attraversiamo un bordo posteriore ( ). Mentre il flusso f aumenta di 1 lungo i bordi (s, v) e (u, t) , diminuisce di 1 lungo (u, v) .
γ=((S,v),(v,tu),(tu,t)){\ displaystyle \ gamma = ((s, v), (v, u), (u, t))} rf((tu,t))=vs((tu,t))-f((tu,t))=1-0=1{\ displaystyle r_ {f} ((u, t)) = c ((u, t)) - f ((u, t)) = 1-0 = 1} (v,tu){\ stile di visualizzazione (v, u)}![{\ stile di visualizzazione (v, u)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e186c23c37b50f8ca8c2ad5624a3f6fd3808a2f7) Si può notare che le portate residue dei bordi posteriori sono sempre uguali ai pesi nel flusso.
|
|
e∈S{\ displaystyle e \ in S}
|
f(e){\ stile di visualizzazione f (e)}
|
(s, tu)
|
3
|
(u, t)
|
1
|
(s, v)
|
1
|
(v, t)
|
3
|
(u, v)
|
2
|
|
e∈S{\ displaystyle e \ in S}
|
rf(e){\ displaystyle r_ {f} (e)}
|
rf(e←){\ displaystyle r_ {f} ({\ overleftarrow {e}})}
|
conoscere
|
1
|
3
|
(u, t)
|
|
1
|
(s, v)
|
1
|
1
|
(v, t)
|
3
|
3
|
(u, v)
|
1
|
2
|
|
Supponiamo che l'algoritmo scelga di nuovo il percorso . Questa volta, il flusso lungo il percorso può essere aumentato solo di 1. Ciò corrisponde esattamente alla quantità di cui abbiamo diminuito (u, v) nel passaggio precedente. In effetti, l'algoritmo può fare molto avanti e indietro.
γ=((S,tu),(tu,v),(v,t)){\ displaystyle \ gamma = \ sinistra ((s, u), (u, v), (v, t) \ destra)}![{\ displaystyle \ gamma = \ sinistra ((s, u), (u, v), (v, t) \ destra)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6c4a3b5f16b2afe723bbe4d86cc3655c58a7ebf) |
|
e∈S{\ displaystyle e \ in S}
|
f(e){\ stile di visualizzazione f (e)}
|
conoscere
|
4
|
(u, t)
|
1
|
(s, v)
|
1
|
(v, t)
|
4
|
(u, v)
|
3
|
|
e∈S{\ displaystyle e \ in S}
|
rf(e){\ displaystyle r_ {f} (e)}
|
rf(e←){\ displaystyle r_ {f} ({\ overleftarrow {e}})}
|
conoscere
|
|
4
|
(u, t)
|
|
1
|
(s, v)
|
1
|
1
|
(v, t)
|
2
|
4
|
(u, v)
|
|
3
|
|
Qui solo il percorso è possibile. Questo quindi aumenta il flusso di 1. Il flusso ha quindi un valore di . I bordi in uscita della sorgente sono completamente utilizzati, quindi questo flusso è un flusso massimo. Il taglio a livello di (s, u) e (s, v) è quindi un taglio minimo . Rispettiamo quindi il teorema flow-max / cut-min che afferma che un flusso massimo ha lo stesso valore di un taglio minimo.
γ=((S,v),(v,t)){\ displaystyle \ gamma = ((s, v), (v, t))} f((S,tu))+f((S,v))=6{\ stile di visualizzazione f ((s, u)) + f ((s, v)) = 6}![{\ stile di visualizzazione f ((s, u)) + f ((s, v)) = 6}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7556d682be73e93f96b6f01eeb6de671d2d1850) L'algoritmo quindi termina perché non esiste alcun cammino da s a t nel grafo residuo ottenuto. Abbiamo quindi ottenuto un flusso massimo.
|
|
e∈S{\ displaystyle e \ in S}
|
f(e){\ stile di visualizzazione f (e)}
|
conoscere
|
4
|
(u, t)
|
1
|
(s, v)
|
2
|
(v, t)
|
5
|
(u, v)
|
3
|
|
e∈S{\ displaystyle e \ in S}
|
rf(e){\ displaystyle r_ {f} (e)}
|
rf(e←){\ displaystyle r_ {f} ({\ overleftarrow {e}})}
|
conoscere
|
|
4
|
(u, t)
|
|
1
|
(s, v)
|
|
2
|
(v, t)
|
1
|
5
|
(u, v)
|
|
3
|
|
Proprietà dell'algoritmo
Complessità
Il flusso massimo viene raggiunto quando non è possibile trovare un percorso di ulteriore miglioramento. Tuttavia, non c'è certezza che questa situazione verrà raggiunta, ma la risposta sarà corretta se l'algoritmo termina. Nel caso in cui l'algoritmo funzioni indefinitamente, il flusso potrebbe anche non convergere verso il flusso massimo. Tuttavia, questa situazione si verifica solo con valori di flusso irrazionali. Quando le capacità sono intere, il tempo di esecuzione dell'algoritmo di Ford-Fulkerson è limitato da (vedi notazioni di Landau ), dove è il numero di archi nel reticolo di flusso ed è il valore del flusso massimo. Questo perché ogni percorso crescente può essere trovato da e aumenta la velocità di un importo intero di almeno con un limite superiore.
oh(Af){\ stile di visualizzazione O (Af)}
A{\ stile di visualizzazione A}
f{\ stile di visualizzazione f}
oh(A){\ stile di visualizzazione O (A)}
1{\ stile di visualizzazione 1}
f{\ stile di visualizzazione f}![f](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61)
Una variante dell'algoritmo di Ford-Fulkerson con terminazione garantita e un tempo di esecuzione indipendente dal valore di flusso massimo è l' algoritmo di Edmonds-Karp , che ha una complessità temporale di .
oh(SA2){\ stile di visualizzazione O (SA ^ {2})}![{\ stile di visualizzazione O (SA ^ {2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/392f5b3548c7bd8239b31767d3282a95f5fe581b)
Cessazione
Se le capacità degli archi sono intere, l'algoritmo termina.
Ciò può essere dimostrato assurdamente, assumendo che l'algoritmo non termini. Considerando la sequenza dei flussi calcolati, si distinguono diverse proprietà:
- Il resto è in forte aumento
- Viene incrementato del valore della portata massima
- Lei è pieno valore
Tutta questa sequenza è infinita, aumentata e strettamente crescente, il che è assurdo.
Note e riferimenti
-
(in) LR Ford e DR Fulkerson , " Flusso massimo attraverso una rete " , Canadian Journal of Mathematics , vol. 8, 1956 / ed., p. 399–404 ( ISSN 0008-414X e 1496-4279 , DOI 10.4153 / CJM-1956-045-5 , lettura online , accesso 29 maggio 2021 )
Vedi anche
link esterno
Bibliografia
-
Un semplice algoritmo per trovare i flussi di rete massimi e un'applicazione al problema di Hitchock (FORD LR, FULKERSON DR), Rand Report Rand Corporation, Santa Monica,dicembre 1955.
- Lester R. Ford e Delbert R. Fulkerson , " Flusso massimo attraverso una rete " , rivista canadese di matematica , vol. 8, n . 3,1956, pag. 399-404
-
Il problema del trasbordo (ORDEN A.), Management Science 2, 1956.
-
Sulla deficienza di una rete infinita (BERGE C.), Atti dell'Accademia delle Scienze 245, 1957.
-
Invito alla ricerca operativa (KAUFMANN A., FAURE R.) Dunod Entreprise, 1979.
-
Contributo della teoria dei grafi allo studio dei problemi di scheduling (ROY B.) International Congress of Operations Research, 1960.
- Lester Randolph Ford e Delbert Ray Fulkerson , Flussi nelle reti , Princeton, NJ, Princeton University Press,1962
- Ravindra K. Ajuha , Thomas L. Magnanti e James B. Orlin , Flussi di rete - teoria, algoritmi e applicazioni , Prentice Hall,1993
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein , Introduzione agli algoritmi , MIT Press,2009
- Jon Kleinberg ed Eva Tardos , Progettazione di algoritmi , Pearson Education India,2006
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">