cours_ING2_graphe_fl.. - ECE

1.
2. Recherche du flot maximum (version mise a jour) 2
Définitions 2
Réseau de transport 2
Flot 2
Flot compatible 3
Flot complet 3
Problème du flot maximum 3
Algorithme de Ford-Fulkerson, chaîne augmentante 4
Exercice corrigé 6
Algorithme de Ford-Fulkerson, graphe d'écart 7
1. RECHERCHE DU FLOT MAXIMUM

1.1 DEFINITIONS
[pic]
Les flots permettent de modéliser une très large classe de problèmes. Leur
interprétation correspond à la circulation de flux physiques sur un réseau
: distribution électrique, réseau d'adduction, acheminement de paquets sur
Internet, ... Il s'agit d'acheminer la plus grande quantité possible de
matière entre une source s et une destination t. Les liens permettant
d'acheminer les flux ont une capacité limitée, et il n'y a ni perte ni
création de matière lors de l'acheminement : pour chaque n?ud intermédiaire
du réseau, le flux entrant (ce qui arrive) doit être égal au flux sortant
(ce qui repart).
Réseau de transport
[pic]
[pic]
Un réseau de transport est un graphe orienté, connexe, sans boucle et
valué, où chaque arc est associé à un nombre c(u) [pic] 0, appelé
"capacité" de l'arc u. En outre, un tel réseau vérifie les hypothèses
suivantes :
. Il existe un seul n?ud s arbitraire appelé l'entrée du réseau, ou la
source.
. Il existe également un seul n?ud t arbitraire appelé la sortie du
réseau, ou le puits.
. Entre les n?uds s et t, il peut exister des n?uds intermédiaires.
Un exemple de réseau.
Le réseau comporte 5 noeuds intermédiaires. La capacité de l'arc (c,e) est
de 2, celle de l'arc (e,t) est de 4 |[pic] | |
|Nous pouvons supposer que tous les arcs (x,y) entre 2 sommets sont présents | |
|dans le réseau. Si un arc est absent, il est en effet possible de le | |
|rajouter en lui attribuant une capacité nulle sans changer le problème du | |
|flot maximum. Seuls les arcs de capacité non nulle seront représentés sur | |
|les exemples. | |
| | |
Flot
[pic]
Un flot f dans un réseau de transport est une fonction qui associe à chaque
arc u une quantité f(u) qui représente la quantité de flot qui passe par
cet arc, en provenance de la source et en destination du puits. [pic]
La somme [pic](x) = [pic]F(y,x) est le flot entrant au sommet x
La somme [pic](x) =[pic]F(x,y) est le flot sortant du sommet x
La valeur F(x) d'un flot est définie comme le flot sortant moins le flot
entrant en x : F(x) = [pic](x) - [pic](x) Un flot doit respecter la règle suivante : la somme des quantités de flot
sur les arcs entrants [pic](x) dans un n?ud x, autre que s et t, doit être
égale à la somme des quantités de flot sur les arcs sortants [pic](x) de ce
même n?ud x. Son flot F(x) est donc nul. Un flot vérifie localement une loi
de conservation analogue aux lois
de Kirchhoff en électricité.
Loi de Kirchhoff :
La somme des intensités qui arrivent au n?ud est égale à la somme des
intensités qui en repartent.
[pic](x) = I1 + I3
[pic](x) = I2 + I4
[pic](x) = [pic](x) ce qui donne F(x) = [pic](x) - [pic](x) = 0 Exemple : Un exemple de flot sur notre réseau.
Le flot entrant en b a une valeur de 3.
La valeur du flot est définie comme le flux net sortant de s ou entrant
dans t.
Sur cet exemple le flot a une valeur de 2.
Flot compatible

[pic]
Un flot f est compatible avec un réseau si pour tout arc u,
0 [pic] f(u) [pic] c(u). Autrement dit, pour chaque arc, le flot qui le
traverse ne doit pas dépasser la capacité de l'arc.
Flot complet

[pic]
Un flot f est complet si pour tout chemin allant de la source au puits, il
y a au moins un arc saturé, i.e. le flot qui le traverse est égal à la
capacité de l'arc.
1.2 PROBLEME DU FLOT MAXIMUM

