Département de Mathématiques

Filière Génie Mathématique et Informatique

Problème de Flot
Rapport

Réalisé par :
Wissal Hattab Encadré par :
Ismail Iaich [Link]
Brahim Anougmar

Année 2023-2024
 Elemets finis Elemets finis

Remerciement

Nous tenons à exprimer notre profonde gratitude envers notre

enseignant, [Link], pour nous avoir donné l’opportunité
d’étudier et de mettre en pratique les algorithmes de théorie de
graphe, notamment l’algorithme de Ford-Fulkerson pour les
flots maximums.
Son soutien et ses explications détaillées ont grandement
contribué à notre compréhension de ces sujets complexes. Son
dévouement à notre apprentissage est sincèrement apprécié et a
enrichi notre expérience académique en tant que groupe. Nous lui
sommes reconnaissants pour son encouragement constant et son
engagement envers notre succès académique.

1
 Table des matières

Table des matières

1 Introduction 4

2 Notions de base des réseaux de flot 5

2.1 Représentation graphique de réseau . . . . . . . . . . . . . 5
2.2 Flot dans un réseau . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Valeur d’un flot . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Flot maximal 8
3.1 Arc saturé . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Flot complet . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 Flot maximal . . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Résolution d’un problème de flot maximal 11

4.1 Problème : Distribution d’eau portable . . . . . . . . . . . 11
4.2 Algorithme de Ford-Fulkerson . . . . . . . . . . . . . . . . 12
4.3 Application . . . . . . . . . . . . . . . . . . . . . . . . . . 13

5 Codes python 23
5.1 Algorithme de Ford-Fulkerson . . . . . . . . . . . . . . . . 23
5.2 Résolution de problème . . . . . . . . . . . . . . . . . . . 25

6 Conclusion 32

2
 List of Algorithms

Table des figures

1 Exemple d’un graphe de flot . . . . . . . . . . . . . . . . . 5
2 Flot réalisable . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Exemple des flots dans un réseau . . . . . . . . . . . . . . 7
4 Exemple d’un arc saturé . . . . . . . . . . . . . . . . . . . 8
5 Exemple d’un flot complet dans un réseau . . . . . . . . . 9
6 Chemins de graphe . . . . . . . . . . . . . . . . . . . . . . 9
7 Exemple d’un flot maximal dans un réseau . . . . . . . . . 10
8 Réseau de distribution d’eau portable . . . . . . . . . . . . 11
9 Flot initial du réseau de distribution d’eau . . . . . . . . . 13
10 Graphe résiduel associé au graphe de flot initial . . . . . . 13
11 Chemin améliorant du graphe résiduel de flot initital . . . 14
12 Flot maximal obtenu à l’itération 0 . . . . . . . . . . . . . 14
13 Graphe résiduel associé au graphe de flot à l’itération 1 . 15
14 Chemin améliorant du graphe résiduel de flot à l’itération 1 15
15 Flot maximal obtenu à l’itération 1 . . . . . . . . . . . . . 16
16 Graphe résiduel associé au graphe de flot à l’itération 2 . . 16
17 Chemin améliorant du graphe résiduel de flot à l’itération 2 17
18 Flot maximal obtenu à l’itération 2 . . . . . . . . . . . . . 17
19 Graphe résiduel associé au graphe de flot à l’itération 3 . . 18
20 Chemin améliorant du graphe résiduel de flot à l’itération 3 18
21 Flot maximal obtenu à l’itération 3 . . . . . . . . . . . . . 19
22 Graphe résiduel associé au graphe de flot à l’itération 4 . . 19
23 Chemin améliorant du graphe résiduel de flot à l’itération 4 20
24 Flot maximal obtenu à l’itération 4 . . . . . . . . . . . . . 20
25 Graphe résiduel associé au graphe de flot à l’itération 5 . 21
26 Chemin du graphe résiduel de flot à l’itération 5 . . . . . . 21
27 Flot maximal du réseau de distribution d’eau . . . . . . . 22

List of Algorithms
1 Algorithme de Ford-Fulkerson . . . . . . . . . . . . . . . . 12

3
 1 Introduction

............

