93 Etude de graphes eulériens 1. Une première approche Le dessin ci-contre peut être tracé sans lever le crayon et sans repasser plus d'une fois sur le même trait, c'est-à-dire que l'on peut trouver une chaîne qui emprunte chaque arête du graphe une et une seule fois. Une telle chaîne est appelée une chaîne eulérienne, si de plus celle-ci est fermée, il s'agit d'un cycle eulérien. a) Parmi les dix graphes connexes ci-dessous, lesquels admettent une chaîne eulérienne, et dans ce cas, dire s'il s'agit d'un cycle eulérien. A G₂ G₁ M GA Gg) A b) Déterminer le nombre de sommets de degré impair de chacun de ces graphes, puis émettre une conjecture pour qu'un graphe connexe admette une chaîne eulérienne et plus précisément un cycle eulérien. On admet alors le théorème d'Euler suivant : Gs (G10) ● Un graphe connexe admet une chaîne eulérienne si, et seulement si, le nombre de sommets de degré impair est 0 ou 2. De plus, les extrémités de cette chaîne sont les sommets de degré impair s'ils existent. • Un graphe connexe admet un cycle eulérien si, et seulement si, tous ses sommets sont de degré pair. 3. Les sept ponts de Königsberg Ce problème, résolu par Euler en 1741, a donné naissance à la théo- rie des graphes: 2. Jeu pour enfants On considère un espace de jeu réservé à des enfants. Les enfants peuvent se déplacer sur cinq plates- formes notées A, B, C, D et E. Ces plates-formes sont reliées entre elles par un certain nombre de rampes. On représente cet espace de jeu par le graphe G ci-contre. a) Peut-on partir de la plateforme C et rejoindre la plateforme E en utilisant toutes les rampes, et sans passer deux fois par la même rampe ? Si oui, proposer un tel chemin. b) Où peut-on placer une nouvelle rampe pour obtenir l'existence d'un chemin qui, partant d'une plate-forme donnée, emprunte une et une seule fois chaque rampe pour revenir à la plate-forme initiale ? Justifier la réponse. À Königsberg, en Poméranie, il y a une île appelée Kneiphof; le fleuve qui l'entoure se divise en deux bras, sur lesquels sont jetés les sept ponts a, b, c, d, e, f, g. Cela posé, peut-on arranger son parcours de telle sorte que l'on ne puisse y passer qu'une seule fois ? a) Construire un graphe où les sommets sont les quatre rives A, B, C, D et les arêtes les sept ponts les reliant. b) Résoudre le problème. B A​