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

[aiolia]

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

[invitecd48d721]

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

[matthias]

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

[martini_bird]

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?

[A voir en vidéo sur Futura]

[aiolia]

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.

[matthias]

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

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

[matthias]

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

[martini_bird]

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

[matthias]

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

[aiolia]

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

[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

[matthias]

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.

[martini_bird]

encore mieux si le second est ECS et pas ECSB

C'était pour voir si tu suivais.

Merci.

[aiolia]

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

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

[aiolia]

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

[matthias]

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.

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

[aiolia]

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.