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

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.

Questions fréquentes

Quelles sont les matières disponibles sur Kartable ?

Sur Kartable, l'élève accède à toutes les matières principales de la primaire au lycée, y compris pour les spécialités et les options. Mathématiques, physique-chimie, SVT, sciences, français, littérature, histoire, géographie, enseignement moral et civique, SES, philosophie, anglais, allemand et espagnol.
Inscrivez-vous

Les cours sont-ils conformes aux programmes officiels de l'Education nationale ?

L'intégralité des cours sur Kartable est rédigée par des professeurs de l'Éducation nationale et est conforme au programme en vigueur, incluant la réforme du lycée de l'année 2019-2020.
Choisissez votre formule

L'élève peut-il accéder à tous les niveaux ?

Sur Kartable, l'élève peut accéder à toutes les matières dans tous les niveaux de son choix. Ainsi, il peut revenir sur les notions fondamentales qu'il n'aurait pas comprises les années précédentes et se perfectionner.
Plus d'info

Kartable est-il gratuit ?

L'inscription gratuite donne accès à 10 contenus (cours, exercices, fiches ou quiz). Pour débloquer l'accès illimité aux contenus, aux corrections d'exercices, mode hors-ligne et téléchargement en PDF, il faut souscrire à l'offre Kartable Premium.
Plus d'info

Qui rédige les cours de Kartable ?

L'intégralité des contenus disponibles sur Kartable est conçue par notre équipe pédagogique, composée de près de 200 enseignants de l'Éducation nationale que nous avons sélectionnés.
Afficher plus

Qu'est ce que le service Prof en ligne ?

L'option Prof en ligne est un service de chat en ligne entre élèves et professeurs. Notre Prof en ligne répond à toutes les questions sur les cours, exercices, méthodologie et aide au devoirs, pour toutes les classes et dans toutes les matières. Le service est ouvert du lundi au vendredi de 16h à 19h pour les membres ayant souscrit à l'option.
Choisissez votre formule