On considère le graphe G à 6 sommets { 1 , 2 , 3 , 4 , 5 , 6 } dont les arêtes sont : 12 , 13 , 14 , 23 , 24 , 25 , 34 , 35 , 36 , 45 , 46 , 56 . Donner le degré de chaque sommet. Énoncer le théorème de Dirac et l'appliquer. Exhiber un circuit hamiltonien. Ce graphe admet-il un cycle eulérien ?

Existence d'un circuit hamiltonien — critère de Dirac

Difficile Inspiré BAC France

Exercice inspiré d'un BAC France

Énoncé et solution adaptés au programme français. Voir crédits.

Énoncé

On considère le graphe $G$ à 6 sommets ${1, 2, 3, 4, 5, 6}$ dont les arêtes sont : $12, 13, 14, 23, 24, 25, 34, 35, 36, 45, 46, 56$ .

Donner le degré de chaque sommet.
Énoncer le théorème de Dirac et l'appliquer.
Exhiber un circuit hamiltonien.
Ce graphe admet-il un cycle eulérien ?

Indices

— clique pour révéler

1 Indice 1

Pour la question 1, comptez pour chaque sommet le nombre d'arêtes qui lui sont reliées dans la liste donnée.

2 Indice 2

Pour la question 2, le théorème de Dirac dit que si tous les degrés sont au moins égaux à $n/2$ (avec $n$ le nombre de sommets), le graphe possède un circuit hamiltonien : comparez chaque degré trouvé à $n/2$.

3 Indice 3

Pour la question 4, souvenez-vous qu'un graphe admet un cycle eulérien si et seulement si tous ses sommets ont un degré pair.

Bloqué sur cet exercice ?

Léo peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Demander à Léo

Exercice Terminé? 🎉

Validez votre réponse pour enregistrer votre progression et gagner des points

Distribution stationnaire — Chaîne à deux états Retour au chapitre Réseau d'amis et matrice d'adjacence

Existence d'un circuit hamiltonien — critère de Dirac

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Existence d'un circuit hamiltonien — critère de Dirac

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Valider votre réponse

Tu as vu 5 exercices aujourd'hui 🎯