Chapitre 3 : Flots page 44

Chapitre 3 : Flots

Plan du chapitre 3 :

1. Définitions
1.1. Réseau de transport
1.2. Flots
1.3. Flot complet
2. Recherche d’un flot maximum dans un réseau de transport
2.1. Définition
2.2. Coupe
2.3. Théorème de Ford-Fulkerson
2.4. Algorithme de Ford-Fulkerson

1. Définitions
1.1. Réseau de transport
Un réseau de transport est un graphe 𝐺 = (𝑋, 𝑈) orienté, sans boucle, où chaque arc est
associé à un nombre 𝑐(𝑢) ≥ 0, appelé "capacité" de l'arc 𝑢. En outre, un tel réseau vérifie les
hypothèses suivantes :
 Il existe un seul nœud 𝑠 qui n'a pas de prédécesseurs, tous les autres en ont au moins
un. Ce nœud est appelé l'entrée du réseau, ou la source.
 Il existe également un seul nœud 𝑝 qui n'a pas 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 𝑅 = (𝑋, 𝑈, 𝐶) où 𝐶 = {𝑐(𝑢𝑗 ) / 𝑢𝑗 ∈ 𝑈}

Exemple :
3
𝑥3
𝑥1 6
2
3

𝑠 𝑝
.
4 𝑥2 𝑥4 7
2
[Link] d’un réseau de transport
1.2. Flot
Un flot 𝜑 dans un réseau de transport est une fonction qui associe à chaque arc 𝑢𝑗 (𝑗 =
1, 2, … , 𝑚) une quantité 𝜑(𝑢𝑗 ) qui représente la quantité de flot qui passe par cet arc, en
provenance de la source et en destination du puits.

Matière : Théorie des graphes 2ème année Licence Informatique Responsable de la matière : Amiar Lotfi
Chapitre 3 : Flots page 45

Un flot doit respecter la règle suivante : la somme des quantités de flot sur les arcs entrants
dans un nœud (autre que 𝑠 et 𝑝) doit être égale à la somme des quantités de flot sur les arcs
sortants de ce même nœud.

En d'autres termes, la quantité totale de flot qui entre dans un nœud est égale à la quantité
totale de flot qui en sort.

Exemple :

Dans le graphe, la quantité de flux rentrant dans 𝑥1 est égale à la somme des quantités de flux
sortant de 𝑥1 . La quantité de flot a pour valeur 2. La loi de Kirchoff est vérifiée au sommet 𝑥1 .

Formellement :
Un flot sur un graphe 𝐺 = (𝑋, 𝑈) est un vecteur ligne 𝜑 = [𝜑(𝑢1 ), 𝜑(𝑢2 ), … , 𝜑(𝑢𝑚 )] ∈ 𝑅 𝑚 à
𝑚 composantes. Ce flot est dit réalisable s’il satisfait aux conditions suivantes :
- 𝜑(𝑢𝑗 ) ≥ 0 ∀𝑗 ∈ {1, … , 𝑚} ⇔ 𝜑 ≥ 0
- 𝜑(𝑢𝑗 ) ≤ 𝑐(𝑢𝑗 ), ∀ 𝑢𝑗 ∈ 𝑈
Autrement dit, pour chaque arc 𝑢𝑗 , ∀𝑗 ∈ {1, … , 𝑚} , le flux 𝜑(𝑢𝑗 ) qui le traverse ne doit pas
dépasser la capacité de l'arc 𝑐(𝑢𝑗 ).
- en tout sommet 𝑖 ∈ 𝑋, 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 𝑗.

- En particulier,

∑ 𝜑𝑗 = ∑ 𝜑𝑗 = 𝜑0
𝑗∈𝑤 + (1) 𝑗∈𝑤 − (𝑛)

La quantité 𝜑0 représente le volume total que met en circulation dans le réseau le flot
réalisable 𝜑, elle est appelée : valeur du flot.

Un flot est dit de valeur maximale s’il maximise cette valeur 𝜑0 dans l’ensemble des flots
réalisables.

On retiendra dans ce qui suit la représentation suivante :

Matière : Théorie des graphes 2ème année Licence Informatique Responsable de la matière : Amiar Lotfi
Chapitre 3 : Flots page 46

x y
𝐶(𝑢𝑗 ) ; 𝜑(𝑢𝑗 )

La capacité de Le flux qui traverse

l’arc 𝑢𝑗 . l’arc 𝑢𝑗 .

[Link] de représentation d’un flot réalisable

