Flusso massimo¶

5.1 Il problema del flusso massimo

Apri
5.2 Tagli

Apri
5.3 La rete residua

Apri
5.4 Il teorema del taglio minimo del flusso massimo

Apri
5.5 L'algoritmo Ford-Fulkerson

Il numero di aumenti

Apri
5.6 L'algoritmo Edmonds–Karp

Apri
5.7 Applicazioni

Corrispondenza massima in un grafo bipartito · Percorsi arcodisgiunti

Apri

Prerequisiti

Da questo modulo, Capitolo 1 «Grafi»: percorsi orientati, la ricerca in ampiezza e la ricerca in profondità.
Da questo modulo, Capitolo 4 «Modelli di flusso di rete»: conservazione del flusso, flusso attraverso un taglio, modello di flusso a costo minimo e suo intero vertici.
Dal modulo Programmazione lineare, Capitolo 15 «La geometria di Programmazione lineare»: una funzione lineare raggiunge il suo massimo su un poliedro limitato non vuoto.

Obiettivi

Alla fine di questo capitolo sarai in grado di:

formula il problema del flusso massimo e scrive il suo modello LP;
calcola la capacità di un taglio \(s\)–\(t\) e utilizza i tagli come limite superiore del valore di ogni flusso;
costruisce la rete residua di un flusso, trova un percorso aumentante e il suo collo di bottiglia e aumenta il flusso;
dimostrare il teorema del taglio minimo del flusso massimo e il teorema dell'integralità;
esegue gli algoritmi Ford–Fulkerson e Edmonds–Karp, legge un taglio minimo alla fermata e fornisce i propri dati tempi di esecuzione;
calcola una corrispondenza massima in un grafo bipartito e un insieme massimo di percorsi arcodisgiunti come flussi massimi.

Avanti: 5.1 Il problema del flusso massimo

Esercizi su questo capitolo: Flusso massimo