[pic]
Connaissant les capacités des arcs d'un réseau de transport, le problème du
flot maximum consiste à trouver quelle est la quantité maximum de flot qui
peut circuler de la source au puits. L'algorithme le plus connu pour
résoudre ce problème est celui de Ford et Fulkerson. Nous verrons deux
approches pour cette méthode. La première est basée sur la recherche d'une
chaîne dans le réseau alors que la seconde construit un graphe "d'écart"
dans lequel on recherche un chemin. [pic]
Tout flot maximum est complet mais un flot complet n'est pas forcément
maximum. [pic]
La valeur du flot maximum correspond au flux net partant de s, c'est à dire
le flot sortant moins le flot entrant de s. La valeur du flot peut être
définie de manière équivalente comme le flux net arrivant à t, c'est à dire
le flot entrant moins le flot sortant de t. En effet pour tout n?ud intermédiaire x, le flot entrant étant égal au flot
sortant, on a :
[pic][pic](x) = [pic][pic](x)
ce qui se réécrit : [pic]( F(s,x) + F(t,x) + [pic]F(y,x) ) = [pic]( F(x,s)
+ F(x,t) + [pic]F(x,y) ) Le dernier terme de part et d'autre de l'égalité est le même, donc on a
[pic](s) +[pic](t) = [pic](s) +[pic](t), le flux net sortant de s est
effectivement égale au flux net entrant en t, ce qui correspond bien à
notre problème d'acheminement de flux de s à t. Le problème du Flot Maximum consiste à trouver un flot de valeur maximale
sur le réseau.
ALGORITHME DE FORD-FULKERSON, CHAINE AUGMENTANTE [pic]
On part d'un flot compatible. Le plus évident est le flot nul, i.e. pour
tout arc u, f(u) = 0. Ensuite, on cherche une chaîne reliant la source au
puits telle que son flot peut être augmenté. Si on n'en trouve pas, le
problème est résolu. Sinon, on augmente le flot sur cette chaîne. Ensuite,
on recommence à chercher une chaîne augmentante et ainsi de suite. Une
chaîne augmentante, i.e. une chaîne pour laquelle le flot peut être
augmenté est une chaîne pour laquelle les arcs dans le sens direct n'ont
pas atteint leur limite maximum et les arcs en sens indirect ont un flot
non nul qui les traverse. L'augmentation de flot maximum pour une chaîne
est le minimum des écarts entre le flot courant et le flot maximal pour les
arcs directs ou le flot courant pour les arcs indirects. Autrement dit, une
chaîne C est augmentante si:
. pour tout arc u direct, f(u) < c(u),
. pour tout arc u indirect, f(u) > 0.
Le flot f sur cette chaîne C peut être augmenté de:
f(C) = min({c(u) - f(u) | u [pic] C et u sens direct} [pic] {f(u) |
u [pic] C et u sens indirect})
[pic]
Tour arc u sens direct de C sera augmenté de f(C) s'il n'est pas saturé i.e
c(u) ? f(u)
Tour arc u sens indirect de C sera diminué de f(C) si f(u) ? 0 Exemple :
Voici une chaîne augmentante de A à E faisant partie d'un réseau de
transport.
[pic]
Dans cette chaîne, on peut augmenter le flot de:
. 3 entre A et B,
. 2 entre B et C,
. 1 entre C et D,
. 5 entre D et E. On augmentera donc de 1 le flot dans cette chaîne. Ce qui signifie:
. augmenter de 1 le flot entre A et B,
. augmenter de 1 le flot entre B et C,
. diminuer de 1 le flot entre D et C,
. augmenter de 1 le flot entre D et E.
[pic]
On remarque que pour les arcs en sens inverse, augmenter le flot signifie
réduire le flot dans le sens direct. Entre D et C, le flot est réduit de 1
pour permettre l'arrivée d'une unité de flot sur C par B tout en conservant
l'équilibre du noeud. D ayant une unité de trop, son équilibre n'est pas
respecté. C'est pourquoi une unité de flot supplémentaire circule entre D
et E. Algorithme de Ford - Fulkerson de recherche de flot maximal dans un réseau. La mise en oeuvre se fait par marquage des sommets et en gardant chaque
prédécesseur des sommets marqués. Un sommet x est marqué par un couple (x,
Fxy), où x est un sommet déjà marqué, précédent de y, et Fxy la valeur
numérique du flot entre x et y. Étape 1.
Initialisation par un flot réalisable. Au début, le flot Fxy = 0 pour tout
arc de 2 sommets (x, y). Étape 2.
On marque le sommet initial S avec (-, ?) : S n'a pas de sommet précédent (-
) et a un flot maximal (?).
x=S Étape 3.
Pour chaque sommet marqué x, chercher tous les sommets non marqués y
adjacents à x, que les arcs (x, y) soient bien ou mal orientés.
S'il n'existe aucun sommet non marqué y, c'est que le flot est maximal :
ARRET. S'il existe au moins un sommet non marqué y, pour chaque y trouvé il y a
deux cas possibles :
Cas 1 : l'arc (x, y) est bien orienté x y et la capacité Cxy > Fxy
(arc non saturé) :
Marquer y avec le couple (x, Cxy - Fxy), où x est le sommet précédent de
y, et Cxy - Fxy la valeur du flux entre x et y. Si Cxy = Fxy (arc saturé)
ne pas marquer y.
Cas 2 : l'arc (x, y) est mal orienté x y et Fxy > 0 (flot pas nul)
:
Marquer y avec le couple (x, Fxy) où x est le sommet précédent de y, et
Fxy la valeur du flux entre x et y. Si Fxy = 0 (flot nul) ne pas marquer
y.
Si y = sommet final T aller à l'étape 4, sinon x=y et répéter l'étape 3.
Étape 4.
- A l'aide des sommets précédents des y marqués, constituer une chaîne
augmentante menant de S à T.
- Calculer le flux Fmin de la chaîne augmentante = valeur minimale des flux
des sommets y marqués
- Pour chaque arc (x, y) bien orienté x y de la chaîne constituée,
Fxy = Fxy + Fmin
- Pour chaque arc (x, y) mal orienté x y de la chaîne constituée,
Fxy = Fxy - Fmin Étape 5.
Effacer toutes les marques et retourner à l'étape 2. EXERCICE CORRIGE [pic]
Avant d'établir un projet de construction d'autoroute, on désire étudier la
capacité du réseau routier, représenté par le graphe ci-dessous, reliant la
ville E à la ville S.
Pour cela, on a évalué le nombre m