Devoir type n°1 (1 h) - Exercice 1

20 min

On considère le graphe

G

représenté ci-dessous.

Barème : 7 points

Question 1

Déterminer l'ordre du graphe et le degré de chaque sommet.

Correction

On appelle

\red{\text{ordre}}

d'un graphe le nombre

n

de sommets de ce graphe.

Le graphe possède

6

sommets donc le graphe est d'ordre

6

.
Les degrés sont :

A

2

;

B

4

;

C

3

;

D

2

;

E

4

;

F

3

Question 2

Correction

Dans un graphe, nous avons la relation suivante :

\text{nombre d'arêtes}=\dfrac{\text{la somme des degrés des sommets}}{2}

La somme de tous les degrés est égale à :

2+4+3+2+4+3=18

Il en résulte donc que :

\text{nombre d'arêtes}=\dfrac{18}{2}

Ainsi :

\text{nombre d'arêtes}=9

Question 3

Correction

Le graphe est connexe, en effet la chaîne suivante :

A-B-C-D-E-F

passe par tous les sommets. Ainsi, deux sommets quelconques seront toujours reliés par une chaîne.
Ce graphe n’est pas complet (

A

C

, par exemple ne sont pas adjacents).

Question 4

Correction

Un graphe connexe possède une

\red{\text{chaîne eulérienne}}

si, et seulement si, le nombre de sommets de degré impair est égal à

0

2

Si le nombre de sommets de degré impair est égal à

2

, alors les deux sommets de degré impair sont les extrémités de la chaîne eulérienne.

D'après la question

1

Le graphe est connexe et deux sommets seulement ont un degré impair (

C

F

), donc le graphe admet une chaîne eulérienne (entre

C

F

).
Par exemple :

C - B - A - F - B - E - C - D - E - F

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.