1. Rete residua:
Immagina di avere una rete con una sorgente (i), un lavandino (T) e bordi con capacità che rappresentano il flusso massimo consentito attraverso ciascun bordo. Una * rete residua * è una rappresentazione della capacità rimanente nella rete * dopo * una certa quantità di flusso è già stata spinta attraverso di essa.
Ecco come funziona:
* bordi in avanti: Per ogni bordo (u, v) nella rete originale con capacità C (u, v) e flusso di corrente f (u, v), la rete residua include un corrispondente * bordo in avanti * (u, v) con capacità c f (u, v) =c (u, v) - f (u, v). Ciò rappresenta la capacità rimanente disponibile sul bordo.
* bordi all'indietro: La parte cruciale è che la rete residua * *include anche *bordi all'indietro *. Per ogni bordo (u, v) nella rete originale con il flusso di corrente f (u, v), la rete residua contiene un bordo all'indietro (v, u) con capacità C f (v, u) =f (u, v). Ciò rappresenta la possibilità di * spingere indietro il flusso * lungo il bordo, annullando efficacemente parte del flusso già inviato. La capacità del bordo all'indietro è uguale al flusso attualmente sul bordo in avanti, perché puoi solo respingere la quantità di flusso che è già lì.
In sostanza, la rete residua mostra la capacità disponibile per le modifiche al flusso. Adatta dinamicamente poiché il flusso viene spinto attraverso la rete. Trovare un percorso di aumento (spiegato di seguito) nella rete residua significa che c'è ancora il potenziale per aumentare il flusso totale dalla sorgente al lavandino.
2. Percorso di aumento:
Un * percorso di aumento * è un percorso semplice (nessun vertico ripetuto) nella rete residua che conduce dalla sorgente (e) al lavandino (t). Fondamentalmente, rappresenta un modo per aumentare il flusso totale attraverso la rete.
La quantità in base al quale il flusso può essere aumentato lungo il percorso di aumento è determinata dalla *capacità di collo di bottiglia *. Questa è la capacità residua minima tra tutti i bordi nel percorso di aumento.
Per esempio:
Se un percorso di aumento ha bordi con capacità residue di 5, 3 e 7, la capacità di collo di bottiglia è 3. Possiamo quindi aumentare il flusso lungo questo percorso di 3 unità. Questo processo aggiorna il flusso nella rete originale e successivamente modifica la rete residua.
relazione tra reti residui e percorsi di aumento:
Il nucleo di molti algoritmi a flusso massimo (come Ford-Fulkerson) è iterativamente:
1. Trova un percorso di aumento nell'attuale rete residua.
2. Aumenta il flusso Lungo quel percorso per la capacità di collo di bottiglia.
3. Aggiorna la rete residua per riflettere il cambiamento nel flusso.
Questo processo continua fino a quando non si trovano più percorsi di aumento nella rete residua, a quel punto il flusso massimo è stato raggiunto. Il teorema tagliato a min-flusso massimo lo garantisce.
networking © www.354353.com