IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme sur le flot maximal de Ford Fulkerson


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé
    Avatar de witch
    Inscrit en
    Mai 2007
    Messages
    346
    Détails du profil
    Informations personnelles :
    Âge : 39

    Informations forums :
    Inscription : Mai 2007
    Messages : 346
    Par défaut 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

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    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.

    => Le flot VΦ (à la sortie du robinet) est toujours égal au flot de la coupe (= la quantité d'eau qui sort du réseau).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre éclairé
    Avatar de witch
    Inscrit en
    Mai 2007
    Messages
    346
    Détails du profil
    Informations personnelles :
    Âge : 39

    Informations forums :
    Inscription : Mai 2007
    Messages : 346
    Par défaut
    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

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par witch Voir le message
    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



    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
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Membre éclairé
    Avatar de witch
    Inscrit en
    Mai 2007
    Messages
    346
    Détails du profil
    Informations personnelles :
    Âge : 39

    Informations forums :
    Inscription : Mai 2007
    Messages : 346
    Par défaut
    Bonsoir Pseudocode,

    Merci beaucoup pour ces explications, vous venez de me sauver

    Juste une ptite chose :
    Reprenant la formule :
    Φ(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 :

    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 ?

  6. #6
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par witch Voir le message
    ç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
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algorithme de Ford-Fulkerson
    Par moujaprim dans le forum MATLAB
    Réponses: 31
    Dernier message: 04/02/2012, 17h43
  2. Algorithme de Ford Fulkerson
    Par camelia136 dans le forum MATLAB
    Réponses: 8
    Dernier message: 10/08/2011, 14h39
  3. Algorithme de Ford-Fulkerson
    Par Du Wassoulou dans le forum C++
    Réponses: 3
    Dernier message: 26/12/2010, 19h29
  4. Algorithme de flot maximal à coût minimal
    Par flool dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 14/10/2009, 09h56
  5. Problème sur un réseau routier avec l'algo de Ford-Fulkerson
    Par Yakurena dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 20/02/2006, 09h35

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo