Graphes

Maitriser le vocabulaire lié aux graphes - Exercice 2

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 : EDFABHCE-D-F-A-B-H-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 HH, 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 à : 2+4+5+5+4+4+2=242+4+5+5+4+4+2=24
    Il en résulte donc que :
    nombres d’areˆtes=242\text{nombres d'arêtes}=\frac{24}{2}
    Ainsi :
    nombres d’areˆtes=12\text{nombres d'arêtes}=12