Quelle min-cut trouve l'algorithme de Ford-Fulkerson?

Question

Il peut y avoir plusieurs coupes min dans un réseau. Par exemple:

a quatre coupes min et Ford-Fulkerson trouve une "plus proche" de s (la source). Pouvons-nous dire la même chose pour tous les réseaux? Autrement dit, Ford-Fulkerson trouve la coupure la plus proche de la source? Si cela est vrai, comment formaliser le concept de «plus proche de la source» dans les réseaux de flux?

Answer 1

Représentons une coupe comme un ensemble de sommets qui contient la source mais pas le puits. Les coupes minimales ont la propriété que l'intersection de deux coupes minimales est une coupure minimale (ceci est également vrai pour les syndicats). Ainsi, l'intersection de toutes les coupes minimales est en quelque sorte la coupure minimale «la plus proche» de la source, car c'est un sous-ensemble de toutes les autres coupes minimales.