Discussion :

[Premium]

Bonjour,

j'aurais besoin d'aide pour savoir comment trouver une coupure de capacité maximale dans un graphe.

J'arrive à calculer le flot maximal d'un graphe mais je bloque dans la recherche de la coupure.

Si quelqu'un pouvait m'aider,ce serait sympa.

PS : j'ai un bouquin Introduction à l'Algorithmique mais je n'y arrive pas.

Merci de votre aide

[FrancisSourd]

Parles-tu de coupure minimale ou maximale? La coupure minimale s'obtient à partir du flot (c'est donc polynomial) mais la coupure maximale est un problème NP complet.
Peux-tu donc préciser ton problème?

[Premium]

Parles-tu de coupure minimale ou maximale? La coupure minimale s'obtient à partir du flot (c'est donc polynomial) mais la coupure maximale est un problème NP complet.
Peux-tu donc préciser ton problème?

Je parle de coupure de capacité minimale et de flot maximal.
Mon problème est que je ne sais pas comment m'y prendre pour trouver une coupure de capacité minimale,une fois que le flot maximal est trouvé.

Par exemple sur cette page,il y a un exemple:
http://www-igm.univ-mlv.fr/~mac/ENS/DOC/flots_13.pdf


je trouve le meme flot mais je ne comprends pas comment la coupure est trouvée

[FrancisSourd]

A partir de ta solution au problème de capacité max, il faut enlever de ton graphe les arcs saturés (ceux dont le flot qui les traverse est égale à leur capacité). Dans ce nouveau graphe (qui a plusieurs composantes connexes, sinon le flot n'est pas max) tu considères l'ensemble X des noeuds qui peuvent être atteints depuis la source (dans ton exemple, c'est l'ensemble des sommets S,A,C).
Une coupe de capacité min est alors donnée par l'ensemble des arcs qui sortent de X.

[Premium]

A partir de ta solution au problème de capacité max, il faut enlever de ton graphe les arcs saturés (ceux dont le flot qui les traverse est égale à leur capacité). Dans ce nouveau graphe (qui a plusieurs composantes connexes, sinon le flot n'est pas max) tu considères l'ensemble X des noeuds qui peuvent être atteints depuis la source (dans ton exemple, c'est l'ensemble des sommets S,A,C).
Une coupe de capacité min est alors donnée par l'ensemble des arcs qui sortent de X.

Lorsque j'enleve les arcs saturés,il ne me reste plus que (A,C) comme arc sortant de X .
Cet arc est 6/8 ce qui n'est pas les 12 .

Est ce que tu peux m'indiquer comment la coupe de capacité min (12) a été trouvé dans l'exemple?

[FrancisSourd]

Les arcs sortant de X sont les arcs qui ont leur origine dans X et leur destination hors de X (dans le graphe original).
Ce sont donc les arcs
(A,B) (C,D) et (C,E), ce qui fait une coupe de 6 + 3 + 3 = 12

[Premium]

Les arcs sortant de X sont les arcs qui ont leur origine dans X et leur destination hors de X (dans le graphe original).
Ce sont donc les arcs
(A,B) (C,D) et (C,E), ce qui fait une coupe de 6 + 3 + 3 = 12

Merci pour ton aide