Problemi di reti di flusso

• Reti
• Problemi di flusso
• Vincoli dei problemi di flusso
• Problema del flusso di costo minimo (MCF)
• Rilassare alcune assunzioni

Problema del flusso massimo

Vediamo prima il problema di flusso massimo perché è più semplice e ci da modo di avere una base per affrontare il problema del flusso di costo minimo.

• Definire il problema
• Massimo flusso e MCF
• Tagli
• Grafi residui
• Cammini aumentanti
• Algoritmo FordFulkerson
• Algoritmo EdmondsKarp
• Algoritmo GoldbergTarjan

Problema del flusso di costo minimo

• Nozioni e risultati preliminari (pseudoflusso-sbilanciamento)
• Grafi residui e cammini aumentanti
• Teorema (struttura degli pseudoflussi)