Enigme : quelle consigne pour le tracé de figure ?

[invite06fcc10b]

Reprenons le problème du tracé de figure où on ne doit pas lever le stylo et où on ne doit pas repasser 2 fois par le même segment.
Considérons le cas général avec une figure comportant un nombre n quelconque de sommets et représentant un graphe connexe (tout sommet est accessible depuis un autre sommet).
Comme il a été dit, pour qu'il y ait au moins 1 solution, il faut qu'il n'y ait pas plus de 2 sommets avec un nombre impair d'arêtes.
Supposons qu'il y ait effectivement 2 sommets avec un nombre impair d'arêtes et que tous les autres en aient un nombre pair non nul. Le départ et l'arrivée du tracé seront les 2 sommets ayant un nombre impair d'arêtes, ça on l'a compris, mais est-ce que cela suffit pour garantir la solution pour un graphe quelconque ?
La question est, plus précisément :
Quelle consigne simple pouvez vous donner à quelqu'un avant qu'il fasse son tracé pour être assuré qu'il n'arrive pas à un cul-de-sac et qu'il parvienne finalement à 1 des solutions possibles (en dehors du fait qu'il doive commencer par 1 des sommets avec un nombre impair d'arêtes) ?
-----

[Jeanpaul]

2 conditions doivent être nécessairement satisfaites : pas plus de 2 points impairs et aussi pas de régions isolées, non connectées aux autres.
Ca suffit pour que le problème soit soluble.
Pour simplifier, on relie les 2 points impairs, comme ça on peut partir d'où on veut, sans perdre en généralité.
Alors, on chemine. Si on est bloqué, c'est forcément au point de départ (la parité, toujours).
Alors de 2 choses l'une : ou bien on a tout fait ou bien il reste des traits non satisfaits. Mais comme il n'y a pas de zones isolées, c'est forcément qu'on est passé par un des points qui bordent un tel trait. Il suffit alors de boucler à partir de ce point dans la zone restante quand on y passe et éventuellement de recommencer.
Ca marche forcément.

[invite06fcc10b]

Pour simplifier, on relie les 2 points impairs, comme ça on peut partir d'où on veut, sans perdre en généralité.

C'est un autre problème, car on supprime les contraintes.

Alors, on chemine. Si on est bloqué, c'est forcément au point de départ (la parité, toujours).

Si on est bloqué, c'est que la consigne était mauvaise ou qu'elle n'était pas claire. Je repose donc la question : quelle consigne simple peut-on donner ?

