Chapitre 4 : Problème du flot maximum 1. Définitions Réseau de transport : Un réseau de transport est un graphe U) orienté, sans boucle, où chaque arc est associé à un nombre c(u) O, appelé « capacité » de l’arc u. En outre, un tel réseau vérifie les hypothèses suivante Cl Il existe un seul nœ autres en ont au moi appelé l’entrée du ré II existe également ors p écesseurs, tous les un. c as de successeurs, tous les autres en ont au moins un.
Ce nœud est appelé la sortie du réseau, ou le puits. On note un réseau de transport par R = (X, U, C) où C = {C(uj) / uj Exemple : 7 Fig. 1. Flot : est réalisable s’il satisfait aux conditions suivantes . -o – ( ) c(uj) , – en tout sommet i à m composantes. Ce flot la 1ère loi de Kirchoff est vérifiée (loi de conservation aux nœuds) . est la quantité de flot ou flux sur l’arc j. – En particulier, lesquels on a au moins un arc saturé.
Le flot est complet Arc saturé Premier chemin Deuxième chemin : 2. Le problème de la recherche du flot maximum : Le problème du flat
Le principe : L’idée de Falgorithme de Ford et Fulkerson est de faire passer un flot compatible dans le réseau, le plus évident st le flot nul, puis de Faméliorer jusqu’à ce qu’on obtienne un flot complet. Une chaîne C est dite augmentante si : Pour tout arc u direct de C, c’est-à-dire u C+ : ( ) C(u) . pour tout arc u indirect de C, c’est-à-dire u C- : ( ) Module : Théorie des graphes Chapitre 4 : Problème du PAGF3œFS On augmentera le flot de cette chaîne de 1, on obtient alors le nouveau flot : Énoncé : Données : un 1 -graphe valué Résultat : un flot complet. n flot maximum. (O) Initialisation Marquer un sommet s et poser : C* — ; C (1 ) Soit A l’ensemble des sommets marqués et soit x un sommet de A : Marquer le sommet y successeur de x tel que ( On pose : C FC {Cx, y)} ; A FA (y} D Marquer le sommet y prédécesseur de x tel que ( On pose : C- x)} ; A (y} Quand on ne peut plus marquer, deux cas se présentent : 1. p est marqué aller en (2) 2. p n’est pas marqué, terminé le flot est maximum. (2) On a obtenu une chaîne au mentante C=C+ C- de s à p Pour améliorer le flot on c
