Qui aura 20 en maths ?

💯 Teste ton niveau de maths et tente de gagner un des lots !S'inscrire au jeu  →

Nouveau

🔥 Découvre nos fiches d'exercices gratuites avec corrections en vidéo !Accéder aux fiches  →

Exercices types : 1ère partie - Exercice 1

10 min
15
On considère le graphe ci-dessous :
Question 1

Déterminer l'ordre du graphe .

Correction
  • On appelle 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

    Déterminer le degré de chaque sommet. En déduire le nombre d'arêtes de ce graphe.

    Correction
  • On appelle degré d'un sommet le nombre d'arêtes dont ce sommet est une extrémité (les boucles étant comptées deux fois).
  • 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=262+4+5+5+4+4+2=26
    Il en résulte donc que :
    nombres d’areˆtes=262\text{nombres d'arêtes}=\frac{26}{2}
    Ainsi :
    nombres d’areˆtes=13\text{nombres d'arêtes}=13
    Question 3

    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 : A−B−C−E−D−F−GA-B-C-E-D-F-G passe par tous les sommets. Ainsi, deux sommets quelconques seront toujours reliés par une chaîne.
    Question 4

    Ce 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 (GG et CC, par exemple ne sont pas adjacents).
    Question 5

    Ce graphe admet-il une chaîne eulérienne?

    Correction
  • Un graphe connexe possède une chaıˆne euleˊrienne\red{\text{chaîne eulérienne}} si, et seulement si, le nombre de sommets de degré impair est égal à 00 ou 22.
  • Si le nombre de sommets de degré impair est égal à 22, alors les deux sommets de degré impair sont les extrémités de la chaîne eulérienne.
    • Regardons les degrés de chaque sommet :
    Le graphe est connexe et deux sommets seulement ont un degré impair (CC et DD), donc le graphe admet une chaîne eulérienne (entre CC et DD).
    Question 6

    Ce graphe admet-il un cycle eulérien?

    Correction
  • Un graphe connexe admet un cycle euleˊrien\red{\text{cycle eulérien}} si, et seulement si, tous ses sommets ont un degré pair.
    • Comme tous les sommets ne sont pas degré pair, le graphe n’admet pas de cycle eulérien.