1 Introduction
Le problème de flot, également connu sous le nom de problème de
circulation, est un concept fondamental en théorie des graphes et en opti-
misation combinatoire. Il trouve des applications dans divers domaines tels
que la logistique, les réseaux de télécommunications, la planification de la
production et la gestion des transports. À son cœur, le problème de flot
implique le déplacement efficace de ressources à travers un réseau, en res-
pectant certaines contraintes et en maximisant ou minimisant un objectif
spécifique.
En termes simples, le problème de flot consiste à déterminer comment
faire circuler des quantités de ressources, représentées par des « flots », à
travers un réseau de nœuds et d’arcs, tout en respectant des contraintes
telles que les capacités maximales des arcs et les demandes de flot sur les
nœuds. L’objectif peut varier selon le contexte ; il peut s’agir de maximiser
le flux total, de minimiser les coûts de transport, d’équilibrer la circulation
ou d’autres critères spécifiques.
Dans ce rapport, nous allons approfondir un aspect spécifique du pro-
blème de flot : le problème de flot maximal. Ce dernier consiste à détermi-
ner la quantité maximale d’éléments qu’il est possible de faire circuler d’un
point à un autre dans un réseau donné, en utilisant toutes les capacités
disponibles et en respectant les contraintes imposées par la structure du
réseau.
Notre étude se concentrera sur la résolution du problème de flot maximal
en utilisant l’algorithme de Ford-Fulkerson .

4
 2 Notions de base des réseaux de flot

2 Notions de base des réseaux de flot

2.1 Représentation graphique de réseau
Un réseau de flot est représenté par un graphe orienté et pondéré G(S, A, c)
où chaque arc (u, v) a une capacité c(u, v) qui indique la quantité maximale
de flux pouvant être transportée le long de cet arc.
Par exemple, considérons le graphe suivant :

Exemple

Figure 1 – Exemple d’un graphe de flot

Dans ce graphe, les nœuds sont représentés par les lettres A,B,C,D,E,F,G
où la source du flux est A et le puits est le nœud G. Chaque arc est associé
à une capacité maximale de flux, indiquée à côté de l’arc.
Par exemple, l’arc entre les nœuds B et E a une capacité maximale de 13.

2.2 Flot dans un réseau

Un flot fait référence à la quantité de quelque chose (comme de l’eau,
de l’électricité, des données, etc.) qui circule à travers les arcs d’un réseau.

Plus formellement, un flot dans un réseau est une fonction f : S × S → R

qui associe à chaque arc une valeur représentant la quantité de substance
(ou de quelque chose d’autre) qui traverse cet arc.

Un flot dans un réseau est dit réalisable s’il satisfait aux contraintes sui-
vantes :

5
 2 Notions de base des réseaux de flot

les contraintes de capacité sur les arcs :

Pour tout arc (u, v), la quantité de flot f (u, v) ne peut pas dépasser la
capacité c(u, v) de cet arc.

0 ≤ f (u, v) ≤ c(u, v)

la conservation du flot au niveau des nœuds :

Pour chaque nœud i ∈ S, à l’exception de la source s et du puits p, la
somme des flots entrants est égale à la somme des flots sortants.
X X
f (u, i) = f (i, v)
u∈S v∈S

Exemple

Figure 2 – Flot réalisable

— 11,6,5 représentent les quantités de flot sur les arcs.

— Le sous-graphe ci-dessus respecte les capacités maximales sur chaque
arc.
Par exemple :

f (A, B) = 11 ≤ c(A,B)=23
f (B, E) = 5 ≤ c(B,E)=13
— Ce sous-graphe assure également la conservation des flots ; la quantité
de flot entrant dans chaque nœud est égale à la quantité de flot sor-
tant.

6
 2 Notions de base des réseaux de flot

Par exemple :

f (A, B) − f (B, D) − f (B, E) = 11 − 6 − 5 = 0

2.3 Valeur d’un flot

Tout simplement c’est la quantité qui sort de la source s ou celle qui
entre en puits p.
X X
|f | = f (s, v) = f (u, p)
v∈S u∈S

Exemple

Considérons le graphe précédent

Figure 3 – Exemple des flots dans un réseau

La valeur de flot dans ce graphe est |f | = 14+11=12+3+10=25

7
 3 Flot maximal

3 Flot maximal
Nous nous attacherons à éclaircir certains concepts fondamentaux qui
sous-tendent le problème de flot maximal dans les réseaux. Notre objectif
est de fournir une explication approfondie et claire de trois notions cen-
trales : l’arc saturé, le flot complet et le flot maximal.

3.1 Arc saturé

Un arc saturé dans un réseau fait référence à une arête dont la capacité
maximale de flot a été atteinte.
Mathématiquement, si nous avons un réseau de flot avec une capacité maxi-
male c(u,v) sur l’arc reliant les nœuds u et v, et si le flot f (u,v) à travers cet
arc atteint sa capacité maximale, alors cet arc est considéré comme saturé
lorsque :
f (u, v) = c(u, v)

