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.

un autre exemple d'application:    • Flot maximum: Application de l'algori...  
comprendre la notion de coupe dans un réseau de flot:    • 2- Algorithme de Ford de Fulkerson: l...  
comprendre l'optimalité de l'algorithme:    • 3- Algorithme de Ford et Fulkerson: I...  

Sur notre plateforme:
Le cours de RO : https://moodle.caseine.org/course/ind...
Des quiz: https://moodle.caseine.org/mod/quiz/v...

Si vous n'êtes pas un étudiant de l'INP/UGA, pour vous connecter, choisir "Connexion Autre" et sélectionner votre université.


Contacts: Nicolas Catusse et Hadrien Cambazard