Comment puis-je trouver la coupure minimale sur un graphique à l'aide d'un algorithme d'écoulement maximal?

à partir du sommet source, faites une recherche en profondeur d'abord le long des bords du réseau résiduel (c.-à-d. les bords non saturés et les bords arrières des bords qui ont un écoulement), et marquez tous les sommets qui peuvent être atteints de cette façon. La coupe se compose de tous les bords qui vont d'un vertex marqué à un vertex non marqué. Clairement, ces bords sont saturés et n'ont donc pas été parcouru. Comme vous l'avez noté, il peut y avoir d'autres bords saturés qui ne font pas partie de la coupe minimale.

Je ne veux pas être difficile, mais la solution suggérée n'est pas tout à fait juste comme proposé.

Correct solution : ce que vous devriez réellement faire est bfs/dfs sur le Residual-Network Gf ( read it up on wikipedia ) et des sommets de marquage. Et puis vous pouvez choisir ceux avec marqué de-vertex et banalisée pour les vertices.

pourquoi "suivre des arêtes non saturées" n'est pas assez : Considérez, que l'algorithme de flux sature les bords comme indiqué dans l'image. J'ai marqué les sommets que je visite avec l'approche de "Just following unsaturated edges" avec du vert. Il est clair que la seule min-cut correcte est le bord de E-F, alors que la solution suggérée retournerait également A-D (et peut-être même D-E).

Notez que le vertex D serait visité par la dfs/bfs si nous considérions Réseau résiduel à la place, parce qu'il y aurait un bord de E à D, faisant ainsi le bord de E-F le seul avec un-vertex marqué et un-vertex non marqué.

Note: L'algorithme de Falk peut être utilisé pour trouver à la fois une coupe minimale avec des sommets minimums et avec des sommets maximums. Pour ce dernier, l'algorithme devrait être inversé, c'est à dire. cherchez à partir du sommet de l'évier au lieu de la source. Voir une question connexe: flux réseau: Ajouter un nouveau bord

une façon de comprendre est, définissons une coupe comme deux ensembles S et T, qui incluront s et t, respectivement.

maintenant, ajouter tous les sommets en S qui sont accessibles à partir de s dans le réseau résiduel et mettre les bords restants en T. Ce sera une coupe.

Deuxièmement, la coupe peut être formée en mettant tous les sommets en T qui sont accessibles à partir de t dans le réseau résiduel et mettre les sommets restants en S.

regardez ça vidéo pour savoir comment trouver les sommets accessibles depuis s et t.

https://www.youtube.com/watch?v=FIJaXfUIXJA&index=4&list=PLe-ggMe31CTduQ68XQ-sVj32wYJIspTma

ainsi, pour donner la procédure exacte comment obtenir la Coupe minumum:

1. exécuter l'algorithme de Ford-Fulkerson pour trouver le flux max et obtenir le graphe résiduel ¹ .
2. exécuter bfs sur le graphe résiduel pour trouver l'ensemble des sommets qui sont accessibles à partir de la source dans le graphe résiduel.(en respectant le fait que vous ne pouvez pas utiliser les bords avec 0 de la capacité dans le graphe résiduel) IMPORTANT: vous devez utiliser reverse des bords dans le graphe résiduel pour trouver le jeu correct de Sommets atteignables!!! (voir cet algorithme)
3. toutes les arêtes dans le graphique original qui sont à partir d'un vertex accessible au vertex non accessible sont des arêtes coupées minimales. Imprimez tous ces bords.

¹ graphique dans lequel la capacité d'un bord est définie comme sa capacité d'origine moins son débit (débit à partir du maximum réseau de flux).

après le calcul du débit maximal, nous pouvons chercher les bords (u,v) de sorte que dans le graphique résiduel, il y a un bord dans le graphique résiduel de v à u et f(v,u) = c(u,v) [ce qui signifie que le bord est saturé]

après avoir shortlisting tels bords, nous pouvons choisir tels bords (u,v) en utilisant le critère qu'il n'existe pas de chemin à partir de u pour couler t dans le graphique résiduel. Si cette condition est remplie, ces arêtes font partie (S,T) couper

la durée D'exécution de cet algorithme peut être O(E) * O( V + E ) = O( E^2 )

je pense que c'est ce que les autres disent, mais je l'ai trouvé peu clair alors voici mon explication:

à partir du noeud source, faire un remplissage de crue du graphe, se déplaçant seulement le long des bords avec la capacité résiduelle, le marquage de chaque vertex visité. Vous pouvez utiliser un DFS pour cela. Rappelons que les bords arrières à partir d'un sommet ont une capacité résiduelle égale à l'écoulement le long de l'extrémité avant (ie. r(u, v) = reste de la capacité de l'arête (u, v), r(v, u) = flux(u, v)).

en effet, cela détermine la partie S de la Coupe S-T du graphe.

la coupe minimale sera maintenant l'ensemble des bords de sorte qu'un sommet soit marqué à partir de votre remplissage de flood ci-dessus, et l'autre sommet n'est pas marqué. Il s'agit d'arêtes sans capacité résiduelle (sinon vous les auriez traversées dans votre DFS), et forment ensemble la coupe minimale.

après avoir enlevé ces bords, l'ensemble de Sommets non marqués formera la section T de la couper.