Modéliser une situation par un graphe - Exercice 1

15 min
20
Six villages AA , BB , CC , DD , EE et FF sont reliés par des routes. Pour chaque village, voici les villages auxquels il est relié directement par une route :
  • AA est relié à BB et CC ;
  • BB est relié à AA , CC et DD ;
  • CC est relié à AA , BB , DD et EE ;
  • DD est relié à BB , CC , EE et FF ;
  • EE est relié à CC , DD et FF ;
  • FF est relié à DD et EE.
Question 1

Représenter cette situation par un graphe.

Correction
Chaque village est représenté par un sommet et chaque route directe entre deux villages par une arête. On obtient par exemple le graphe suivant :

D'autres dessins sont possibles : seuls comptent les sommets et les arêtes qui les relient.
Question 2

Déterminer l'ordre du graphe et le degré de chaque sommet.

Correction
  • On appelle ordre\red{\text{ordre}} d'un graphe le nombre nn de sommets de ce graphe.
    • Le graphe possède 66 sommets donc le graphe est d'ordre 66.
    Le degré d'un sommet est le nombre de routes qui partent de ce village. D'où :
    Question 3

    Combien y a-t-il de routes ?

    Correction
  • 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} .
    • Chaque route est une arête du graphe.
    La somme de tous les degrés est égale à : 2+3+4+4+3+2=182+3+4+4+3+2=18
    Il en résulte donc que :
    nombre d’areˆtes=182\text{nombre d'arêtes}=\dfrac{18}{2}
    Ainsi :
    nombre d’areˆtes=9\text{nombre d'arêtes}=9

    Il y a donc 99 routes.
    Question 4

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

    Correction
  • Un graphe est connexe\red{\text{connexe}} si deux sommets quelconques sont reliés par une chaîne.
  • Un graphe est dit complet\red{\text{complet}} si tous ses sommets sont adjacents, c’est-à-dire si toutes les arêtes possibles existent.
    • Le graphe est connexe, en effet la chaîne suivante : A−B−D−C−E−FA-B-D-C-E-F 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 5

    Un cantonnier doit inspecter toutes les routes en passant une et une seule fois par chacune d'elles. Est-ce possible ? Si oui, préciser les villages de départ et d'arrivée, puis 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.
    • D'après la question 22 :
    Le graphe est connexe et deux sommets seulement ont un degré impair (BB et EE), donc le graphe admet une chaîne eulérienne (entre BB et EE).
    Le cantonnier doit donc partir de BB et arriver en EE (ou l'inverse). Par exemple : B−A−C−B−D−C−E−D−F−EB - A - C - B - D - C - E - D - F - E .

    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.