On appele (v,u) l’arc inverse.

Exemple

Figure 4 – Exemple d’un arc saturé

— L’arc (B,D) est saturé ;

f (B, D) = c(B, D) = 16

— Ainsi,l’arc (E,B) ; l’inverse de (B,E) est un arc saturé.

8
 3 Flot maximal

3.2 Flot complet

— Un flot complet dans un réseau de flot est une configuration où chaque

chemin reliant la source au puits est utilisé à sa pleine capacité.
— Cela signifie que le flot à travers chaque chemin est égal à la capacité
de ce chemin.
Mathématiquement, un flot est dit complet dans un réseau de flot si pour
chaque paire de nœuds s (source) et t (puits), tous les chemins possibles
reliant s à t contiennent au moins un arc saturé.

Exemple Considérons un autre graphe de flot complet.

Figure 5 – Exemple d’un flot complet dans un réseau

— Quelques chemins reliant A à J dans ce graphe :

Figure 6 – Chemins de graphe

— Dans cet exemple, tous les chemins possibles reliant la source (A) au
puits (J) ont au moins un arc saturé , donc le flot de ce graphe est
complet,sa valeur est |f | = 5+3+7=6+5+4=15.

9
 3 Flot maximal

3.3 Flot maximal

— Un flot maximal dans un réseau de flot est un agencement de flot qui

maximise le débit total du réseau, tout en respectant les capacités des
arcs.
— Mathématiquement,Le flot est dit maximal si sa valeur est optimale
— Déterminer un flot maximal dans un réseau implique de résoudre
un problème d’optimisation en utilisant des techniques telles que la
programmation linéaire en nombres entiers. Différents algorithmes,
comme l’algorithme de Ford-Fulkerson.

.....
Exemple

Graphe de flot maximal.

Figure 7 – Exemple d’un flot maximal dans un réseau

— Dans cet exemple, on peut dire que toutes les chaines reliant la source
(A) au puits (J) ont au moins un arc saturé , donc le flot de ce graphe
est maximal,sa valeur est |f | = 5+4+7=6+5+5=16.

10
 4 Résolution d’un problème de flot maximal

4 Résolution d’un problème de flot maximal

4.1 Problème : Distribution d’eau portable
Optimiser un réseau de distribution d’eau pour fournir un flot
maximal de la source aux points de consommation.
Dans un petit village, un réseau de distribution d’eau portable doit être op-
timisé pour assurer un approvisionnement maximal aux habitants. Chaque
tuyau dans le réseau a une capacité de transport d’eau spécifique.
Le but est de déterminer le flot maximal d’eau pouvant être envoyé de
la source (par exemple, un réservoir d’eau) vers les différents points de
consommation (par exemple, les maisons, les écoles) tout en respectant les
capacités de chaque tuyau.

Plus formellement, étant donné un graphe pondéré dirigé représentant le

réseau de distribution d’eau, où les nœuds représentent les points de dis-
tribution et les arêtes représentent les tuyaux avec leurs capacités, ainsi
qu’une source et un puits.
les nœuds sont représentés par des lettres A,B,C,D,E,F,G

Figure 8 – Réseau de distribution d’eau portable

— V (f )=30 représente le flot total circulant dans le réseau à ce un mo-

ment.

11
 4 Résolution d’un problème de flot maximal

Pour résoudre ce problème, on va utiliser l’algorithme de Ford-Fulkerson.

4.2 Algorithme de Ford-Fulkerson

L’idée principale de cet algorithme est d’augmenter itérativement le flot
à travers les chemins améliorants des graphes résiduels jusqu’à ce qu’aucun
chemin améliorant ne puisse être trouvé.
— Un chemin améliorant Ps,p est un chemin de la source vers le puits
dans le graphe résiduel Gf où la capacité résiduelle de chaque arête
est strictement positive.
— min(u,v)∈S(Ps,p ) cf (u, v) est le minimum des capacités résiduelles d’un
chemin améliorant Ps,p .
— Cette capacité résiduelle minimale est ajoutée ou au flot de chaque
arc le long du chemin dans le graphe original.
— Le graphe résiduel est construit en ajoutant des arêtes résiduelles
aux arêtes existantes.
— Une arête résiduelle représente la capacité supplémentaire qui peut
être ajoutée au flux le long de cette arête. Elle est utilisée pour com-
penser le flux existant et permettre d’augmenter le flux global.
Voici les étapes principales de l’algorithme de Ford-Fulkerson :

