Introduzione
I teoremi approximate max-flow min-cut sono proposizioni matematiche nella teoria del flusso di rete .Teorema approssimativo max-flow min-cut riguardano la relazione tra portata massima (“max-flow”) e taglio minimo (“min-cut”) in un problema di flusso multicommodity . I teoremi hanno consentito lo sviluppo di algoritmi di approssimazione per l’uso nella partizione del grafico e problemi correlati.
Teorema approssimativo del flusso massimo e del taglio minimo
