Algorithme sur le flot maximal de Ford Fulkerson

Bonsoir,

Voilà ma question repose sur le flot maximal, sur le cours : http://www.lix.polytechnique.fr/~cori/Majeure/cours3.pdf

Je suis déjà bloquée sur entre page 4 et 5 :?

Si quelqu'un est déjà passé par là, pour m'expliquer les notions ci-dessous.

Merci


Cdt

Si tu fais l'analogie avec un réseau de tuyaux, un robinet ("s") et une évacuation ("t), c'est assez intuitif.

Le Lemme dit que TOUTE l'eau qui sort du robinet s'écoulera par terre si tu coupes ton réseau de tuyaux en 2. Bref, il n'y a pas d'eau qui resterait quelque part coincée entre le robinet et la coupe. :P

=> Le flot VΦ (à la sortie du robinet) est toujours égal au flot de la coupe (= la quantité d'eau qui sort du réseau).

Salut Pseudocode,

Je retiens ce que vous dites, mais j'ai plutôt du mal avec les formules pour la démonstration, la preuve par récurrence, déjà on a définit :
/_\ (Y,Z)=Φ(Y,Z)-Φ(Z,Y)
les deux flot Φ(Y,Z) et Φ(Z,Y) ne sont pas égaux?

Comment lire déjà le formule ? "Φ(Y U y,Z \ y) "


Φ(Y U y,Z \ y) = (Y,Z) + (y,Z) − (Y, y)

Φ(Z \ y, Y U y) = (Z, Y ) + (Z, y) − (y, Y )

ce qui donne :

/_\(Z \ y, Y [ y) = /_\(Z, Y ) + (y,Z) + (y, Y ) − (Y, y) − (Z, y) = /_\(Y,Z)

Sur l'exemple ptite "y" représente ça représente quel sommet ?

je veux juste comprendre cette démo.

Merci

Cdt

Citation:

---

Envoyé par witch

Salut Pseudocode,

Je retiens ce que vous dites, mais j'ai plutôt du mal avec les formules pour la démonstration, la preuve par récurrence, déjà on a définit :
/_\ (Y,Z)=Φ(Y,Z)-Φ(Z,Y)
les deux flot Φ(Y,Z) et Φ(Z,Y) ne sont pas égaux?

---

Non. Ils ne sont pas égaux. Il y a les flots sortants et les flots entrants.

Φ(Y,Z) c'est le flot qui part de Y pour aller vers Z. C'est à dire l'eau qui vient de la partie Y et qui va vers la partie Z, en passant par certains tuyaux de la coupe. Φ(Z,Y), c'est l'inverse... et c'est donc l'eau qui passe dans les autres tuyaux restant de la coupe.

D'où la formule du Lemme : si on fait la somme des flux qui sortent, et que l'on retranche les flux qui rentrent, au total on a le flux total du réseau.

Exemple simpliste :

      :
      :
S -->--->---
      :     |
      :     |
   --<---<--
  |   :
  |   :
   -->--->--- T
      :
      :

Si on coupe le réseau en 2 par les pointillés au milieu, on coupe 3 tuyaux.

Si on considère que le flot du robinet (VΦ) vaut +1, alors:
- Le flot sortant vaut +2 (2 tuyaux propagent l'eau de gauche a droite)
- Le flot entrant vaut +1 (1 tuyau propage l'eau de droite a gauche)

Le Lemme nous dit alors, en toute logique, qu'on n'a ni perdu ni crée d'eau en coupant le réseau. C'est à dire que :

• flot sortant - flot entrant = Flot au robinet
• Φ(gauche,droite)-Φ(droite,gauche) = VΦ
• 2 - 1 = 1

Citation:

---

Comment lire déjà le formule ? "Φ(Y U y,Z \ y) "

---

C'est le flot qui vient de "Y en ajoutant le tuyau y" et qui va vers "Z en lui enlevant le tuyau y".

Bref, on change l'emplacement de la coupe : le tuyau y passe de la partie Z à la partie Y

Bonsoir Pseudocode,

Merci beaucoup pour ces explications, vous venez de me sauver :)

Juste une ptite chose :
Reprenant la formule :

Citation:

---

Φ(Y U y,Z \ y) = Φ(Y,Z) + Φ(y,Z) − Φ(Y, y)

---

je regarde en même temps la représentation graphique sur le doc.

quand vous avez dit :

Citation:

---

C'est le flot qui vient de "Y en ajoutant le tuyau y" et qui va vers "Z en lui enlevant le tuyau y".

---

ça veut bien dire que le flot venant de Y et allant ver Z, en ajoutant le y à Z et en l'enlevant à Y.
C'est bien ça ?

Citation:

---

Envoyé par witch

ça veut bien dire que le flot venant de Y et allant ver Z, en ajoutant le y à Z et en l'enlevant à Y.
C'est bien ça ?

---

Non, c'est l'inverse

Y U y = "partie Y" Union "tuyau y" = Y + le tuyau y

Z \ y = "partie Z" privée de "tuyau y" = Z - le tuyau y

Ok pseudocode, c'est assez clair. Merci.

L'essentiel, dans la partie est plutôt de dérouler le script, chose que j'ai toujours du mal à faire.

J'ai dans mon cours

l'algorithme de marquage qui suit :

Citation:

---

1. On part d'un flot quelconque tel que 0<phi(u)<=C(u) pour tout u appartenant à U
2. On marque l'entrée du réseau par *
3. A chaqye étape, si x est marqué, si y n'est pas marqué alors

• Si f(x,y) < C(x,y) on marque y par +x

• Si phi(y,x) > 0 on marque y par -x

4. Si p est marqué, on s'arrête sinon on retourne en 3.

---

Je joins le graphe en exemple, avec en rouge le marquage.
pour quoi -2 ? si le flot de 1 vers S est supérieur à 0 (cad de y à x dans l'algo) je pense que de 2 à S respecte aussi la même condition phi(y,x) > 0.

Clair que j'ai pas bien compris :?

Citation:

---

Envoyé par witch

Clair que j'ai pas bien compris :?

---

Je ne comprend pas bien non plus les notations, ni ce qu'est censé faire cet algo.

Ok pas grave, je passe à autre chose.

Merci pour vos réponses Pseudocode ;)