Nouveau

🤔 Bloqué sur un exercice ou une notion de cours ? Échange avec un prof sur le tchat !Découvrir  →

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.

    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.