Exemple :
3;1
𝑥3
𝑥1 6;1
2;2
3;1

𝑠 𝑝

.
4;2 𝑥2 𝑥4 7;3
2;2

Fig.3. Exemple d’un flot réalisable

Dans le réseau 𝑅, le flot qui traverse chaque arc ne dépasse pas sa capacité, alors ce flot est
réalisable.

1.3. Flot complet

Un flot est complet si pour tout chemin allant de la source au puits, il y’a au moins un arc
saturé, c'est-à-dire : le flux qui le traverse est égal à sa capacité (𝐶(𝑢) = 𝜑(𝑢)).

Exemple :
Dans le réseau de la figure Fig.3., on a 3 chemins qui mènent de 𝑠 à 𝑝 pour lesquels on a au
moins un arc saturé. Le flot est complet.

Arc saturé

Premier chemin : 𝑠 𝑥1 𝑥3 𝑝
2;2 3;1 6;1

Arc saturé

Deuxième chemin : 𝑠 𝑥1 𝑥4 𝑝
2;2 3;1 7;3

Arc saturé

Troisième chemin : 𝑠 𝑥2 𝑥4 𝑝
4;2 2;2 7;3

Matière : Théorie des graphes 2ème année Licence Informatique Responsable de la matière : Amiar Lotfi
Chapitre 3 : Flots page 47

2. Recherche d'un flot maximum dans un réseau de transport

2.1. Définition

Le problème du flot maximum consiste à trouver la quantité maximum de flot à acheminer de

la source 𝑠 vers le puits 𝑝, en tenant compte des capacités de transport et de la quantité
disponible en 𝑠.

2.2. Coupe

Soient 𝑠 et 𝑝 deux sommets d’un réseau 𝑅 = (𝑋, 𝑈, 𝐶).

D’une manière générale, une (𝑠, 𝑝) − 𝑐𝑜𝑢𝑝𝑒 est un ensemble 𝐶𝑝 d’arcs déconnectant 𝑠 de 𝑝
tel que il n’existe pas de chemin orienté de 𝑠 à 𝑝.

Une (𝑠, 𝑝) − 𝑐𝑜𝑢𝑝𝑒 se définit également par une partition 𝐶𝑝 = 𝑆 ∪ 𝑃 des sommets telle
que 𝑠 ∈ 𝑆, 𝑝 ∈ 𝑃 et 𝑆 ∩ 𝑃 = ∅.
Les arcs de la coupe sont alors les arcs (𝑥, 𝑦) ayant leur origine 𝑥 dans 𝑆 et leur destination 𝑦
dans 𝑃.
La capacité d'une coupe est la somme des capacités des arcs de la coupe :

𝐶(𝐶𝑝 ) = ∑ 𝑐(𝑥, 𝑦)
𝑥∈𝑆
𝑦∈𝑃

Le problème est de déterminer parmi toutes les coupes d'un réseau celle de capacité minimale.

2.2.1. Coupe Minimum (MinCut)

Le problème de la Coupe Minimum consiste à trouver une coupe 𝐶𝑝𝑚𝑖𝑛 entre 𝑠 et 𝑝 de

capacité minimale.

Une coupe est un passage obligé pour un flot, et potentiellement un goulot d'étranglement. En
effet un flot transitant de 𝑠 à 𝑝 doit nécessairement emprunter les arcs de la coupe (tous
chemins de 𝑠 à 𝑝 en comporte au moins un arc par définition).

La coupe minimale 𝐶𝑝𝑚𝑖𝑛 est une coupe telle que tous les arcs sortant de 𝐶𝑃 soient saturés et
tous les arcs entrant de 𝐶𝑃 portent un flot nul.

Formellement :
Une coupe 𝐶𝑃 est une coupe minimale si :

- L’arc (𝑥, 𝑦) est saturé si 𝑥 ∈ 𝑆 et 𝑦 ∈ 𝑃

- 𝜑(𝑥, 𝑦) = 0 si 𝑥 ∈ 𝑃 et 𝑦 ∈ 𝑆

Matière : Théorie des graphes 2ème année Licence Informatique Responsable de la matière : Amiar Lotfi
Chapitre 3 : Flots page 48

La valeur du flot peut ainsi être redéfinie comme le flot sortant de la coupe moins le flot
entrant.

Propriété 1 : Valeur d’un flot

