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
Discussion :
[Graphe] Flot maximal par l'algorithme de Ford-Fulkerson
Bonjour,
Petite question sur le calcul du flot maximal selon l'algo de Ford Fulkerson.
Sur le graphe ci-joint, j'ai tracé un chemin entre les sommets a et t (flèche bleue)
Ma question est :
Est- ce que j'ai le droit de passer par le sommet t pour y revenir par la suite tout en sachant que c'est mon"puits" ?
Merci à vous
Pluplume
Bonjour
oui.Est- ce que j'ai le droit de passer par le sommet t pour y revenir par la suite tout en sachant que c'est mon"puits" ?
Un puits dont l'eau ressort n'est pas un puits.
Le fait est que, sur ton dessin, il n'y a ni source, ni puits.
Il n'y a que des nœuds. (même S, même T)
Il faut considérer :
- une source à gauche de S avec une flèche (quantité infinie) vers S
- un puits à droite de T avec une flèche (quantité infinie) de T vers ton puits.
Après, pour Ford-Fulkerson, je ne vois pas de problème. Ça va marcher.
En avant !
- une source à gauche de S avec une flèche (quantité infinie) vers S
- un puits à droite de T avec une flèche (quantité infinie) de T vers ton puits.
Merci pour votre réponse
Sachant que la question de l'exercice est : calculer le flot maximal entre a et t
En suivant vos indications cela me parait un peu trop simple
Si je ne dis pas de bêtises du coup le flot maximal est de 3
En considérant que ma source est en haut de a alors je ne peux pas avoir plus de 3 en flot entrant et donc obligatoirement 3 en flot sortant sur t qui sort vers le puits.
D’où mon flot maximal de 3.
Vous confirmez mon calcul ?
Ah ! L'art de faire un bon schéma pour poser un problèmeEnvoyé par Pluplume
Effectivement, tu mets la source avant A, et non S.
Oui.D’où mon flot maximal de 3.
Vous confirmez mon calcul ?
Tu n'as quasiment pas un graphe, vu sous cet angle, puisque le seul chemin possible est source-A-D-T-puits.
Les chemins (suite d'arcs directs) sont immédiatement saturés sans alternatives.
Les chaînes (suite d'arcs, directs ou inverses) ont des arcs inverses déjà saturés (à 0).
Le flot complet maximal est 3.
à vous pour toutes ces explications !!! (et dire que ça fait trois heures que je suis sur cette question
À la réflexion, j'ai dit une bêtise :
Il y a des tas d'alternatives de chemin.
Mais la tentative de trouver des alternatives biscornues sera détruite par la saturation des arcs inverses.
Et tu aboutiras à source-A-D-T-puits comme seul flot.
Un chemin biscornu peut être "source A D T C E B S B A D T puits" (avec un flot de 1)
C'est quoi un flox ?
oups désolé faute de frappe il faut comprendre "flot"C'est quoi un flox ?
Ok merci.oups désolé faute de frappe il faut comprendre "flot"
La source est le point a ?
On a donc une source a , un puis t, et 4 noeuds quelconques b,c,d,s.
C'est surprenant.
En terme de notation, en terme de difficulté de l'exercice, ce serait plus cohérent si on avait une source s, un puits t, et 4 sommets quelconques a,b,c,d.
Et dans ce cas le flux maximal est ?
Répondre avec citation
Partager