Les flots

Calcul du flot maximum dans un graph reliant le puits (t) à la source(s).
Il faut respecter la loi de kirshoff : l’ensemble flux entrant sur un nœud=l’ensemble des flux sortant du même nœud

Algorithme de Ford -Fulkerson

Recherche du flot complet

1. 1. On fait passer un flot au juger
   2. Améliorer le flot jusqu’à ce qu’on ait un flot complet- Flot qui sature suffisamment de relations pour que tout chemin entre source, s et la sortie t comporte au moins un arc saturé.
2. Procédure de marquage
   1. Marquer l ’entrée du réseau (+)
   2. Marquer toute extrémité, j, d ’un arc (i,j) non saturé si origine,i , est marquée (+)
   3. Marquer l ’origine, k, (-) d ’un arc (k, l) transportant un flot non nul si extrémité,l , est marquée
   4. Si on ne peut marquer l ’extrémité, t, sortie du graphe, le flot est maximum
   5. Sinon le flot n ’est pas maximum. Améliorer le flot en respectant les lois de Kirchoff. Retour en 3-1

Dans cette exemple les valeur entre parenthèse représente la valeur maximal, à coté la valeur que l’on fait passé.

Etape 1 :
On fait passé un flot au jugé de pour obtenir sur tous chemin au moins un arc saturé. :
SA : 15, SB : 35, SC : 30, AD : 5 , AF : 15, etc...
toujours en respectant la loi de kirshoff

Vérification :
en partant de S, je peux aller vers A en prenant un arc non saturé puis la seule solution est d’aller vers D car AF est saturé et de D je suis coincé car plus de solution non saturée SB est déjà saturé, donc fini. Enfin je peux prendre l’arc SC de C, je ne peux aller que vers E et la, je suis coincé, donc c’est Ok.

Étape 2 Marquage :

On part de la source S que l’on marque d’un +, puis on va regarder chaque arc partant d’un ’+’ ,
si l’arc n’est pas saturé, alors l’extrémité est aussi marquée d’un ’+’ SC n’est pas saturé, donc je marque le point C d’un signe ’+’. je pouvais également marquer A d’un + si l’arc est saturé, je le marque d’un signe ’-’ , donc, je marque B d’un ’-’ car SB est saturé.
Je part de C, ou je peut allé à E ou F. F est saturé, on peut le marqué de ’-’, mais pas intéressant, E n’est pas saturé, on le marque de ’+’. Depuis E, je ne peux pas aller direct a l’arrivée car c’est saturé, mon objectif est d’arriver a la fin T.
Par contre, je peux reculer vers B car il est marqué de ’-’ et de B, je peux aller vers F car l’arc n’est pas saturé, donc je peux marque F d’un ’+’. Enfin, de F, je peux rejoindre le puits T car FT n’est pas saturé. J’ai donc identifié un chemin que je peux optimiser le chemin est le suivant : SCEBFT

On regarde la capacité d’optimisation sur chaque arc, quand on avance : les noeuds marqués d’un +
La marge est la différence entre ce qui passe réellement et la capacité. Vous avez sur SC, vous avez une capacité de 40 mais seulement 30 passent, donc vous avez une marge de 10.
Quand vous allez vers un nœud marqué ’-’, vous avez une capacité de revenir à zero, donc la marge est entre 0 et ce qui passe réellement. Sur la chaine à améliorer, le minimum est de 5 entre B et F, donc on va ajouter 5 à chaque chemin + et retirer 5 à chaque chemin marqué - les nouvelles valeurs sont sur le second graphe ci dessus

1. Flot amélioré
2. Marquage sorite : impossible
   => flot maximal=85

Sommet marqués 1= S,A,B,C,D,E
Sommet non marqués : A*=T,F

Capacité de la coupe C séparant les sommets marqués des sommets non marqués =20+30+10+5+20=85

Le flot est optimal quelle est sa valeur ?
La somme de tous les flux qui arrivent en T
soit : 20 + 30 + 35 =85 qui correspond au flot maximal
Au lieu d’optimiser en partant de C, nous aurions pu le faire en passant par A
SADBFT est aussi un chemin qui permet d’optimiser on aurait pu l’améliorer seulement de 5 aussi.