Modélisation des problèmes de coupes minimales
Graphe correspondant au problème de recherche de coupes minimales
On considère le même graphe orienté muni d'une seule source et d'un seul puits ainsi que de capacités G=(X, E, C) de la section précédente.
Définition : Définition d'une coupe dans un graphe orienté connexe muni d'une seule source et d'un seul puits
Une coupe d'un graphe G=(X, E) est définie par un sous-ensemble X' de points tels que s est dans X' et t est dans X-X'.
Les arcs de la coupe sont les arcs (x,y) de G tels que x est dans X' et y est dans X-X'.
Définition : Capacité d'une coupe et problème de la coupe minimale
La capacité d'une coupe (X', X-X') est la somme des capacités des arcs de la coupe.
Le problème de la coupe minimale consiste à trouver la coupe dont la capacité est minimale.
