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

  1. #1
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2018
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2018
    Messages : 3
    Points : 3
    Points
    3

    Par défaut Non-terminaison de l'algorithme de Ford-Fulkerson

    Bonjour !
    On démontre aisément que l'algorithme de Ford-Fulkerson se termine pour des capacités entières (et donc pour des capacités rationnelles).
    Or, j'ai lu qu'il pouvait ne pas se terminer pour des capacités irrationnelles. Je vois à peu près pourquoi mais je n'arrive pas à trouver d'exemple concret de graphe dans cette situation.
    Quelqu'un pourrait-il m'aider à construire un tel graphe ?

  2. #2
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 876
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 876
    Points : 9 436
    Points
    9 436

    Par défaut

    Bonjour

    Quelqu'un pourrait-il m'aider à construire un tel graphe ?


    La réponse est ici (clic).


    L'explication est simple.
    • La saturation des arcs directs est une augmentation de la valeur du flot.
    • La saturation des arcs inverses est une diminution de la valeur du flot.

    Donc, dans la 2ème phase de Ford Fulkerson, si tu choisis 2 chaînes, dont chacune a un arc direct qui correspond à l'arc inverse de l'autre, et inversement, il est possible que cela boucle. Cette boucle se termine-t-elle ? S'il y a un déséquilibre, sûrement. Mais si une capacité est irrationnelle, on peut certainement trouver un graphe, correspondant à un polynôme, qui trouve un équilibre.
    Par suite, l'algorithme passera son temps a déshabillé Pierre pour habiller Paul et inversement: boucle infinie.

    Étudie le lien que je t'ai donné pour mieux comprendre.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2018
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 20
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2018
    Messages : 3
    Points : 3
    Points
    3

    Par défaut

    Merci beaucoup !!
    J'avais plus ou moins eu la bonne idée mais je n'arrivais pas à boucler correctement pour parcourir la suite (et j'étais plutôt parti sur une somme genre e ou ln(2) ).
    Il est vrai que je suis un peu un boulet, je n'ai pas encore le réflexe de faire ce genre de recherche en anglais, c'est pour ça que je n'ai pas trouvé x)

Discussions similaires

  1. [Graphe] Flot maximal par l'algorithme de Ford-Fulkerson
    Par Pluplume dans le forum Algorithmes et structures de données
    Réponses: 17
    Dernier message: 31/03/2019, 12h19
  2. Flot maximal : algorithme de Ford-Fulkerson
    Par Webb_Ellis dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 18/01/2018, 12h32
  3. Algorithme de Ford-Fulkerson
    Par moujaprim dans le forum MATLAB
    Réponses: 31
    Dernier message: 04/02/2012, 17h43
  4. Algorithme de Ford Fulkerson
    Par camelia136 dans le forum MATLAB
    Réponses: 8
    Dernier message: 10/08/2011, 14h39
  5. Algorithme de Ford-Fulkerson
    Par Du Wassoulou dans le forum C++
    Réponses: 3
    Dernier message: 26/12/2010, 19h29

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