Construire un flot complet

[juju78]

Bonjour
on a le graphe suivant

http://img207.imageshack.us/i/dscn3128j.jpg/
en rouge on a fait circuler un flot realisable

je dois contruire un flot complet mais j'ai du mal je ne sais ps trop comment proceder ?

[sclormu]

Haha mais tu postes sur tous les forums toi !

Alors soit tu as vu un algorithme dans le cours qui permet de le faire, par exemple Ford-Fulkerson, soit tu n'as pas de méthode dans le cours et tu ne peux pas.

[juju78]

Bonsoir :)

oui j'ai en effet vu cette algorithme


je dois commencer de bas en haut c ca?
On doit examiner systematiquement tous les chemins de e vers s, en commencant par celui du bas.Sur chaque chemin il faut faire passer un flot de valeur égale a la capacié residuelle minimale des arcs de facon à saturer au moins un arc ?


donc si on considere le chemin E B C S

on a [0,7] pour {E B}, [2,4] pour {B C} et [0,3]pour {CS}

la valeur min c'est 0 pour cet arc non?

[sclormu]

C'est trop compliqué pour expliquer ça ici, il faut trouver des chaines augmentantes, parfois augmenter les flux ou les diminuer...
C'est le rôle de ton prof ou chargé de TD. Essaie de fureter sur internet pour voir si tu ne trouves pas un cours avec exemple.

[juju78]

on a fait un exemple dans le cour que j'ai bien compris
mais ici il y a des bornes minimales donc ça change un peu et je sais pas comment faire
qu'estce qu'on retient pour le chemin E B C S par exemple ?

[sclormu]

Comment ça qu'est-ce qu'on retient ?

[juju78]

Ben sur chaque chemin il faut faire passer un flot de valeur égale a la capacité residuelle minimale des arcs de ce chemin
donc ici la capacité residuelle correspond à quoi?

[sclormu]

Ben si tu veux faire passe quelque chose sur ce chemin de E à S ce ne pourra être que 3 ou 4.