Graphes de Flots

Introduction

• Un graphe de flot modélise des réseaux (réseaux de transport, télécommunications, etc.).

• On y définit un flux maximal allant de la source au puits, en respectant les capacités.

Concepts Clés

• Flot (f): Quantité circulant dans le graphe.

• Capacité (c): Limite maximale sur chaque arc.

• Source (s) et Puits (t): Point de départ et d’arrivée des flux.

• Conservation: Pour tout sommet sauf s et t, le flux entrant est égal au flux sortant.

Algorithme de Résolution

• Ford-Fulkerson: Cherche des chemins augmentants pour améliorer le flot.

• Edmonds-Karp: Variante utilisant une recherche en largeur pour sélectionner le chemin le plus court augmentant.

Pseudo-code de Ford-Fulkerson

f = 0
Tant que existe un chemin p de s à t dans le graphe résiduel :
    δ = min{ capacité résiduelle sur p }
    Pour chaque arc (u,v) de p :
         f(u,v) += δ
         f(v,u) -= δ
    f = f + δ
Retourner f

Propriétés et Théorème

• Théorème du flot maximum/coupe minimale : Le flot maximal est égal à la capacité minimale d'une coupe séparant s et t.

• La méthode repose sur l'amélioration itérative jusqu'à saturation.