Répondre à la discussion
Affichage des résultats 1 à 20 sur 20

J'ai un problème avec les graphes (décomposition des flots)



  1. #1
    aiolia

    J'ai un problème avec les graphes (décomposition des flots)


    ------

    Dans un cours sur les graphes (problème de flots), l'auteur donne tout d'abord la définition d'un flot, suivi du graphe suivant pour exemple : (graphe1.gif parmi les pièces jointes, je sais pas comment afficher une image)


    Ensuite, l'auteur parle de la décomposition des flots en citant le théorème suivant :

    "Tout flot non nul, à valeur positive ou nulle, peut s'écrire comme une combinaison linéaire à coéfficients positifs de flots dont dont chacun vaut 1 sur les arcs d'un circuit du graphe, et zéro sur tout autre arc."

    Non seulement je ne comprend pas un traitre mot de cet énoncé, mais je ne comprend pas non plus l'exemple qu'on nous donne qui est le suivant (graphe2.gif dans les pièces jointes).


    Si vous pouviez éclairer ma lanterne, ce serait sympa. D'autant plus qu'après ça se corse et si déjà je ne comprend pas le début je risque d'avoir des problèmes pour la suite. Merci d'avance.

    -----
    Images attachées Images attachées

  2. Publicité
  3. #2
    sylvun1

    Question Re : J'ai un problème avec les graphes (décomposition des flots)

    Il doit y avoir moyen de déduire la signification du théorème... si je connaissais la définition d'un flot !

  4. #3
    matthias

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Bon jamais étudié les flots, mais en lisant ce document http://roso.epfl.ch/cours/optimisati...phes-flots.pdf ça m'a l'air si terrible
    C'est un peu comme si on demandait de démontrer que toute matrice est une combinaison linéaire de matrices dont un seul coefficient est non nul (et vaut 1 en l'occurence).

  5. #4
    martini_bird

    Re : J'ai un problème avec les graphes (décomposition des flots)

    En effet, je comprends aussi l'énoncé ainsi.

    Mais je ne comprends pas l'exemple: puisqu'il y a huit arcs, on devrait avoir huit coefficients, non?

  6. #5
    aiolia

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Ben c'est aussi mon problème, grosso modo je comprend à peu près l'énoncé (en fait y' rien à comprendre, il suffit de le lire), mais je ne comprend pas l'exemple. Je donne la définition d'un flot pour ceux qui ne la connaisse pas :

    "Un flot dans un graphe est une valuation des arcs respectant la loi de conservation des flux (dite aussi loi de Kirchhoff) : Pour tout sommet s, la somme des valuations des arcs d'origine s (flux sortant de s) est égale à la somme des valuations des arcs de but s (flux entrant)". Bon en gros, la somme des valuations des arcs entrant dans un sommet est égale à la somme des valuations des arcs sortant de ce sommet.

    Si quelqu'un a réussi à comprendre l'exemple, qu'il me l'explique parce que j'y comprend vraiment que dalle. Merci d'avance.

  7. A voir en vidéo sur Futura
  8. #6
    matthias

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Tu es sûr(e) de ta définition ?
    Parce que dans le document que j'ai cité, ta définition correspond plutôt à une circulation. Et pour un flot dont tous les coefficients sauf 1 sont nuls, la conservation ne peut pas être respectée.
    Mais bon moi je dis ça, c'est la première fois que j'entends parler de flots ...

  9. Publicité
  10. #7
    martini_bird

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Ok, y'a compris:

    il faut penser en terme de circuits (fermés) et non en terme d'arcs: le premier circuit est ABSE (pondéré par 3), le second ECSB (2), le troisième ECABS (2) et le dernier ABC (2) qui est "interne" (ne relie pas E à S).

    Ca va mieux?

  11. #8
    matthias

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Ah oui, j'avais mal lu
    C'est 1 sur tous les arcs d'un circuit et 0 sur les autres arcs ...

  12. #9
    martini_bird

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Citation Envoyé par matthias
    Ah oui, j'avais mal lu
    C'est 1 sur tous les arcs d'un circuit et 0 sur les autres arcs ...
    On était deux...

  13. #10
    matthias

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Citation Envoyé par martini_bird
    Ok, y'a compris:

    il faut penser en terme de circuits (fermés) et non en terme d'arcs: le premier circuit est ABSE (pondéré par 3), le second ECSB (2), le troisième ECABS (2) et le dernier ABC (2) qui est "interne" (ne relie pas E à S).

    Ca va mieux?
    encore mieux si le second est ECS et pas ECSB

  14. #11
    aiolia

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Citation Envoyé par martini_bird
    Ok, y'a compris:

    il faut penser en terme de circuits (fermés) et non en terme d'arcs: le premier circuit est ABSE (pondéré par 3), le second ECSB (2), le troisième ECABS (2) et le dernier ABC (2) qui est "interne" (ne relie pas E à S).

    Ca va mieux?
    Heu, je suis probablement un gros boulet, parce que je ne sais pas ce que signifie "pondéré par quelque chose" (enfin dans le cas d'un circuit). Si tu pouvais éclairer ma lanterne ...

  15. #12
    matthias

    Re : J'ai un problème avec les graphes (décomposition des flots)

    pondéré = multiplié par un coefficient
    en gros si tu appelles ABSE, ECS, ABSEC, ABC, les flots pour lesquels les valuations valent 1 sur les arcs des cycles du même nom et 0 sur les autres arcs, tu as :
    Flot total = 3.ABSE + 2.ECS + 2.ABSEC + 2.ABC

    Et donc dans ton exemple l'erreur est 7 = 3 + 2 + 2 + 0, et non pas 7 = 3 + 2 + 2, puisque l'arc SE n'est pas dans le cycle ABC

  16. Publicité
  17. #13
    matthias

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Ce que j'ai écrit n'est pas hyper rigoureux, l'équation concernant les vecteurs de flots. Mais tu obtiens une équation identique pour chaque composante et donc pour chaqe flot.

  18. #14
    martini_bird

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Citation Envoyé par matthias
    encore mieux si le second est ECS et pas ECSB
    C'était pour voir si tu suivais.

    Merci.

  19. #15
    aiolia

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Citation Envoyé par matthias
    pondéré = multiplié par un coefficient
    en gros si tu appelles ABSE, ECS, ABSEC, ABC, les flots pour lesquels les valuations valent 1 sur les arcs des cycles du même nom et 0 sur les autres arcs, tu as :
    Flot total = 3.ABSE + 2.ECS + 2.ABSEC + 2.ABC

    Et donc dans ton exemple l'erreur est 7 = 3 + 2 + 2 + 0, et non pas 7 = 3 + 2 + 2, puisque l'arc SE n'est pas dans le cycle ABC
    Merci pour tes explications, mais c'est justement là où je bloque : Qu'appelles-tu "flot total" ? Et de manière générale, comment représente-tu un flot ? Par un vecteur ? Un scalaire ? Je n'ai pas très bien compris l'histoire d'ajouter des flots. En vous lisant tous, j'ai l'impression que j'ai de sérieuses lacunes, mais pourtant le cours est sensé être adapté à ceux qui n'ont pas de pré-requis dans cette matière.

    Merci d'avance

  20. #16
    matthias

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Je veux bien admettre que mes explications ne sont pas très claires étant donné que j'ai découvert cette terminologie de flots avec ton post. Cela dit le document dont j'ai posté le lien me semble pas mal, quoique très succinct.

    En gros, le flot c'est juste une valeur attribué à un arc.
    On note Xi,j le flot associé à l'arc (i;j) (donc reliant i et j, de i vers j)
    A noter qu'il peut exister un arc (i;j) et un arc (j;i) étant chacun associé à un flot différent.
    Maintenant la liste des Xi,j est le vecteur de flots. On peut le représenter par un vecteur ou par une matrice ou n'importe quoi, ce n'est pas très important pour l'instant.
    Ce que moi j'ai fait, c'est ajouter des vecteurs de flots, ce qui n'est évidemment faisable que pour des graphes identiques, et qui revient à dire que pour un arc donné, le flot résultant est la somme des flots associés à cet arc. Tu peux aussi multiplier un vecteur de flots par un scalaire (tu multiplies alors tous les flots par ce même scalaire) et donc faire des combinaisons linéaires de vecteurs de flots.

    Dans l'exemple donné, on associe à chaque circuit un vecteur de flots tel que les flots sont égaux à un sur les arcs du circuit et égaux à 0 sur les autres arcs. Ensuite on fait la combinaison linéaire.

    C'est plus clair ?
    Si la notion de vecteur te dérange, considère juste que tu fais la même combinaison linéaire sur les composantes, chaque composante correspondant à un arc.

  21. #17
    aiolia

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Citation Envoyé par matthias
    Je veux bien admettre que mes explications ne sont pas très claires étant donné que j'ai découvert cette terminologie de flots avec ton post. Cela dit le document dont j'ai posté le lien me semble pas mal, quoique très succinct.

    En gros, le flot c'est juste une valeur attribué à un arc.
    On note Xi,j le flot associé à l'arc (i;j) (donc reliant i et j, de i vers j)
    A noter qu'il peut exister un arc (i;j) et un arc (j;i) étant chacun associé à un flot différent.
    Maintenant la liste des Xi,j est le vecteur de flots. On peut le représenter par un vecteur ou par une matrice ou n'importe quoi, ce n'est pas très important pour l'instant.
    Ce que moi j'ai fait, c'est ajouter des vecteurs de flots, ce qui n'est évidemment faisable que pour des graphes identiques, et qui revient à dire que pour un arc donné, le flot résultant est la somme des flots associés à cet arc. Tu peux aussi multiplier un vecteur de flots par un scalaire (tu multiplies alors tous les flots par ce même scalaire) et donc faire des combinaisons linéaires de vecteurs de flots.

    Dans l'exemple donné, on associe à chaque circuit un vecteur de flots tel que les flots sont égaux à un sur les arcs du circuit et égaux à 0 sur les autres arcs. Ensuite on fait la combinaison linéaire.

    C'est plus clair ?
    Si la notion de vecteur te dérange, considère juste que tu fais la même combinaison linéaire sur les composantes, chaque composante correspondant à un arc.
    Merci, en fait je n'avais pas vraiment lu attentivement ce document. Par contre maintenant j'ai un autre problème concernant les flots, cette fois-ci avec l'algorithme de Ford-Fulkerson pour l'optimisation d'un flot :
    Voici l'algo en question :

    On suppose donné un flot compatible associant à tout arc s->t une valuation f(s->t). L'algorithme de Ford-Fulkerson consiste à marquer les sommets de façon à determiner si le flot est maximal et, sinon, à indiquer une façon de l'augmenter.

    Algorithme de marquage :

    marquer + le sommet entrée;
    Répéter
    Pour tout sommet marqué s non encore traité
    Pour tout arc s->t
    Si t n'est pas marqué et s->t n'est pas saturé ALORS
    marquer t par (+,s)
    Fin Si
    Fin Pour
    Pour tout arc s->t
    Si t n'est pas marqué et t->s n'est pas antisaturé alors
    marquer t par (-,s)
    Fin Si
    Fin Pour
    Tant qu'on marque de nouveaux sommets;

    SI le sommet sortie n'est pas marqué Alors
    le flot est maximal
    SINON
    augmenter le flot
    Fin Si


    Ensuite, le shéma qu'on nous montre pour illuster cet algorithme est le graphe.gif (pièce jointe).
    Or, lorsque l'on traite le sommet B, on passe en revue tous les arcs sortants ainsi que tous les arcs entrants.
    A->B est un arc entrant qui n'est pas encore marqué à cet endroit de l'algo et qui, de plus, n'est pas antisaturé (c'est à dire que la valeur du flot n'est pas égale au flot minimal qui est ici 0). On devrait donc en toute logique marquer le sommet A par (-,B) . Or, dans l'exemple, il n'est pas marqué. Je ne sais pas si c'est moi où l'auteur de ce cours qui a fait une erreur, mais si quelqu'un pouvait me donner son avis (erreur ou pas ?)
    Images attachées Images attachées

  22. #18
    matthias

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Après avoir fait des recherches pour savoir ce qu'était un flot compatible (c'est pénible on trouve des définitions assez différentes concernant les flots), j'ai tendance à croire que tu as raison. J'aurais moi aussi marqué le sommet A par (-,B), s'il est bien sous entendu que la borne minimale est 0.
    Je continue à chercher des exemples sur internet pour vérifier que j'ai bien compris, mais si tu as la réponse avant, n'hésite pas à l'envoyer, ça m'intéresse.

  23. Publicité
  24. #19
    matthias

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Je crois que j'ai la réponse. Le but est de trouver un chemin menant de la source au puits (ou de l'entrée à la sortie) capable d'augmenter le flot.
    Il ne sert à rien de marquer A, puisque quand tu augmenteras le flot tu utiliseras le chemin inverse SBCE. Il s'agit donc a priori d'une imprécision dans l'algorithme que tu peux corriger ainsi : s'arrêter dès que le puits (sortie) est marqué.
    Une fois que B est marqué et que tu traite ce sommet, tu commences par les arcs sortant et donc tu marques le puits (+,B) et tu t'arrêtes.
    Ensuite tu calcules la valeur dont tu dois augmenter le flot (1 je pense dans ton exemple), tu effaces les marquages et tu recommences le marquage pour vérifier si le flot est maximal.

    ça te paraît correct ?

  25. #20
    aiolia

    Re : J'ai un problème avec les graphes (décomposition des flots)

    Citation Envoyé par matthias
    Je crois que j'ai la réponse. Le but est de trouver un chemin menant de la source au puits (ou de l'entrée à la sortie) capable d'augmenter le flot.
    Il ne sert à rien de marquer A, puisque quand tu augmenteras le flot tu utiliseras le chemin inverse SBCE. Il s'agit donc a priori d'une imprécision dans l'algorithme que tu peux corriger ainsi : s'arrêter dès que le puits (sortie) est marqué.
    Une fois que B est marqué et que tu traite ce sommet, tu commences par les arcs sortant et donc tu marques le puits (+,B) et tu t'arrêtes.
    Ensuite tu calcules la valeur dont tu dois augmenter le flot (1 je pense dans ton exemple), tu effaces les marquages et tu recommences le marquage pour vérifier si le flot est maximal.

    ça te paraît correct ?
    Oui en effet, je m'étais un peu compliqué la vie en supposant qu'il ne fallait s'interesser qu'aux chemins optimisants (à priori facile à trouver sur un graphe simple mais probablement moins sur un graphe complexe) mais finalement ton explication me semble la plus simple et la plus logique. Tu devais t'en douter, je ne suis pas très à l'aise en math

    En tout cas, merci d'avoir passé du temps là dessus, ça m'a permis d'y voir un peu plus clair.

Discussions similaires

  1. J'ai un problème avec les Reactions chimiques
    Par Invaders113 dans le forum Chimie
    Réponses: 1
    Dernier message: 16/12/2007, 10h12
  2. j'ai un problème avec les Séismes!!!
    Par djydji dans le forum Géologie et Catastrophes naturelles
    Réponses: 1
    Dernier message: 23/11/2007, 06h33
  3. Théorie des graphes et graphes de liaisons
    Par Eogan dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 08/12/2006, 22h59
  4. Les graphes mélés avec des probabilités
    Par stefoufoune dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 03/05/2006, 11h16
  5. Problème sur les graphes
    Par stefouille31 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 04/02/2006, 14h10