(tu as bien compris le problème,mais je n'ai pas vu de consigne claire dans tes propos)

[invite06fcc10b]

Qu'on se comprenne bien, peut-être qu'il n'y a pas de consigne simple, mais je pose la question quand même ...

[A voir en vidéo sur Futura]

[invite06fcc10b]

Qu'on se comprenne bien, peut-être qu'il n'y a pas de consigne simple, mais je pose la question quand même ...

Hum, dans le cas général, ça me semble difficile.
Mais qu'en est-il du cas des graphes dits planaires, c'est à dire dont les connexions ne se croisent jamais, comme un réseau routier par exemple, chaque sommet correspondant à un croisement de route ?

[yat]

J'ai peut-être une méthode assez systématique : on commence par relier le point de départ et d'arrivée, par un chemin quelconque. Ensuite on cherche une boucle dans les segments restants (et qui passent par au moins un point du premier tracé... on devrait pouvoir démontrer qu'il y en a toujours), et on dévie le tracé original pour passer par cette boucle. Je pense qu'en itérant jusqu'à ce qu'il n'y ait plus de segments non parcourus, on devrait arriver à une solution à tous les coups sans le moindre tâtonnement.

[invite06fcc10b]

J'ai peut-être une méthode assez systématique : on commence par relier le point de départ et d'arrivée, par un chemin quelconque. Ensuite on cherche une boucle dans les segments restants (et qui passent par au moins un point du premier tracé... on devrait pouvoir démontrer qu'il y en a toujours), et on dévie le tracé original pour passer par cette boucle. Je pense qu'en itérant jusqu'à ce qu'il n'y ait plus de segments non parcourus, on devrait arriver à une solution à tous les coups sans le moindre tâtonnement.

Bien vu, ça me semble correct.

[Jeanpaul]

Et c'est très exactement ce que j'avais écrit.
Le fait de rajouter un lien entre les 2 points impairs ne change rien puisque de toute façon il faut partir d'un de ces points et arriver à l'autre. Simplement on revient au point de départ.

[yat]

Et c'est très exactement ce que j'avais écrit.

Désolé. En deuxième lecture et avec cet indice supplémentaire, oui, en effet... mais j'avais pas compris ça comme ça du tout la première fois... Mais bon, je saisis pas trop ce que tu dis sur le fait de se retrouver bloqué au point de départ.

[invité576543]

La réponse de Jean-Paul me semble claire et complète! Bloqué veut dire pas moyen de continuer, or ne pas pouvoir continuer veut dire qu'avant d'arriver il n'y avait qu'une arète menant à ce point, et, de par la partité, il y a un seul point comme cela: celui dont on est parti pour démarrer le cycle...

Cordialement,

[invite06fcc10b]

La réponse de Jean-Paul me semble claire et complète!

Désolé, mais on ne peut pas qualifier de "clair" quelque chose que 2 personnes n'ont pas comprises. De plus, ce n'est toujours pas très clair à mes yeux. En effet, en rajoutant une connexion entre le 1er et le dernier et en disant qu'on ne peut être bloqué que sur le 1er (ce que je comprend), ça veut dire qu'on s'autorise un chemin passant temporairement par cette nouvelle connexion. Or, ça, ça me parait hors-sujet, car on construit un chemin qui ne répond pas à la question. De plus, il faut finir sur un certain sommet, or en rajoutant la nouvelle connexion, on finit sur le sommet initial, donc on est vraiment sur un autre problème.
D'où l'incompréhension.

[invité576543]

Alors je me permets de réécrire l'algo décrit par Jean-Paul (l'algo est le même, seul le texte diffère!):

On relie les 2 points impairs par un chemin quelconque, le choix n'a pas d'importance. Après cette étape tous les points sans exception ont un nombre pair d'arêtes non encore utilisées.

Alors de 2 choses l'une : ou bien on a tout parcouru ou bien il reste des arêtes libres. Mais comme il n'y a pas de zones isolées, le chemin établi passe nécessairement par un des sommets d'une de ces arêtes libres.

On prend alors une arête non utilisée dont une extrémité est sur le chemin déjà tracé. Notons A cette extrémité. Et on chemine n'importe comment sur les arêtes non encore utilisées. Tôt ou tard on se retrouve en A. En effet la condition de parité implique qu'en tout autre point on peut continuer (passer via un point enlève deux arêtes, donc si on arrive sur un point via une arête, il y en a nécessairement une pour sortir, sinon le total est impair). Quand on se retrouve sur le point A, on insère le cycle dans le chemin établi à l'étape précédente.

S'il reste des arêtes libres, le même raisonnement s'applique, et on réitère. Et ce jusqu'à l'absence d'arête libre.

En espérant que cela est plus clair...

Amicalement,

Michel

[invite06fcc10b]

Alors je me permets de réécrire l'algo décrit par Jean-Paul (l'algo est le même, seul le texte diffère!):

En fait, c'est exactement l'algo de Yat !
Je viens de relire le texte initial de Jean Paul, et j'ai compris où se situe le malentendu. Il dit
<<Alors, on chemine. Si on est bloqué, c'est forcément au point de départ (la parité, toujours). >>

Or, pour moi (et pour Yat je suppose, d'après ses remarques), le point de départ, c'est le seul et unique point de départ qui a initialement 3 arêtes. Mais finalement, Jean Paul parlait du point de départ d'un cycle, pas du chemin !!!
2ème quiproquo, c'est quand il dit qu'il "relie les 2 points impairs" que j'ai interprété comme "on ajoute une nouvelle connexion entre les 2 sommets". Il parlait en fait d'une liaison par un chemin existant.
Bref, on aurait pu piger plus vite, mais il y avait quand même matière à confusion, non ?

[yat]

En fait, c'est exactement l'algo de Yat !

Tout à fait JeanPaul a envoyé son post dans le passé après avoir lu mon algo !

[invité576543]

En fait, c'est exactement l'algo de Yat !

Milles excuses, je n'avais pas vu le poste de Yat... Jean-Paul ajoutait quelques justifications que j'ai un peu &#233;labor&#233;es...

Michel

[invité576543]

Mais finalement, Jean Paul parlait du point de départ d'un cycle, pas du chemin !!!

C'est pour ça que j'ai inversé deux de ses paragraphes... Il justifiait après l'existence d'un point de départ de cycle

2ème quiproquo, c'est quand il dit qu'il "relie les 2 points impairs" que j'ai interprété comme "on ajoute une nouvelle connexion entre les 2 sommets". Il parlait en fait d'une liaison par un chemin existant.

En fait c'est peut-être bien la bonne interprétation (ce qui ramène à la recherche d'un parcours fermé). J'ai préféré l'autre...

Cordialement,

[invite446ab7a4]

Salut

Heu juste une petite pr&#233;cision (ou question s'il s'av&#232;re que je me prompe lol).
Pour que &#231;a marche il faut qu'il y ait 2 points avec un nombre d'arr&#234;tes impair, et pas 2 maximum!
Car s'il n'y en a qu'un,il me semble que le probl&#232;me n'ai pas de r&#233;ponses.

Votre avis ?

@+

[invité576543]

Salut

Heu juste une petite précision (ou question s'il s'avère que je me prompe lol).
Pour que ça marche il faut qu'il y ait 2 points avec un nombre d'arrêtes impair, et pas 2 maximum!
Car s'il n'y en a qu'un,il me semble que le problème n'ai pas de réponses.

Votre avis ?

@+

Soit 0, soit 2. Tous les autres cas n'admettent pas de solution.

Cordialement

[invite06fcc10b]

Soit 0, soit 2. Tous les autres cas n'admettent pas de solution.
Cordialement

De toute façon, avoir dans un graphe 1 seul sommet avec un nombre impair d'arêtes est impossible.
En effet, le nombre total de connexions est forcément pair puisqu'à chaque connexion X-Y, il existe Y-X.
Donc "au maximum 2" est une expression juste.

[invite446ab7a4]

Ha oui c'est juste .
J'ai parl&#233; trop vite, d&#233;sol&#233;.

allez @+