View
102
Download
0
Category
Preview:
Citation preview
Démo 10 - #2
En détails…
1
5
7
4
2 6
3
0≤ 3
0≤ 7
0≤ 4
0≤ 3
0≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
Au début, tous les sommets sauf la source (1) sont dans T:
S = {1}; T ={2,3,4,5,6}
Notons la remarque précédente sur le graphe en accordant l’étiquette 0 au sommet 1 et T aux autres sommets
01
5
7
4
2 6
3
0≤ 3
0≤ 7
0≤ 4
0≤ 3
0≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
T
T
T
T
T
T
0≤ 5
0≤ 5
Ajoutons maintenant une étiquette relative à la capacité résiduelle du chemin qui à mené au sommet i.
Évidemment, pour 1 (la source) nous affecterons une étiquette infinie pour signifier une capacité infinie à fournir un flot.
01
5
7
4
2 6
3
0≤ 3
0≤ 7
0≤ 4
0≤ 3
0≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
T
T
T
T
T
T
01
5
7
4
2 6
3
0≤ 3
0≤ 7
0≤ 4
0≤ 3
0≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
T
T
T
T
T
T
∞
0≤ 5
0≤ 5
Pour les autres sommets, l’étiquette de capacité sera affectée au minimum entre l’étiquette du prédécesseur et la capacité résiduelle de l’arc reliant le prédécesseur au sommet courrant.
Observons les sommets qui sont à une distance topologique de 1 du sommet source (2,4,5,7).
01
5
7
4
2 6
3
0≤ 3
0≤ 7
0≤ 4
0≤ 3
0≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
T
T
T
T
T
T
∞
01
5
7
4
2 6
3
0≤ 3
0≤ 7
0≤ 4
0≤ 3
0≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
1
1
T
1
T
1
∞
1
2
3
3
0≤ 5
0≤ 5
Ils ont tous pour prédécesseur le sommet 1. Et pour le sommet 2, par exemple, on a une capacité résiduelle de 3, le minimum entre l’infini et (3-0).
On continue ainsi avec le sommet à distance topologique 2, 3, …
01
5
7
4
2 6
3
0≤ 3
0≤ 7
0≤ 4
0≤ 3
0≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
1
1
7
1
2
1
∞
1
2
2
3
3
3
01
5
7
4
2 6
3
0≤ 3
0≤ 7
0≤ 4
0≤ 3
0≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
1
1
T
1
T
1
∞
1
2
3
3
0≤ 5
0≤ 5
On remarque ici que l’étiquette de capacité (que l’on veut ici maximisée) du sommet 7 peut être augmentée en empruntant le chemin 1,2,4,7.
Il en va de même pour le sommet 6 en empruntant 1,2,4,6.
01
5
7
4
2 6
3
0≤ 3
0≤ 7
0≤ 4
0≤ 3
0≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
1
4
4
1
2
1
∞
1
2
3
3
3
3
01
5
7
4
2 6
3
0≤ 3
0≤ 7
0≤ 4
0≤ 3
0≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
1
1
7
1
2
1
∞
1
2
2
3
3
3
0≤ 5
0≤ 5
Maintenant que 6 est étiqueté avec une capacité résiduelle maximale, on a ici sans effort ε = 3, qui est ici égale à l’étiquette de capacité.
Maintenant, on est fin prêt à procédé à une nouvelle itération.
01
5
7
4
2 6
3
3≤ 3
3≤ 7
0≤ 4
0≤ 3
3≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
T
T
T
T
T
T
∞
0≤ 5
01
5
7
4
2 6
3
0+ε ≤ 3
0+ε ≤ 7
0≤ 4
0 ≤ 3
0+ε ≤ 3
0≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
1
4
4
1
2
1
∞
1
2
3
3
3
3
0≤ 5
01
5
7
4
2 6
3
3≤ 3
3≤ 7
0≤ 4
0+ε≤ 3
3≤ 3
0+ε ≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
1
4
7
1
T
T
∞
1
3
33
0+ε ≤ 5
Ici, il n’est pas nécessaire de tenter d’étiqueté 2 et 3 puisque 6 est étiqueté et que la capacité résiduelle 3 est forcément plus grande ou égale à celle qu’un autre chemin vers 6 aurait (vu les capacités des arcs entrant en 6).
01
5
7
4
2 6
3
3≤ 3
3≤ 7
0≤ 4
3≤ 3
3≤ 3
3≤ 3
0≤ 2
0≤ 2
0≤ 6
0≤ 1
0≤ 1
T
T
T
T
T
T
∞
3≤ 5
3-ε ≤ 7
3-ε ≤ 5
01
5
7
4
2 6
3
3≤ 3
0+ε ≤ 4
3≤ 3
3≤ 3
0+ε ≤ 2
0+ε ≤ 2
0 ≤ 60 ≤ 1
0≤ 1
1
1
3
7
2
4
∞
1
2
2
2
2
2
Il ne faut pas oublier qu’un arc peut être parcouru à rebours!!! Auquel cas, il faudra lui soustraire ε.
Nous avons terminé! Il n’y a plus de chemin non saturé se rendant à t=6 donc t sera dans T.
3≤ 3
01
5
7
4
2 6
3
3≤ 3
1≤ 7
2≤ 4
3≤ 3
3≤ 3
3≤ 3
2≤ 2
2≤ 2
0≤ 6
0≤ 1
0≤ 1
T
T
T
T
T
T
∞
1≤ 5
Recommended