Se connecter
S'inscrire
Formules
Blog
Se connecter
Retour au chapitre
Graphes
Maitriser le vocabulaire lié aux graphes - Exercice 2
5 min
10
On considère le graphe
G
G
G
représenté ci-dessous :
Question 1
Quel est l'ordre du graphe ?
Correction
On appelle
ordre
\red{\text{ordre}}
ordre
d'un graphe le nombre
n
n
n
de sommets de ce graphe.
Le graphe possède
7
7
7
sommets donc le graphe est d'ordre
7
7
7
.
Question 2
Ce graphe est-il connexe?
Correction
Un graphe est
connexe
\red{\text{connexe}}
connexe
si deux sommets quelconques sont reliés par une chaîne.
Le graphe est connexe, en effet la chaîne suivante :
E
−
D
−
F
−
A
−
B
−
H
−
C
E-D-F-A-B-H-C
E
−
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}}
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}}
complet
si tous ses sommets sont adjacents, c’est-à-dire si toutes les arêtes possibles existent.
Ce graphe n’est pas complet (
A
A
A
et
H
H
H
, par exemple ne sont pas adjacents).
Question 5
Donner le degré de chaque sommet .
Correction
On appelle
degr
e
ˊ
\red{\text{degré}}
degr
e
ˊ
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’ar
e
ˆ
tes
=
la somme des degr
e
ˊ
des sommets
2
\text{nombres d'arêtes}=\frac{\text{la somme des degré des sommets}}{2}
nombres d’ar
e
ˆ
tes
=
2
la somme des degr
e
ˊ
des sommets
.
La somme de tous les degrés est égale à :
2
+
4
+
5
+
5
+
4
+
4
+
2
=
24
2+4+5+5+4+4+2=24
2
+
4
+
5
+
5
+
4
+
4
+
2
=
24
Il en résulte donc que :
nombres d’ar
e
ˆ
tes
=
24
2
\text{nombres d'arêtes}=\frac{24}{2}
nombres d’ar
e
ˆ
tes
=
2
24
Ainsi :
nombres d’ar
e
ˆ
tes
=
12
\text{nombres d'arêtes}=12
nombres d’ar
e
ˆ
tes
=
12