Algorithm 1 Algorithme de Ford-Fulkerson

1: Initialiser le flot.
2: while il existe un chemin améliorant du source au puits do
3: Trouver un chemin améliorant.
4: Déterminer le flux maximal pouvant être ajouté le long de ce chemin.
5: Mettre à jour le flot en ajoutant ce flux au réseau.
6: end while
7: return Le flot final.

La coupe minimale
Une coupe dans un réseau de flot est une partition de l’ensemble des nœuds
du réseau en deux ensembles, généralement appelés le "côté source N " et
le "côté puits N ".
La coupe minimale est donc la coupe dont la capacité est la plus petite
parmi toutes les coupes possibles qui séparent la source du puits.
Mathématiquement,la capacité de la coupe est :
X
c(N, N ) = c(u, v)
u∈N,v∈N

12
 4 Résolution d’un problème de flot maximal

4.3 Application
Résolution du problème :

- itération=0
Considérons le flot actuel (un flot réalisable) comme un flot initial , sa va-
leur est V (f )=30.

Figure 9 – Flot initial du réseau de distribution d’eau

Étape 1 : Le graphe résiduel

Le graphe résiduel associé est :

Figure 10 – Graphe résiduel associé au graphe de flot initial

13
 4 Résolution d’un problème de flot maximal

Étape 2 : Trouver un chemin améliorant

Le chemin améliorant trouvé est : A-B-E-G

Figure 11 – Chemin améliorant du graphe résiduel de flot initital

Le minimum des capacités résiduelles de ce chemin est min(4, 10, 27) = 4

Étape 3 : Rééquilibrer le flot le long de chemin dans le graphe

original
On va rééquilibrer de 4 le flot le long de ce chemin pour augmenter le flot
global courant.

Figure 12 – Flot maximal obtenu à l’itération 0

La valeur de flot courant V (f )=34.

14
 4 Résolution d’un problème de flot maximal

............
- itération=1
Étape 1 : Le graphe résiduel
Le graphe résiduel associé est :

Figure 13 – Graphe résiduel associé au graphe de flot à l’itération 1

Étape 2 : Trouver un chemin améliorant

Le chemin améliorant trouvé est : A-C-F-E,G

Figure 14 – Chemin améliorant du graphe résiduel de flot à l’itération 1

Le minimum des capacités résiduelles de ce chemin est min(26, 5, 4, 23) = 4

Étape 3 : Rééquilibrer le flot le long de chemin dans le graphe

original
On va rééquilibrer de 4 le flot le long de ce chemin pour augmenter le flot
global courant.

15
 4 Résolution d’un problème de flot maximal

............
............

Figure 15 – Flot maximal obtenu à l’itération 1

La valeur de flot courant V (f )=38.

............
- itération=2
Étape 1 : Le graphe résiduel
Le graphe résiduel associé est :

Figure 16 – Graphe résiduel associé au graphe de flot à l’itération 2

16
 4 Résolution d’un problème de flot maximal

............
Étape 2 : Trouver un chemin améliorant
Le chemin améliorant trouvé est : A-C-D-G

Figure 17 – Chemin améliorant du graphe résiduel de flot à l’itération 2

Le minimum des capacités résiduelles de ce chemin est min(22, 13, 5) = 5

Étape 3 : Rééquilibrer le flot le long de chemin dans le graphe

original
On va rééquilibrer de 5 le flot le long de ce chemin pour augmenter le flot
global courant.

Figure 18 – Flot maximal obtenu à l’itération 2

La valeur de flot courant V (f )=43.

17
 ..........
- itération=3
Étape 1 : Le graphe résiduel
Le graphe résiduel associé est :

Figure 19 – Graphe résiduel associé au graphe de flot à l’itération 3

Étape 2 : Trouver un chemin améliorant

Le chemin améliorant trouvé est : A-C-E-G

Figure 20 – Chemin améliorant du graphe résiduel de flot à l’itération 3

Le minimum des capacités résiduelles de ce chemin est min(17, 10, 19) = 10

Étape 3 : Rééquilibrer le flot le long de chemin dans le graphe

original
On va rééquilibrer de 10 le flot le long de ce chemin pour augmenter le flot
global courant.

18
 ............
............

Figure 21 – Flot maximal obtenu à l’itération 3

La valeur de flot courant V (f )=53.

............
- itération=4

Étape 1 : Le graphe résiduel

Le graphe résiduel associé est :

