Discussion :

[Pluplume]

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

[Flodelarab]

Bonjour

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" ?

oui.

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 !

[Jipété]

graphe flox maximal ford fulkerson

C'est quoi un flox ?

[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 ?

[Pluplume]

C'est quoi un flox ?

oups désolé faute de frappe il faut comprendre "flot"

[Jipété]

oups désolé faute de frappe il faut comprendre "flot"

Ok merci.

[tbc92]

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 ?

[Flodelarab]

Sachant que la question de l'exercice est : calculer le flot maximal entre a et t

Ah ! L'art de faire un bon schéma pour poser un problème
Effectivement, tu mets la source avant A, et non S.

D’où mon flot maximal de 3.

Vous confirmez mon calcul ?

Oui.
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.

[Pluplume]

à vous pour toutes ces explications !!! (et dire que ça fait trois heures que je suis sur cette question

[Flodelarab]

À 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)

[Pluplume]

À 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

[Flodelarab]

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 ?

Par contre ma deuxième question est : donnez une instanciation du flot maximal ,

"instanciation" ? "instanciation" est le fait de créer une instance. Veut-on une instance ou une instanciation ?

un flot maximum de 3

Même un flot complet maximal n'est pas unique.
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.

[Pluplume]

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 ?
[/LIST]

J'ai demandé confirmation à mon prof et la source est bien derrière A. Il m'a dit c'est fait exprès ...

"instanciation" ? "instanciation" est le fait de créer une instance. Veut-on une instance ou une instanciation ?

Même un flot complet maximal n'est pas unique.
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.

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 ?

[tbc92]

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 ...

[Flodelarab]

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.

[Pluplume]

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 ...

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

si on sature les arcs directs avec un flot exotique. On revient à la version simple.

Euh tu entends quoi par flot exotique ? (j'ai cherché sur internet mais google ne connait pas )

[dourouc05]

Euh 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 technique .)

[Pluplume]

Ç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