Personne ne s'interesse au graphe ?

Bonjour,

Je ne savais pas ce qu'est une chaîne (alternée) "M-augmentante". J'ai regardé la définition, et j'ai vu que le résultat était une conséquence à peu près immédiate de la définition.

Commence donc par rappeler la définition de chaîne M-augmentante. Fais un dessin, au besoin. Et demande toi le rapport qu'il y a entre le nombre d'arêtes dans M et le nombre d'arêtes en dehors de M le long de la chaîne M-augmentante. La première arête est-elle dans M ? La dernière arête est elle dans M ?

Merci de m'avoir répondu. Je savais pas que l'on pouvait aussi apellé ça chaine alterné.

Alors je remarque que la première et dernieres arêtes de v n'appartiennent pas à M. Après franchement même en faisant un dessin je ne vois pas trop. J'ai l'impression que ||P\M|-|M||1. Mais honnêtement je n'en suis pas sur et je ne vois pas ou cela méne.

Maintenant il s'agirait de calculer |M\P|. Et là je vois pas. Pour moi tout est possible là.

Je t'ai demandé une chose :

Commence donc par rappeler la définition de chaîne M-augmentante.

Pourrais-tu le faire ? Au moins pour vérifier qu'on parle bien de la même chose.

Bien sur pas de soucis (je croyais que tu me disais de faire ça chez moi au broullion pour que ce soit plus clair).

D'après mon cours j'ai les définitions suivantes:

Soit G=(V,E) un graphe non orienté connexe.

Couplage:
Un ensemble d'arêtes M est un couplage si on ne peut pas trouver deux arêtes e et e' dans M incidentes à un même sommet.

Points couplés
Tout sommet vV tel qu'il existe wV tel que {v,w}M est dit couplé par M.

À partir de maintenant on note M un couplage.

chaîne M-alternante
Une chaîne élémentaire est M-alternante si elle est composée alternativement d'arêtes de E\M et M.

Chaîne M-augmentante
Une chaîne élémentaire est M-augmentante si elle est M_alternante et telle que ses deux sommets extrémités ne sont pas couplés par M.


Je dois montrer la proposition suivante:

Soit G=(V,E) un graphe non orienté connexe et M un couplage. Soit v une chaîne M-augmentante et P l'ensemble des arêtes de v. On note M'=MP=(M\P)(P\M). Alors, |M'|=|M|+1.

Une chaîne élémentaire est M-alternante si elle est composée alternativement d'arêtes de E\M et M.

Alors, ça ne fait pas tilt ?

Quel rapport y a-t-il entre le nombre d'arêtes dans M et le nombre d'arêtes en dehors de M le long de la chaîne M-augmentante. Si tu ne vois pas, dessine une chaîne M-augmentante en coloriant en rouge les arêtes de la chaîne qui sont dans M et en bleu celles qui ne sont pas dans M. Quelle est la différence entre le nombre d'arêtes bleues et le nombre d'arêtes rouges ?

Hum j'avais répondu quelque chose tout à l'heure mais maintenant ça me semble faux. Je referais un dessin demain parce que là il est tard. Ce qui me pose problème c'est que l'on peut sortir à tout moment du couplage (je sais pas si ce que je dis est clair). Je veux dire la chaîne M-alternante n'est pas obligé de contenir toutes les arêtes de M.

Si on passe uniquement par une arête de M (i.e la chaine ne contient qu'1 arête de M) on a |P\M|=2
Si on passe uniquement par deux arêtes de M on a |P\M|=3
...et ainsi de suite.

Mais je vois pas de lien direct entre |M| et |P\M|.
Ca doit être facile pourtant mais sérieux je dois pas être doué.

Bon je continuerais à réfléchir demain matin sur ça.

Merci et bonne soirée.

Peut-être ne vois-tu pas clairement ce qu'est une chaîne ? Qu'est-ce qu'une chaîne ?

Peut-être aussi ne vois-tu pas ce que fait la différence symétrique ?

Ok à mon avis quelque chose ne va pas dans ma définition. Bon déjà la différence symétrique c'est l'ensemble des arêtes qui appartiennent à M ou à  mais pas aux deux.

A partir de là j'ai fait le graphe suivant:

G=(V,E) avec V={1,...,9} et E={{1,2},{1,3},{2,5},{3,5},{3,4},{4,5},{5,6},{5,7},{6,7},{7,8},{8,9}}
M={{1,3},{4,5},{7,8}} donc |M|=3

Maintenant mes 3 chaînes M-augmentante:

₁=2{2,1}1{1,3}3{3,4}4{4,5}5{5,6}6 et donc |M'₁|=3 problème
₂=9{9,8}8{8,7}7{7,6}6 et donc |M'₂|=2 problème
₃=9{9,8}8{8,7}7{7,5}5{5,4}4{4,3}3{3,1}1{1,2}2 et donc |M'₃|=4 donc là ok la proposition est vraie.


Donc là je ne comprend plus rien.

Oui, visiblement ton problème est que tu ne comprends pas "différence symétrique", ou du moins que tu n'appliques pas correctement la définition.

Voici ton graphe, ton couplage (arêtes en rouge), ta chaîne (arêtes avec triple barre). Qu'est-ce que ?

bah M'₁ c'est {{2,1},{3,4},{5,6},{7,8}} oui j'ai un peu de mal avec la différence symétrique. Je crois que tout à l'heure j'avais oublié de compter l'arête {7,8}.