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 !
C'est quoi un flox ?Envoyé par Pluplume
- 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 ?
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 ?
Ah ! L'art de faire un bon schéma pour poser un problème
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)
D'accord donc peu importe le chemin j'arriverais à un flot maximum de 3 .
Par contre ma deuxième question est : donnez une instanciation du flot maximal , si je fais le graphe suivant est ce suffisant ou est ce que vous pensez que je dois passer par un chemin biscornues?Pièce jointe 462342
Que c'est bizarre ! Créer un beau graphe et poser des questions nouilles est difficile à croire.
Es-tu sur que la source est derrière A ?
As-tu inversé A et T ?
Autre ?
"instanciation" ? "instanciation" est le fait de créer une instance. Veut-on une instance ou une instanciation ?Par contre ma deuxième question est : donnez une instanciation du flot maximal ,
Même un flot complet maximal n'est pas unique.un flot maximum de 3
L'algorithme de Ford-Fulkerson ne sert qu'à trouver le nombre 3.
Pour une instance :
- Soit tu fais appel à ta créativité artistique et tu présentes n'importe quel flot qui aboutit à 3 dans le puits. (Rappel: ton graphe a des cycles ... )
- Soit tu présentes le flot auquel tu aboutis à la fin de Ford-Fulkerson.
J'ai demandé confirmation à mon prof et la source est bien derrière A. Il m'a dit c'est fait exprès ...
La question est : Donnez une instanciation de ce flot maximal sur le graphe ( C'est à dire donnez pour chaque arc le flot effectivement acheminé lorsque le flot maximal est réalisé. )
Quand tu dis "Veut-on une instance ou une instanciation " je ne comprend pas trop la différence ? pour l'instanciation est l'action qui permet d'avoir une instance? Donc mon 2ème graphe sera une instance de mon 1er graphe créer grâce à l'action d'instanciation ?
Instance ou instanciation : Flodelarab te taquine sur une question de langue française. Instance paraît plus adapté ici.
Quel chemin il faut proposer : Le prof attend la réponse ADT. Si tu veux l'embêter, tu peux proposer un autre chemin, en passant 13 fois par certaines boucles et 25 fois par d'autres boucles. Ainsi, le prof va devoir passer beaucoup de temps à vérifier si ta réponse est correcte. Comme ça, il va être bien énervé. A toi de voir si tu veux prendre ce risque.
Plus sérieusement, entre 2 réponses correctes, une réponse simple et une réponse tordue, il faut toujours choisir la réponse simple.
Ici tu peux aussi ajouter un commentaire : Le chemin le plus court de A vers T est le chemin ADT, de flot 3. On peut aussi trouver d'autres chemins plus longs, par exemple ...
Il m'a dit c'est fait exprès
L'intérêt pédagogique que je vois est de bien voir que la phase 2 détruit la phase 1 de Ford-Fulkerson, si on sature les arcs directs avec un flot exotique. On revient à la version simple.
Sinon je ne vois pas.
ADTCET va saturer en direct.
Et CET va disparaître en saturant les arcs inverses de ADTECT.
Ahaha en effet je veux pas prendre le risque je vais choisir la solution la plus simple
En tous cas merci d'avoir pris le temps de me répondre
Euh
si on sature les arcs directs avec un flot exotique. On revient à la version simple.tu entends quoi par flot exotique ? (j'ai cherché sur internet mais google ne connait pas
Ça m'étonnerait : http://www.cnrtl.fr/definition/exotique. Par extension, un flot "bizarre", si tu préfères. (Non, toute combinaison de mots dont l'un est technique n'est pas forcément techniqueEuh.)
Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.
Créer des applications graphiques en Python avec PyQt5
Créer des applications avec Qt 5.
Pas de question d'ordre technique par MP !
Ça m'étonnerait : http://www.cnrtl.fr/definition/exotique. Par extension, un flot "bizarre", si tu préfères. (Non, toute combinaison de mots dont l'un est technique n'est pas forcément technique
ah oui flot bizarre je comprends
Merci
Répondre avec citation
Partager