Graphes

Maitriser le vocabulaire lié aux graphes - Exercice 1

5 min
10
On considère le graphe GG représenté ci-dessous :
Question 1

Quel est l'ordre du graphe ?

Correction
  • On appelle ordre\red{\text{ordre}} d'un graphe le nombre nn de sommets de ce graphe.
    • Le graphe possède 55 sommets donc le graphe est d'ordre 55.
    Question 2

    Ce graphe est-il connexe?

    Correction
  • Un graphe est connexe\red{\text{connexe}} si deux sommets quelconques sont reliés par une chaîne.
    • Le graphe est connexe, en effet la chaîne suivante : E−D−B−A−CE-D-B-A-C passe par tous les sommets. Ainsi, deux sommets quelconques seront toujours reliés par une chaîne.
    Question 3

    Le graphe est-il simple ?

    Correction
  • Un graphe est dit simple\red{\text{simple}} si au plus une arête relie deux sommets et s'il n'y a pas de boucle sur un sommet.
    • Dans notre situation, le graphe est simple car il ne possède pas de boucle et il y a au plus une arête entre deux sommets.
    Question 4

    Le graphe est-il complet ?

    Correction
  • Un graphe est dit complet\red{\text{complet}} si tous ses sommets sont adjacents, c’est-à-dire si toutes les arêtes possibles existent.
    • Ce graphe n’est pas complet (AA et DD, par exemple ne sont pas adjacents).
    Question 5

    Donner le degré de chaque sommet .

    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).
    • Question 6

    En déduire le nombre d'arêtes de ce graphe ?

    Correction
  • Dans un graphe, nous avons la relation suivante : nombres d’areˆtes=la somme des degreˊ des sommets2\text{nombres d'arêtes}=\frac{\text{la somme des degré des sommets}}{2} .
    • La somme de tous les degrés est égale à : 3+2+2+3+2=123+2+2+3+2=12
    Il en résulte donc que :
    nombres d’areˆtes=122\text{nombres d'arêtes}=\frac{12}{2}
    Ainsi :
    nombres d’areˆtes=6\text{nombres d'arêtes}=6