Terminale ES 2016-2017
Kartable
Terminale ES 2016-2017

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 :

SommetABCDEF
Degré242321
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.

pub

Demandez à vos parents de vous abonner

Vous ne possédez pas de carte de crédit et vous voulez vous abonner à Kartable.

Vous pouvez choisir d'envoyer un SMS ou un email à vos parents grâce au champ ci-dessous. Ils recevront un récapitulatif de nos offres et pourront effectuer l'abonnement à votre place directement sur notre site.

J'ai une carte de crédit

Vous utilisez un navigateur non compatible avec notre application. Nous vous conseillons de choisir un autre navigateur pour une expérience optimale.