Graphes

Chaîne eulérienne - Exercice 3

5 min
15
On considère le graphe Γ\Gamma représenté ci-dessous :
Question 1

Ce graphe admet-il une chaîne eulérienne?

Correction
  • Un graphe connexe possède une chaıˆne euleˊrienne\red{\text{chaîne eulérienne}} si, et seulement si, le nombre de sommets de degré impair est égal à 00 ou 22.
  • Si le nombre de sommets de degré impair est égal à 22, alors les deux sommets de degré impair sont les extrémités de la chaîne eulérienne.
    • Dans un graphe non orienté, le degré d'un sommet du graphe est le nombre d'arêtes issues de ce sommet. D'où :
    Le graphe est connexe et deux sommets seulement ont un degré impair (DD et GG), donc le graphe admet une chaîne eulérienne (entre DD et GG).
    Question 2

    Donner alors une chaine eulérienne possible.

    Correction
  • Le graphe est connexe et contient seulement deux sommets de degré impair donc il existe une chaîne eulérienne commençant par un des deux sommets de degré impair (DD ou GG) et finissant par le deuxième sommet de degré impair.
    • Le graphe Γ\Gamma admet une chaîne eulérienne.
    Par exemple D−C−A−B−C−F−G−D−F−E−B−D−E−GD - C - A - B - C - F - G - D - F - E - B - D - E - G.