Les ponts de Königsberg

Shadows Asgard

Titre initial "Est-il possible de se promener dans cette ville en parcourant tous les ponts une et une seule fois ?"
[Le titre doit être informatif, mais bref. Tu as tout le corps du message pour développer. AD]

Bonjour, j'ai un problème concernant cet exercice 2.

Car pour la question 1) j'ai répondu non, car cela se voit sur le graphe, mais je ne sais pas ce qu'il était attendu comme réponse mathématique, cela suffisait de dire ''Non''?

Et pour la question 2 je suis totalement bloqué je ne vois pas du tout comment faire, pouvez-vous m'aider s'il vous plaît ?
Merci d'avance pour votre réponse
Bonne journée à vous
Cordialement.

noobey

Hello, tu n'as pas vu le théorème d'Euler pour les circuits Eulériens?

GaBuZoMeu

Bonjour,

"cela se voit" : que vois-tu sur le graphe qui te fait dire que non ?

Si un sommet du graphe n'est ni le début ni la fin de ma promenade, que peux-tu dire sur son dégré (le nombre d'arêtes-ponts dont il est l'une des extrémités) ?

Pour le 2) : si c'est possible, il suffit de donner un exemple pour répondre. Sinon, il faut là aussi donner un argument (autre que "j'ai essayé et je n'ai pas réussi").

Shadows Asgard

Hello Noobey, j'ai vu ce que je viens de joindre en pièce jointe à ce présent message, je n'ai pas vu le nom de ''théorème d'Euler pour les circuits Eulériens '' concrètement, mais peut-être que c'est ce que dans mon cours on appelle ''définition d'une chaîne eulérienne '' et ''condition nécessaire et suffisante d'existence d'une chaîne eulérienne / caractérisation des graphes eulériens ''.

Finalement j'ai tenté une réponse plus mathématique que de simplement répondre ''non'' pour la question 1, en disant que ce n'est pas possible de parcourir tous les ponts une seule fois car le graphe n'admet pas de chaîne eulérienne (c'est l'autre pièce jointe que j'ai jointe à ce présent message).
C'est correct et bien cela qu'il fallait faire pour la question 1 ?

Et pour la question 2 par contre je n'ai vraiment aucune idée, que faut-il faire ? Car pareil je pense que la réponse est ''non'' visuellement en regardant le graphe, mais je ne sais pas comment le justifier concrètement mathématiquement de manière sûre.

GaBuZoMeu

Pour le 2), tu penses à tort.

Shadows Asgard

Mais comment le démontrer pour la 2 GaBuZoMeu ?

GaBuZoMeu

En se promenant.

Shadows Asgard

C'est à dire, pouvez vous me montrer la rédaction de la réponse pour que j'ai un modèle, car je n'ai encore jamais fait d'exercice avec ce type de question s'il vous plaît ?

Math Coss

Oui c'est possible et voici un chemin : ADABD...

Shadows Asgard

Donc pour la réponse attendue c'est juste de donner un chemin comme ça en observant le graphe ? Il n'y a pas besoin de mobiliser de concept mathématiques comme je l'ai fait dans la question 1 comme je l'ai montré en pièce jointe dans mes précédents messages ?

Alain24

@Shadows Asgard  Simple logique et "bon sens" (notion subjective) : pour montrer que la réponse à 1) est faux il faut une preuve "claire" (autre notion subjective) : on peut essayer d'exhiber toutes les combinaisons de chemin possibles  et constater qu'aucun n'emprunte chaque pont une et une seul fois mais donner une preuve fondée sur le degré des sommets est plus élégant car cette preuve se généralise à d'autres graphes. Pour montrer que la réponse à 2) est vrai il suffit de donner un exemple et c'est d'autant plus facile que le graphe a peu d'arcs et de sommets.

GaBuZoMeu

Bonjour,

Si on a du mal à trouver un exemple, on peut se lancer dans la démonstration d'un résultat général :

Soit G un graphe fini tel qu'il existe un sommet relié par une arête à chacun des autres sommets. Alors on peut se promener dans le graphe G en parcourant chaque arête deux fois, une fois dans un sens et une fois dans l'autre.

bisam

@GaBuZoMeu : N'est-ce pas vrai de tout graphe connexe ? Il me semble qu'un simple parcours en profondeur (qui n'emprunte que les arêtes que l'on n'a pas encore vues, et ensuite les emprunte en sens inverse) règle la question.

Alain24

Le graphe $G$ est dit non orienté (un arc de $A$ vers $B$ se représente par la paire $\left\lbrace A,B\right\rbrace$). En remplaçant chaque paire $\left\lbrace A,B\right\rbrace$ par deux couples $(A,B)$ et $(B,A)$ on obtient un graphe orienté (l'arc qui joint $A$ et $B$ est remplacé par deux "flèches" : une de $A$ vers $B$ et l'autre de $B$ vers $A$. Il faut alors trouver un chemin qui utilise tous les arcs flèchés une et une seule fois en respectant le sens des flèches (faire un dessin). Personnellement j'arrive mieux à faire le 2) si j'oriente le graphe en doublant un arc par deux arcs orientés de sens opposés.