Réseau de 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
F pour passer en plein écran ou O pour afficher la vue d'ensemble.
Versions sans animation, plein écran, imprimable.
Exercices
Ford-Fulkerson
Appliquer l'algorithme de Ford-Fulkerson et trouver la coupe minimum sur les graphes suivants :
Solution
Flot maximum : 5 + 5 + 5 = 15
Coupe minimum : {S, U, V} / {T} ou {S} / {T, U, V}
Solution
Flot maximum : 2 + 3 + 2 = 7
Coupe minimum : {S, A} / {B, C, D, T} ou {S} / {A, B, C, D, T}
Références
- https://fr.wikipedia.org/wiki/R%C3%A9seau_de_flot
- https://fr.wikipedia.org/wiki/Probl%C3%A8me_de_flot_maximum
- https://www.programiz.com/dsa/ford-fulkerson-algorithm
- https://fr.wikipedia.org/wiki/Coupe_(th%C3%A9orie_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%C3%A9or%C3%A8me_flot-max/coupe-min