Devoir type n°2 (2 h) - Exercice 1

30 min
45
Le graphe ci-dessous représente le plan d'un parc : les sommets sont sept zones AA , BB , CC , DD , EE , FF et GG , et les arêtes sont les allées qui les relient.

Barème : 7 points
Question 1

Déterminer l'ordre du graphe, le degré de chaque sommet et le nombre d'allées du parc.

Correction
  • On appelle ordre\red{\text{ordre}} d'un graphe le nombre nn de sommets de ce graphe.
  • 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 graphe possède 77 sommets donc le graphe est d'ordre 77.
    D'où :
    La somme de tous les degrés est égale à : 2+4+3+2+3+4+4=222+4+3+2+3+4+4=22
    Il en résulte donc que :
    nombre d’areˆtes=222\text{nombre d'arêtes}=\dfrac{22}{2}
    Ainsi :
    nombre d’areˆtes=11\text{nombre d'arêtes}=11

    Le parc compte donc 1111 allées.
    Question 2

    Le graphe est-il connexe ? Est-il complet ?

    Correction
    Le graphe est connexe, en effet la chaîne suivante : A−B−C−D−E−F−GA-B-C-D-E-F-G passe par tous les sommets. Ainsi, deux sommets quelconques seront toujours reliés par une chaîne.
    Ce graphe n’est pas complet (AA et DD, par exemple ne sont pas adjacents).
    Question 3

    Le jardinier veut parcourir toutes les allées en passant une et une seule fois par chacune d'elles. Est-ce possible ? Si oui, préciser les zones de départ et d'arrivée et proposer un parcours.

    Correction
  • Un graphe connexe possède une chaıˆne euleˊrienne\red{\text{chaîne eulérienne}} si, et seulement si, le nombre de sommets de degré impair est égal à 00 ou 22.
  • Si le nombre de sommets de degré impair est égal à 22, alors les deux sommets de degré impair sont les extrémités de la chaîne eulérienne.
    • Le graphe est connexe et deux sommets seulement ont un degré impair (CC et EE), donc le graphe admet une chaîne eulérienne (entre CC et EE).
    Le jardinier doit partir de CC et arriver en EE (ou l'inverse). Par exemple : C−B−A−F−E−D−C−G−B−F−G−EC - B - A - F - E - D - C - G - B - F - G - E .
    Question 4

    On ajoute une allée entre les zones CC et EE (en rouge ci-dessous). Montrer que le jardinier peut alors parcourir chaque allée une et une seule fois en revenant à son point de départ, et proposer un tel parcours partant de AA .

    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.

    • Les sommets CC et EE passent de degré 33 à degré 44 : tous les sommets sont maintenant de degré pair, et le graphe est toujours connexe. Il admet donc un cycle eulérien.
    Par exemple : A−B−C−D−E−F−G−C−E−G−B−F−AA - B - C - D - E - F - G - C - E - G - B - 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.