Graphes

Chaîne eulérienne - Exercice 1

3 min
5
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 (AA et DD), donc le graphe admet une chaîne eulérienne (entre AA et DD).