Flot

Objectifs

• Définir le problème du flot maximum
• Appliquer l'algorithme de Ford-Fulkerson
• Définir une coupe dans un réseau de flot
• Connaître le théorème flot-max/coupe-min
• Trouver la coupe minimum d'un réseau de flot

Cours

Appuyez sur F pour passer en plein écran.
Version plein écran ou imprimable.

Exercices

Exercice : Ford-Fulkerson

Appliquer l'algorithme de Ford-Fulkerson et trouver la coupe minimum sur les graphes suivants :

Correction

Flot maximum : 5 + 5 + 5 = 15

Coupe minimum : {S, U, V} / {T} ou {S} / {T, U, V}

Correction

Flot maximum : 2 + 3 + 2 = 7

Coupe minimum : {S, A} / {B, C, D, T} ou {S} / {A, B, C, D, T}

Sources

• https://fr.wikipedia.org/wiki/Réseau_de_flot
• https://fr.wikipedia.org/wiki/Problème_de_flot_maximum
• https://www.programiz.com/dsa/ford-fulkerson-algorithm
• https://fr.wikipedia.org/wiki/Coupe_(théorie_des_graphes)
• https://www.hackerearth.com/practice/algorithms/graphs/min-cut/tutorial/
• https://fr.wikipedia.org/wiki/Coupe_minimum
• https://fr.wikipedia.org/wiki/Théorème_flot-max/coupe-min