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

Mathématiques Discussion :

Non-terminaison de l'algorithme de Ford-Fulkerson


Sujet :

Mathématiques

  1. #1
    Candidat au Club
    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 sénior
    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
    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)