Figure 22 – Graphe résiduel associé au graphe de flot à l’itération 4

Étape 2 : Trouver un chemin améliorant

Le chemin améliorant trouvé est : A-C-D-B-E-G

19
 Figure 23 – Chemin améliorant du graphe résiduel de flot à l’itération 4

Le minimum des capacités résiduelles de ce chemin est min(7, 8, 16, 6, 9) = 6

Étape 3 : Rééquilibrer le flot le long de chemin dans le graphe original

On va rééquilibrer de 6 le flot le long de ce chemin pour augmenter le flot global courant.

Figure 24 – Flot maximal obtenu à l’itération 4

La valeur de flot courant V (f )=59.

- itération=5

Étape 1 : Le graphe résiduel

Le graphe résiduel associé est :

20
 Figure 25 – Graphe résiduel associé au graphe de flot à l’itération 5

............
Étape 2 : Trouver un chemin améliorant
On n’a pas de chemins améliorants qui va de s à p.

Figure 26 – Chemin du graphe résiduel de flot à l’itération 5

Le flot est donc optimal et sa valeur est V (f )=59.

Coupe minimale

Reprenons le flot optimal obtenu par l’application d’algorithme de Ford-Fulkerson.

21
 Figure 27 – Flot maximal du réseau de distribution d’eau

Les sommets qu’on peut atteindre depuis A sont :

A,C,F,D,B

On partitionne le graphe courant :

N = {A,C,F,D,B} et N = {E,G}

les arcs qui traversent cette coupe sont : (B,E),(C,E),(F,E),(F,G),(D,G).

La capacité de la coupe est égale à : c(N ,N )=13+10+4+10+22 =59

Alors il n’existe pas de flot de valeur supérieure à 59, donc nous avons trouvé un flot
de valeur optimale V(f )=59.

22
 5 Codes python
5.1 Algorithme de Ford-Fulkerson
1 from collections import defaultdict
2 import matplotlib . pyplot as plt
3 import networkx as nx
4

5 # Algorithme de Ford - Fulkerson :

6

7 class ReseauFlux :
8 def __init__ ( self , graphe ) :
9 self . graphe = graphe # Initialisation du reseau de flux
avec le graphe donne
10

11 def ford_fulkerson ( self , source , puits ) :

12

13 # Fonction de recherche de chemin ameliorant utilisant

une recherche en profondeur ( en anglais DFS : Depth -
First Search )
14

15 def dfs (u , puits , chemin , visite ) :

16 if u == puits :
17 return chemin
18 visite . add ( u )
19 for v , capacite in enumerate ( self . graphe [ u ]) :
20 if capacite > 0 and v not in visite :
21 resultat = dfs (v , puits , chemin + [( u , v ) ] ,
visite )
22 if resultat :
23 return resultat
24 return None
25

26 # Initialisation du flot maximal

27 flot_maximal = 0
28

29 # Initialisation du compteur d ’ iteration

30 iteration = 0
31

32 # Boucle principale de l ’ algorithme de Ford - Fulkerson

33 while True :
34

35 # Affichage du graphe a chaque iteration

36

37 G = nx . DiGraph ()
38 labels_noeuds = {}
39 for u in range ( len ( self . graphe ) ) :
40 labels_noeuds [ u ] = chr ( ord ( ’A ’) + u ) #
Correspondance des noeuds avec des lettres
41 for v in range ( len ( self . graphe [ u ]) ) :

23
42 if self . graphe [ u ][ v ] > 0:
43 G . add_edge (u , v , capacite = self . graphe [ u ][
v ])
44 plt . figure ( figsize =(10 , 5) )
45 pos = nx . circular_layout ( G ) # Utilisation de la
disposition circulaire
46

47 # Definition des couleurs des noeuds et des aretes

48

49 couleurs_noeuds = [ ’ skyblue ’ if noeud != source and

noeud != puits else ’ cyan ’ if noeud == source else
’ yellow ’ for noeud in G . nodes () ]
50 couleurs_aretes = [ ’ black ’ for _ in G . edges () ]
51 nx . draw (G , pos , with_labels = True , labels =
labels_noeuds , node_color = couleurs_noeuds ,
node_size =1500 , edge_color = couleurs_aretes ,
linewidths =1 , arrows = True )
52 labels = nx . g et _ e dg e _ at t r ib u t es (G , ’ capacite ’)
53 nx . d r a w _ n e t w o r k x _ e d g e _ l a b e l s (G , pos , edge_labels =
labels )
54 plt . title ( f ’ Iteration { iteration }: Flot maximal ’)
55 plt . show ()
56