Si 𝐶𝑝 = 𝑆 ∪ 𝑃 est une coupe et 𝜑 un flot sur le réseau 𝑅, alors la valeur du flot est égale au
flot sortant de 𝑆 moins le flot entrant de 𝑆.
| 𝜑𝐶𝑝 | = 𝜑𝐶+𝑝 (𝑆) − 𝜑𝐶−𝑝 (𝑆)
avec :
𝜑𝐶+𝑝 = ∑ 𝑥∈𝑆 𝜑(𝑥, 𝑦) et 𝜑𝐶−𝑝 (𝑆) = ∑𝑥∈𝑃 𝜑(𝑥, 𝑦)
𝑦∈𝑃 𝑦∈𝑆

Cette différence de sommes de flots est appelée flot net 𝜑𝐶𝑝 traversant la coupe 𝐶𝑝 .

Propriété 2 : MaxLow-MinCut
Si 𝜑 est un flot sur un réseau entre 𝑠 et 𝑝 et 𝐶𝑝 est une (𝑠, 𝑝) − 𝑐𝑜𝑢𝑝𝑒, alors : | 𝜑 | ≤ | 𝐶𝑝 |.
Ce qui peut également s'énoncer par rapport au flot maximum et à la coupe minimum :
| 𝜑𝑚𝑎𝑥 | ≤ | 𝐶𝑝 𝑚𝑖𝑛 |.

2.3. Théorème de Ford-Fulkerson

Etant donné un réseau de transport 𝐺 = (𝑋, 𝑈, 𝐶) et 𝜑 un flot réalisable sur 𝐺. La valeur du
flot maximum réalisable de 𝑠 à 𝑝 est égale à la capacité de la coupe minimale séparant 𝑠 et 𝑝 :
| 𝜑𝑚𝑎𝑥 | = | 𝐶𝑝 𝑚𝑖𝑛 |

2.4. Algorithme de Ford-Fulkerson

L’algorithme le plus connu pour résoudre ce problème est celui de Ford et Fulkerson.

2.4.1. Le principe

L’idée de l’algorithme de Ford et Fulkerson est de faire passer un flot compatible dans le
réseau, le plus évident est le flot nul, puis de l’améliorer jusqu’à ce qu’on obtienne un flot
complet.

Une chaîne 𝐶 est dite augmentante si :

 Pour tout arc 𝑢 direct de 𝐶, c'est-à-dire 𝑢 ∈ 𝐶 + : 𝜑(𝑢) < 𝑐(𝑢) .
 Pour tout arc 𝑢 indirect de 𝐶, c'est-à-dire 𝑢 ∈ 𝐶 − : 𝜑(𝑢) > 0 .

Le flot sur cette chaîne 𝐶 peut être augmenté de la valeur suivante :

𝜀 = 𝑀𝑖𝑛{𝑐(𝑢) − 𝜑(𝑢)/𝑢 ∈ 𝐶 + ; 𝜑(𝑢)/𝑢 ∈ 𝐶 − }

Matière : Théorie des graphes 2ème année Licence Informatique Responsable de la matière : Amiar Lotfi
Chapitre 3 : Flots page 49

Pour améliorer le flot, on ajoute 𝜀 au flot des arcs de 𝐶 + , c'est-à-dire les arcs directs dans la
chaîne, et on retranche au flot des arcs de 𝐶 − , c'est-à-dire, les arcs indirects dans la chaîne.

Exemple :
Voici la chaîne 𝐶 reliant les sommets 𝑠 et 𝑝 prise d’un réseau de transport dont le flot peut
être augmenté :

𝑠 𝑥1 𝑥2 𝑥3 𝑝
3;1 4;2 3;1 4;1

On augmentera le flot de cette chaîne de 1, on obtient alors le nouveau flot :

𝑠 𝑥1 𝑥2 𝑥3 𝑝
3;2 4;3 3;0 4;2

Propriété d’optimalité :
Un flot 𝜑 de 𝑠 à 𝑝 est maximal si et seulement s’il n’existe pas de chaîne augmentante de 𝑠 à
𝑝.

2.4.2. Enoncé

Données : un 1-graphe valué 𝐺 = (𝑋, 𝑈, 𝐶) ; 𝜑 un flot.

Résultat : un flot 𝜑 complet (maximum).

(0) Initialisation
Marquer le sommet 𝑠 et poser : 𝐶 + = ∅ ; 𝐶 − = ∅ ; 𝜑 𝑘 = 0 ; 𝐴 = {𝑠} ; 𝑘 = 0
(1) Soit 𝐴 l’ensemble des sommets marqués et soit 𝑥 un sommet de 𝐴 :
 Marquer le sommet 𝑦 successeur de 𝑥 tel que 𝜑(𝑥, 𝑦) < 𝑐(𝑥, 𝑦).
