Title: ~Archivio / Ottimizzazione Combinatoria / 04 - Algoritmi Max Flow Problem

Q: Trasformazioni Equivalenti
A: Nei problemi di MCF si possono fare alcune assunzioni che ne semplificano la descrizione e l'analisi, costruendo un instanza MCF a quella data:

Problema di flusso massimo

Def: Taglio di una rete

Q: Def: Tagli proprietà, flusso del taglio, e capacità del taglio (e dimostrazione)
A: primo passo utilizza, il vincolo del problema (che dev'essere per forza vero), poi essendo che i nodi intermedi hanno l'uscita uguale all'entrate, shifta i nodi in avanti, shiftando i nodi in avanti tutti i nodi intermedi li conti due volte e quindi gli togli e rimangono solo i nodi di frontiera

Def: Grafi Residui

Def:Cammini Aumentati, archi concordi, discordi , capacità di un cammino aumentatnte

Correttezza Ford-Fulkerson solo teoremi

Teorema: Max-Flow Min-Cut  con Dim