57 print ( f " Iteration { iteration }: " )

58 iteration += 1
59 chemin = dfs ( source , puits , [] , set () )
60 if not chemin :
61 break
62 print ( " Chemin ameliorant trouve : " , chemin )
63

64 # Calcul du flot a augmenter

65

66 flot = min ( self . graphe [ u ][ v ] for u , v in chemin )

67 print ( " Flot a augmenter : " , flot )
68 flot_maximal += flot
69

70 # Mise a jour des capacites residuelles du graphe

71

72 for u , v in chemin :
73 self . graphe [ u ][ v ] -= flot
74 self . graphe [ v ][ u ] += flot # Capacite residuelle
75

76 print ( " Mise a jour du reseau de flot : " )

77 for ligne in self . graphe :
78 print ( ligne )
79 return flot_maximal
80

81 # Determiner les noeuds du cote source et du cote puits de la

coupe minimale
82

24
83 def min_cut_noeuds ( self , source , puits ) :
84 visite = set ()
85 file_attente = [ source ]
86 while file_attente :
87 u = file_attente . pop (0)
88 visite . add ( u )
89

90 # Parcours en largeur ( en anglais BFS : Breadth - First

Search ) pour trouver les noeuds accessibles depuis
la source
91

92 for v , capacite in enumerate ( self . graphe [ u ]) :

93 if capacite > 0 and v not in visite :
94 file_attente . append ( v )
95 cote_source = visite
96 cote_puits = set ( range ( len ( self . graphe ) ) ) - visite
97 return cote_source , cote_puits # Retourne les noeuds du
cote source et du cote puits de la coupure minimale

5.2 Résolution de problème

.
Input :
1 # Le Graphe du reseau de distribution d ’ eau
2

3 graph = [[0 ,23 ,37 , 0 , 0 , 0 , 0] ,

4 [0 , 0 , 0 ,16 ,13 , 0 , 0] ,
5 [0 , 0 , 0 ,14 ,10 ,15 , 0] ,
6 [0 , 0 , 0 , 0 , 0 , 0 ,22] ,
7 [0 , 0 , 0 , 0 , 0 , 0 ,30] ,
8 [0 , 0 , 0 , 0 , 4 , 0 ,10] ,
9 [0 , 0 , 0 , 0 , 0 , 0 , 0]]
10

11

12 # Creation d ’ un objet de la classe ReseauFlux avec le graphe

donne
13 reseau = ReseauFlux ( graph )
14

15

16 # Definition du noeud source et du noeud puits

17 source = 0
18 puits = 6
19

20

21 # Calcul du flot maximal dans le reseau en utilisant l ’ algorithme

de Ford - Fulkerson
22

23 flot_maximal = reseau . ford_fulkerson ( source , puits )

24 print ( " Flot maximal : " , flot_maximal )

25
Output :

26
.............

27
...................

28
 ...................... :

;;;;;;;;;;;;;;

29
...............

30
 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

la coupe minimale :
Input :

1 # Recherche des noeuds du cote source et du cote puits de la coupe

minimale
2

3 noeuds_source , noeuds_puits = reseau . min_cut_noeuds ( source , puits

)
4 print ( " Noeuds du cote source de la coupe minimale : " ,
noeuds_source )
5 print ( " Noeuds du cote puits de la coupe minimale : " , noeuds_puits )
Output :

Donc La valeur de flot optimale est 59.

31
 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

6 Conclusion
En conclusion, le problème du flot maximal est d’une importance cruciale dans de
nombreuses applications pratiques, allant de la logistique à la conception de réseaux in-
formatiques.
À travers ce rapport, nous avons examiné divers aspects de ce problème, y compris ses
définitions, ses algorithmes de résolution et ses applications. Nous avons constaté l’algo-
rithme efficace de Ford-Fulkerson qui est capable de trouver des solutions optimales dans
des délais raisonnables pour une grande variété d’instances du problème. Cependant, la
complexité théorique de ce problème reste un défi important, et de nouvelles recherches
sont nécessaires pour explorer des approches plus efficaces dans des contextes spécifiques.
En outre, nous avons souligné l’importance de la modélisation précise des problèmes réels
pour garantir que les solutions trouvées soient réellement applicables et pertinentes.
En fin de compte, le problème du flot maximal demeure un domaine riche en défis et en
opportunités, avec un potentiel continu pour des applications innovantes et des avancées
théoriques.

32