Vidéo (11 min): Application de Ford et Fulkerson sur un exemple


Cette vidéo suppose que vous avez déjà fait un effort de lecture du polycopié et notamment des définitions de réseaux de flot, flot, graphe résiduel, chemin augmentants.

Vous pouvez démarrer l'algorithme de Ford et Fulkerson de n'importe quel (s,t)-flot réalisable (notamment le flot nul), c'est ce que nous faisons sur cet exemple en démarrant avec un flot de valeur 19.


Attention la notion d'arc en avant et d'arc en arrière concerne le graphe résiduel pas le graphe d'origine. Par exemple le flot de valeur 4 sur l'arc (b,c) engendre dans le graphe résiduel, un arc en avant (b,c) de capacité 5 et un arc en arrière (c,b) de capacité 4.

Contacts: Nicolas Catusse et Hadrien Cambazard

Last modified: Thursday, 12 September 2019, 9:48 AM