Comment puis-je trouver la coupe minimale d'un graphe en utilisant un algorithme de flux maximal ?

Question

Je dois trouver la coupe minimale sur un graphe. J'ai lu des informations sur les réseaux de fluide, mais tout ce que je trouve sont des algorithmes de flux maximum tels que Ford-Fulkerson, push-relabel, etc. Étant donné le théorème du flux maximal-coupe minimale, est-il possible d'utiliser l'un de ces algorithmes pour trouver la coupe minimale sur un graphe en utilisant un algorithme de flux maximum? Comment?

Les meilleures informations que j'ai trouvées jusqu'à présent sont que si je trouve des arêtes "saturées" c'est-à-dire des arêtes où le flux égale la capacité, ces arêtes correspondent à la coupe minimale. Est-ce vrai? Ça ne me semble pas tout à fait juste. Il est vrai que toutes les arêtes de la coupe minimale seront saturées, mais je crois qu'il pourrait également y avoir des arêtes saturées qui sont en dehors du "chemin" de la coupe minimale.

Answer 1

À partir du sommet source, effectuer une recherche en profondeur le long des arêtes dans le réseau résiduel (c'est-à-dire les arêtes non saturées et les arêtes de retour des arêtes ayant un flux), et marquer tous les sommets qui peuvent être atteints de cette manière. La coupe est composée de toutes les arêtes qui vont d'un sommet marqué à un sommet non marqué. De façon évidente, ces arêtes sont saturées et n'ont donc pas été parcourues. Comme vous l'avez noté, il peut y avoir d'autres arêtes saturées qui ne font pas partie de la coupe minimale.

Answer 2

Je ne veux pas être pointilleux, mais la solution suggérée n'est pas tout à fait correcte telle que proposée.

Solution correcte: Ce que vous devriez réellement faire, c'est bfs/dfs sur le réseau résiduel Gf (lisez à ce sujet sur wikipedia) et marquer les sommets. Ensuite, vous pouvez choisir ceux avec un sommet d'où l'on part marqué et un sommet d'arrivée non marqué.

Pourquoi "suivre les arêtes non saturées" ne suffit pas: Considérez que l'algorithme de flot sature les arêtes comme le montre l'image. J'ai marqué les sommets que je visite avec l'approche "juste suivre les arêtes non saturées" en vert. Clairement, le seul min-coupe correct est l'arête de E à F, tandis que la solution suggérée retournerait également A à D (et peut-être même D à E).

Notez que le sommet D serait visité par le dfs/bfs si nous considérions le réseau résiduel à la place, car il y aurait une arête de E à D, ce qui ferait de l'arête E-F la seule avec un sommet d'où l'on part marqué et un sommet d'arrivée non marqué.

Answer 3

Si vous jetez un œil à ce réseau de flot, il devient clair pourquoi la réponse de Falk Hüffner est correcte. Si vous commencez à la source (nœud 1) et essayez d'atteindre l'écoulement (nœud 7), le min cut est donné par l'ensemble des arêtes que vous ne pouvez pas traverser car il n'y a pas de capacité résiduelle.

Answer 4

Note : L'algorithme de Falk peut être utilisé pour trouver à la fois une coupe minimale avec un minimum de sommets et avec un maximum de sommets. Pour ce dernier, l'algorithme doit être inversé, c'est-à-dire rechercher à partir du sommet puits au lieu de la source. Voir une question connexe : Flot de réseau : Ajout d'un nouvel arête

Answer 5

Ou mieux encore, utiliser une approche totalement différente en n'utilisant pas de diagrammes de flux pour trouver la coupe minimale. Vous pouvez consulter un algorithme populaire ici

http://www.cin.ufpe.br/~pcp/stoer-wagner.pdf