Graphes eulériens : les ponts de Königsberg, les tracés d'un seul trait et les cycles - Exercice 3

20 min
35
Un musée comporte six salles AA , BB , CC , DD , EE et FF . Dans le graphe ci-dessous, une arête relie deux salles lorsqu'une porte permet de passer de l'une à l'autre.
Question 1

Donner le degré de chaque sommet, puis le nombre de portes du musée.

Correction
  • On appelle degreˊ\red{\text{degré}} d'un sommet le nombre d'arêtes dont ce sommet est une extrémité (les boucles étant comptées deux fois).
  • Dans un graphe, nous avons la relation suivante : nombre d’areˆtes=la somme des degreˊs des sommets2\text{nombre d'arêtes}=\dfrac{\text{la somme des degrés des sommets}}{2} .
    • Le degré d'une salle est le nombre de portes de cette salle. D'où :
    La somme de tous les degrés est égale à : 4+4+4+4+4+4=244+4+4+4+4+4=24
    Il en résulte donc que :
    nombre d’areˆtes=242\text{nombre d'arêtes}=\dfrac{24}{2}
    Ainsi :
    nombre d’areˆtes=12\text{nombre d'arêtes}=12

    Le musée compte donc 1212 portes.
    Question 2

    Un gardien veut faire sa ronde en franchissant chaque porte une et une seule fois, et en revenant à son point de départ. Est-ce possible ?

    Correction
  • Un graphe connexe admet un cycle euleˊrien\red{\text{cycle eulérien}} si, et seulement si, tous ses sommets ont un degré pair.
    • Le graphe est connexe, en effet la chaîne suivante : A−B−C−E−D−FA-B-C-E-D-F passe par tous les sommets. Ainsi, deux sommets quelconques seront toujours reliés par une chaîne.
    Tous les sommets sont de degré 44 , donc pair : le graphe admet un cycle eulérien.
    Ainsi :
    la ronde est possible

    Question 3

    Proposer une telle ronde partant de la salle AA .

    Correction
    Par exemple : A−B−C−A−D−E−F−D−B−E−C−F−AA - B - C - A - D - E - F - D - B - E - C - F - A .

    Signaler une erreur

    Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

    Connecte-toi ou crée un compte pour signaler une erreur.