Démonstration intéressante, théorie des graphes.

[Ignae]

Bonjour,
depuis quelques temps je bloque sur une démonstration d'un théorème dans le cadre d'un cours de théorie & algorithmique des graphes. Il s'agit d'un énoncé simple.

Les différents dessins peuvent aider à la compréhension de mes propos.

La proposition à démontrer est :
Hypothèses: On prend un ensemble de n points que l'on relie grâce à des lignes à n autres points. Ces lignes peuvent prendre trois couleurs et ne sont pas nécessairement de couleur unie. Une ligne peut donc être constituée de plusieurs segments de couleurs différentes.



L'opération que l'on peut effectuer: Si l'on a un tracé de couleur unie qui relie un point du premier ensemble à un point du second ensemble, on peut intervertir les deux autres couleur d'un des deux coté du tracé.



Proposition à démontrer: Il est toujours possible après une suite finie de cette opération d'obtenir uniquement deux couleurs pour les tracés qui relient des points du premier ensemble au second ensemble.


J'ai une démonstration qui tient la route si l'on ne démarre que avec des lignes de couleur unie. Après je bloque. Des idées ? Une façon intuitive de voir que c'est possible dans tous les cas ? Une idée par ou commencer ?

Merci d'avance.

[noix07]

j'ai pas compris: "on peut intervertir les deux autres couleurs d'un des deux cotés du tracé"

[Doraki]

Si t'as un chemin d'une seule couleur qui va du haut vers le bas,
par exemple le segment vert au milieu (mais j'imagine qu'on est pas forcé d'aller tout droit),
tu peux échanger la couleur rouge/noir d'un coté du chemin.

Si j'ai bien compris il faut faire des échanges jusqu'à ce qu'il n'y ait plus aucun chemin du haut vers le bas qui utilise 3 couleurs.

[Ignae]

C'est exactement ça Doraki

Alors quelques observations pour ceux que cela intéresse:

Définition: Un chemin est une suite de segments reliés entre eux, avec le premier segment commencant en haut et le dernier terminant en bas.
Définition: Un tracé est un chemin de couleur unie.
Définition: Un sommet est le point d'intersection de deux chemin.

[list=]Faire un échange de couleurs autour d'un tracé, ne change que la 'structure' des chemins qui coupent ce tracé. Les autres chemins n'auront que leur couleurs intervertie, s'ils étaient de couleur unie, ils le resteront donc.
[/list]

[list=]Il est toujours possible de n'arriver qu'à des tracés qui ne se coupent pas.
[/list]

[nodjim]

Euh, si on a une configuration minimale, 3 droites qui ne se coupent pas, chacune une couleur différente, comment fait on pour obtenir 2 couleurs ?

[Ignae]

Les trois tracés ne se touchant pas:
[CENTER]rouge | noir | bleu
[/CENTER]
On prend le tracé du milieu et on interverti à gauche, on obtient:
[CENTER]bleu | noir | bleu
[/CENTER]

[nodjim]

D'accord. Maintenant, si 1 seule ligne tricolore ?
J'espère que c'est ma dernière question, ça permet de bien cerner le problème.

[Ignae]

Alors ce n'est pas un tracé et il n'y a donc pas de problème puisque cela ne relie pas le haut avec le bas ;)

Ce qu'il faut démontrer ce qu'on à des tracés qui ne sont que de deux couleurs.

[Doraki]

par exemple dans ton dessin, on a un tracé rouge, deux tracés verts et deux tracés noirs.
donc si on intervertit rouge/vert à gauche du tracé noir de gauche, ça casse le tracé rouge et on a gagné ?

[Ignae]

Exactement. =D

[Ignae]

Alors personne n'a d'idées ? C'est tellement complexe ?

[Doraki]

J'imagine qu'on a jamais 3 segments concourants en un points ?

Si tu as une intersection où une couleur A fait un coude et où les deux autres traits sont de couleurs B et C distinctes, ben de toutes façons tu pourras jamais changer cette situation.
Donc autant supprimer les deux bouts B et C, ils ne pourront jamais faire partie d'un "tracé".
Ca simplifie un peu le problème.

Les tracés potentiels sont alors clairement visibles (c'est les chemins qui vont tout droit dans les intersections), et on a un truc qui ressemble à ce que t'as fait dans ton dessin.