Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Probleme du flot Problème du Flot Dans ce chapitre le graphe est supposé orienté I Position du problème Soit G X U un graphe et l ? application c U R U ? u c u capacité de l ? arc u Soient S et P deux sommets et ur PS appelé arc de retour Le problème de r

Problème du Flot Dans ce chapitre le graphe est supposé orienté I Position du problème Soit G X U un graphe et l ? application c U R U ? u c u capacité de l ? arc u Soient S et P deux sommets et ur PS appelé arc de retour Le problème de recherche d ? un ot maximum de S à P dans R X U c revient à chercher un vecteur f ?? Rm m U tel que i f est un ot sur R U ur ii f u ? c u ?? u ?? U iii f ur maximum Si A est la matrice d ? incidence aux arcs associée à G alors A f F f ? c f ? f ur Z Max Exemple a S P b ur f Sa f Sb ?? f ur f ab f aP ?? f Sa f bP ?? f Sb ?? f ab f ur ?? f bP ?? f aP f Sa ? f ? f Sb ? f ab ? f aP ? f bP ? f ur Z Max II Algorithme Ford Fulkerson FF Principe de l ? algorithme Initialisation f u ?? u ??U L ? algorithme se base sur deux idées ère idée chemin augmentant de S à P le réel à côté de chaque arc est sa capacité CS a b c d e P f g ur C S a b c d e P C S f c d g P Application l ? exemple er chemin S a b P ème chemin S b P f ur f ur ème idée cha? ne augmentante de S à P on a porté à côté de chaque arc u le couple f u c u S a b c d e P C Sa ab cd eP C - cb ed ur Min - - - - Min Application l ? exemple C Sb bP Min - - C- ab f ur Algorithme FLOTMAX données X U I T ur s p c résultats f Y f u pour tout u ?? U Itérer MARQUAGE X U I T ur s p c f Y A Arrêt p ?? Y x p C ur C - ? Tantque x ?? s faire u A x si x T u alors C C U u x I u Sinon dans ce cas x I u C - C - U u x T u Finsi Fintantque f u si u ?? C f u f u - si u ?? C - f u si u ?? C U C - Finitérer Finalgo CAlgorithme MARQUAGE données X U I T ur s p c f résultats Y A MARK est une variable logique qui vaut FAUX lorsqu ? on ne peut plus marquer de nouveaux sommets Y s MARK VRAI Tant que p ?? Y et MARK faire Si il existe u xy avec x ?? Y y