Se connecter
ou

En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. En savoir plus : Conditions générales d'utilisation

J'ai compris

Déterminer si un graphe admet une chaîne eulérienne ou un cycle eulérien

Un graphe connexe admet une chaîne eulérienne s'il a zéro ou deux sommets de degré impair. Il admet un cycle eulérien si tous ses sommets sont de degré pair.

On considère le graphe G suivant :

-

Déterminer si G admet un cycle eulérien ou une chaîne eulérienne.

Etape 1

Vérifier que le graphe est connexe

On vérifie que le graphe est connexe, c'est-à-dire que chaque couple de sommets du graphe est relié par une chaîne.

Chaque couple de sommets est relié par une chaîne. On en déduit que le graphe G est connexe.

Etape 2

Déterminer le degré de chacun des sommets

On détermine le degré de chacun des sommets.

On récapitule les résultats dans le tableau suivant le degré de chacun des sommets :

Sommet A B C D E F
Degré 2 4 2 3 2 1
Etape 3

Compter le nombre de sommets de degré impair

On compte le nombre de sommets de degré impair.

On remarque que G possède deux sommets de degré impair (D et F).

Etape 4

Rappeler le cours

On énonce le théorème d'Euler :

  • Un graphe connexe admet une chaîne eulérienne si et seulement s'il possède zéro ou deux sommet(s) de degré impair.
  • Un graphe connexe admet un cycle eulérien si et seulement s'il ne possède que des sommets de degré pair.

D'après le théorème d'Euler :

  • Un graphe connexe admet une chaîne eulérienne si et seulement s'il possède zéro ou deux sommet(s) de degré impair.
  • Un graphe connexe admet un cycle eulérien si et seulement s'il ne possède que des sommets de degré pair.
Etape 5

Conclure

On en conclut que le graphe admet une chaîne eulérienne ou un cycle eulérien.

On en conclut que le graphe G admet une chaîne eulérienne.

Identifie-toi pour voir plus de contenu

Pour avoir accès à l'intégralité des contenus de Kartable et pouvoir naviguer en toute tranquillité,
connecte-toi à ton compte. Et si tu n'es toujours pas inscrit, il est grand temps d'y remédier.