Le problème du flot maximal

Le problème du flot maximal est un concept fondamental en théorie des graphes et en optimisation. Je vais vous l'expliquer simplement avec des exemples et des graphiques.

Qu'est-ce que le problème du flot maximal ?

Imaginez un réseau de tuyaux où l'eau circule d'un point source vers un point destination (puits). Chaque tuyau a une capacité maximale (combien d'eau peut y passer). Le problème du flot maximal consiste à déterminer la quantité maximale d'eau qui peut circuler de la source au puits sans dépasser la capacité d'aucun tuyau.

Éléments clés

1. Graphe orienté : Un ensemble de nœuds (sommets) reliés par des arcs (arêtes orientées)
2. Source (s) : Le nœud de départ du flot
3. Puits (t) : Le nœud d'arrivée du flot
4. Capacité (c) : La quantité maximale pouvant circuler sur chaque arc
5. Flot (f) : La quantité qui circule effectivement sur chaque arc

Exemple simple

Visualisons un petit réseau avec une source S, un puits T et quelques nœuds intermédiaires. Les nombres sur les arcs représentent les capacités.

Algorithmes de résolution

1. Algorithme de Ford-Fulkerson

C'est l'algorithme le plus connu pour résoudre ce problème. Il fonctionne comme suit :

1. Initialiser le flot à 0 sur tous les arcs
2. Tant qu'il existe un chemin d'augmentation de S à T :
   • Trouver un chemin où chaque arc peut accepter plus de flot
   • Déterminer la capacité résiduelle minimale sur ce chemin
   • Augmenter le flot sur ce chemin de cette valeur

2. Algorithme d'Edmonds-Karp

C'est une variante de Ford-Fulkerson qui utilise un parcours en largeur (BFS) pour trouver les chemins d'augmentation.