Graphes

Maitriser le vocabulaire lié aux graphes - Exercice 3

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 77 sommets donc le graphe est d'ordre 77.
    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 : F−D−G−E−C−B−AF-D-G-E-C-B-A 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 (BB et EE, par exemple ne sont pas adjacents).
    Question 5

    Déterminer un sous-graphe complet d'ordre 33 . Quel est le degré de chacun de ses sommets ?

    Correction
  • G′G' est un sous-graphe\red{\text{sous-graphe}} de GG s'il est constitué de certains sommets de GG et de certaines arêtes qui relient ses sommets .
    • Nous pouvons par exemple choisir le sous-graphe DCEDCE. Dans notre situation, tous les sommets sont alors de degré 22.