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