On pose : 𝐶 + : = 𝐶 + ∪ {(𝑥, 𝑦)} ; 𝐴 : = 𝐴 ∪ {𝑦}
 Marquer le sommet 𝑦 prédécesseur de 𝑥 tel que 𝜑(𝑦, 𝑥) > 0.
On pose : 𝐶 − : = 𝐶 − ∪ {(𝑦, 𝑥)} ; 𝐴 : = 𝐴 ∪ {𝑦}
Quand on ne peut plus marquer, deux cas se présentent :
1. 𝑝 est marqué aller en (𝟐)
2. 𝑝 n’est pas marqué, terminé, le flot est maximum.

(2) On a obtenu une chaîne augmentante 𝐶 = 𝐶 + ∪ 𝐶 − de 𝑠 à 𝑝

Pour améliorer le flot on calcule :
𝜀1 = 𝑚𝑖𝑛 {𝑐(𝑢) − 𝜑(𝑢)/𝑢 ∈ 𝐶 + }
𝜀2 = 𝑚𝑖𝑛 {𝜑(𝑢)/𝑢 ∈ 𝐶 − }
D’où 𝜀 = 𝑚𝑖𝑛 {𝜀1 , 𝜀2 }
On définit le nouveau flot :
𝜑 𝑘 (𝑢) + 𝜀 𝑝𝑜𝑢𝑟 𝑢 ∈ 𝐶 +
𝜑 𝑘+1 (𝑢) = {𝜑 𝑘 (𝑢) − 𝜀 𝑝𝑜𝑢𝑟 𝑢 ∈ 𝐶 −
𝜑 𝑘 (𝑢) 𝑝𝑜𝑢𝑟 𝑢 ∉ 𝐶
Effacer les marques sauf en 𝑠, et aller en (𝟏)
Sortie : 𝜑𝑚𝑎𝑥

Matière : Théorie des graphes 2ème année Licence Informatique Responsable de la matière : Amiar Lotfi
Chapitre 3 : Flots page 50

2.4.3. Valeur du flot maximum

La valeur du flot maximum 𝜑𝑚𝑎𝑥 est égale à celle des flux sortant de la source 𝑠, ou la
somme des valeurs des flux entrant au puits 𝑝. On le représente comme suit :

Arcs
Flux

𝜑𝑚𝑎𝑥 = ∑ (𝜑(𝑠, 𝑥)/𝑥 ∈ Г+ −

𝑅 (𝑠)) = ∑(𝜑(𝑥, 𝑝)/𝑥 ∈ Г𝑅 (𝑝))

2.4.4 Exemple d’application

Une usine à gaz alimente une ville 𝑉 par l’intermédiaire du réseau de distribution ci-dessous.
Les nombres associés aux arcs représentent les capacités de transport.

3
𝑥3
𝑥1
8
5
7
4
𝑔 𝑉

6 𝑥2 𝑥4 4
5

Fig.4. Un réseau de transport de 𝑔 vers 𝑉

On voudrait connaître la quantité maximale que peut écouler l’usine. Ce qui revient à chercher
un flot maximum sur le réseau ?
Application de l’algorithme de Ford-Fulkerson pour la recherche du flot maximum
Initialisation :
C+ = ∅ ; C − = ∅ ; φk = 0 ; A = {g} ; k = 0

3;0 𝑥3
𝑥1
8;0
5;0
7; 0
4;0
𝑔 𝑉

6;0 𝑥2 𝑥4 4;0
5;0

Fig.5. Le réseau 𝑅 avec 𝜑 0

Itération 1 :
Marquer les sommets dans l’ordre : (𝑔, 𝑥1 , 𝑥3 , 𝑉) , A = {g, 𝑥1 , 𝑥3 , 𝑉}

Matière : Théorie des graphes 2ème année Licence Informatique Responsable de la matière : Amiar Lotfi
Chapitre 3 : Flots page 51

Le sommet 𝑉 était marqué, la procédure de marquage s'arrête. On obtient donc la chaine

augmentante :
𝐶 = 𝐶 + ∪ 𝐶 − = 𝐶 + ∪ ∅ = {(𝑔, 𝑥1 ), (𝑥1 , 𝑥3 ), (𝑥3 , 𝑉)}
Pour améliorer le flot, on calcule :
𝜀1 = 𝑚𝑖𝑛{5 − 0, 3 − 0, 8 − 0} = 𝑚𝑖𝑛{5, 3, 8} = 3
Alors, on améliore le flot 𝜑 0 (Fig.5.) pour obtenir 𝜑1 (Fig.6.) en augmentant la chaine avec :
𝜀 = 𝜀1 = 3. Le flux des arcs n'appartenant pas à la chaine, reste inchangé.

3;3
𝑥3
𝑥1
8;3
5;3
7; 0
4;0
𝑔 𝑉

6;0 𝑥2 𝑥4 4 ;0
5;0

Fig.6. Le réseau 𝑅 avec 𝜑1

Itération 2 :
Marquer les sommets dans l’ordre : (𝑔, 𝑥2 , 𝑥3 , 𝑥4 , 𝑉) , A = {𝑔, 𝑥2 , 𝑥3 , 𝑥4 , 𝑉}
Le sommet 𝑉 était marqué, la procédure de marquage s'arrête. On obtient donc la chaine
augmentante :
𝐶 = 𝐶 + ∪ 𝐶 − = 𝐶 + ∪ ∅ = {(𝑔, 𝑥2 ), (𝑥2 , 𝑥3 ), (𝑥3 , 𝑥4 ), (𝑥4 , 𝑉)}
Pour améliorer le flot, on calcule :
𝜀1 = 𝑚𝑖𝑛{6 − 0, 7 − 0, 4 − 0, 4 − 0} = 𝑚𝑖𝑛{6, 5, 4, 4} = 4
Alors, on améliore le flot 𝜑1 (Fig.6.) pour obtenir 𝜑 2 (Fig.7.) en augmentant la chaine avec :
𝜀 = 𝜀1 = 4. Le flux des arcs n'appartenant pas à la chaine, reste inchangé.

3;3
𝑥3
𝑥1
8;3
5;3
7; 4
4;4
𝑔 𝑉

6;4 𝑥2 𝑥4 4;4
5;0
Fig.7. Le réseau 𝑅 avec 𝜑 2

Matière : Théorie des graphes 2ème année Licence Informatique Responsable de la matière : Amiar Lotfi
Chapitre 3 : Flots page 52

Itération 3 :
Marquer les sommets dans l’ordre : (𝑔, 𝑥2 , 𝑥4 , 𝑥3 , 𝑉) , A = {𝑔, 𝑥2 , 𝑥4 , 𝑥3 , 𝑉}
Le sommet 𝑉 était marqué, la procédure de marquage s'arrête. On obtient donc la chaine
augmentante :
𝐶 = 𝐶 + ∪ 𝐶 − = {(𝑔, 𝑥2 ), (𝑥2 , 𝑥4 ), (𝑥3 , 𝑉)} ∪ {(𝑥3 , 𝑥4 )}
Pour améliorer le flot, on calcule :
𝜀1 = 𝑚𝑖𝑛{6 − 4, 5 − 0, 8 − 3} = 𝑚𝑖𝑛{2, 5, 5} = 2
𝜀2 = 𝑚𝑖𝑛{4} = 4
Alors, on améliore le flot 𝜑 2 (Fig.7.) pour obtenir 𝜑 3 (Fig.8.) en augmentant la chaine avec :
𝜀 = 𝑚𝑖𝑛{𝜀1 , 𝜀2 } = 𝑚𝑖𝑛{2, 4 } = 2. Le flux des arcs n'appartenant pas à la chaine, reste
inchangé. 3;3
𝑥3
𝑥1
8;5
5;3
7; 4
4;2
𝑔 𝑉

6;6 𝑥2 𝑥4 4;4
5;2
Fig.8. Le réseau 𝑅 avec 𝜑 3
Itération 4 :
Marquer les sommets dans l’ordre : (𝑔, 𝑥1 , 𝑆𝑇𝑂𝑃) , A = {𝑔, 𝑥1 }
On ne peut plus marquer et V n’est pas marqué, ALORS terminé, le flot est maximum :
𝜑𝑚𝑎𝑥 = 𝜑 3 , et on le représente comme suit :

Arcs (𝑔, 𝑥1 ) (𝑔, 𝑥2 ) (𝑥1 , 𝑥3 ) (𝑥2 , 𝑥3 ) (𝑥2 , 𝑥4 ) (𝑥3 , 𝑥4 ) (𝑥3 , 𝑉) (𝑥4 , 𝑉)

Flux 3 6 3 4 2 2 5 4

La production maximale que peut écouler l'usine 𝑔 vers la ville 𝑉 :

𝜑𝑚𝑎𝑥 = ∑ (𝜑(𝑔, 𝑥)/𝑥 ∈ Г+ 3 3

𝑅 (𝑔)) = 𝜑 (𝑔, 𝑥1 ) + 𝜑 (𝑔, 𝑥2 ) = 3 + 6 = 9

ou

𝜑𝑚𝑎𝑥 = ∑(𝜑(𝑥, 𝑉)/𝑥 ∈ Г− 3 3

𝑅 (𝑉)) = 𝜑 (𝑥3 , 𝑉) + 𝜑 (𝑥4 , 𝑉) = 5 + 4 = 9

Alors :
𝝋𝒎𝒂𝒙 = 𝟗

Matière : Théorie des graphes 2ème année Licence Informatique Responsable de la matière : Amiar Lotfi
Chapitre 3 : Flots page 53

La (g, V) - coupe :
La (g, V) - coupe du réseau de transport de la figure Fig.8. est donnée par l’ensemble des
sommets marqués A = {𝑔, 𝑥1 } :

3;3
𝑥3
𝑥1
8;5
5;3
7; 4
4;2
𝑔 𝑉

6;6 𝑥2 𝑥4 4;4
5;2

[Link] (g, V) - coupe

L’ensemble des arcs de la (𝑔, 𝑉) – 𝑐𝑜𝑢𝑝𝑒 est donné par :

(𝑔, 𝑉) – 𝑐𝑜𝑢𝑝𝑒 = {(𝑔, 𝑥2 ), (𝑥1 , 𝑥3 ) }

tel que les extrémités initiales de ces arcs 𝑔, 𝑥1 ∈ 𝑆 et les extrémités terminales 𝑥2 , 𝑥3 ∈ 𝑃.
La (𝑔, 𝑉) − 𝑐𝑜𝑢𝑝𝑒 est la partition des sommets :
𝐶𝑝 = 𝑆 ∪ 𝑃/𝑆 = {𝑔, 𝑥1 } 𝑒𝑡 𝑃 = {𝑥2 , 𝑥3 , 𝑥4 , 𝑉} avec 𝑔 ∈ 𝑆, 𝑉 ∈ 𝑃 et 𝑆 ∩ 𝑃 = ∅.
La capacité de la (𝑔, 𝑉) – 𝑐𝑜𝑢𝑝𝑒 est égale à :

𝐶(𝐶𝑝 ) = ∑ 𝑐(𝑥, 𝑦) = 𝑐(𝑔, 𝑥2 ) + 𝑐(𝑥1 , 𝑥3 ) = 6 + 3 = 𝟗

𝑥∈𝑆
𝑦∈𝑃

Cette coupe 𝐶𝑃 est minimale car :

- Les arcs (𝑔, 𝑥2 ) et (𝑥1 , 𝑥3 ) sortant de la coupe sont saturés.
- Pas d’arcs entrant dans la coupe avec un flux 𝜑(𝑥, 𝑦) = 0, alors cette condition est
vérifiée implicitement.

Alors, la valeur du flot maximum réalisable de 𝑔 à 𝑉 calculé par l’algorithme de Ford-

Fulkerson (𝜑𝑚𝑎𝑥 = 9) est égale à la capacité de la (𝑔, 𝑉) – 𝑐𝑜𝑢𝑝𝑒 (| 𝐶𝑝 𝑚𝑖𝑛 | = 9).

Le flot net 𝜑𝐶𝑝 traversant la coupe 𝐶𝑝 𝑚𝑖𝑛 est égal à :

𝑚𝑖𝑛

| 𝜑𝐶𝑝 | = 𝜑𝐶+𝑝 (𝑆) − 𝜑𝐶−𝑝 (𝑆) = ∑ 𝑥∈𝑆 𝜑(𝑥, 𝑦) − ∑𝑥∈𝑃 𝜑(𝑥, 𝑦)

𝑚𝑖𝑛 𝑚𝑖𝑛 𝑚𝑖𝑛
𝑦∈𝑃 𝑦∈𝑆

| 𝜑𝐶𝑝 | = (𝜑(𝑔, 𝑥2 ) + 𝜑(𝑥1 , 𝑥3 )) − 0

𝑚𝑖𝑛

| 𝜑𝐶𝑝 | = (6 + 3) − 0 = 9 − 0 = 𝟗
𝑚𝑖𝑛

Matière : Théorie des graphes 2ème année Licence Informatique Responsable de la matière : Amiar Lotfi