Discussion :

[david1599]

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 ?

[Flodelarab]

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.

[david1599]

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)