Maitriser le vocabulaire lié aux graphes - Exercice 1
5 min
10
On considère le graphe G représenté ci-dessous :
Question 1
Quel est l'ordre du graphe ?
Correction
On appelle ordre d'un graphe le nombre n de sommets de ce graphe.
Le graphe possède 5 sommets donc le graphe est d'ordre 5.
Question 2
Ce graphe est-il connexe?
Correction
Un graphe est 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−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 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 si tous ses sommets sont adjacents, c’est-à-dire si toutes les arêtes possibles existent.
Ce graphe n’est pas complet (A et D, par exemple ne sont pas adjacents).
Question 5
Donner le degré de chaque sommet .
Correction
On appelle degreˊ 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=2la somme des degreˊ des sommets .
La somme de tous les degrés est égale à : 3+2+2+3+2=12 Il en résulte donc que : nombres d’areˆtes=212 Ainsi :
nombres d’areˆtes=6
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.