3ème Eco Chapitre :Initiation graphes www.mathinfo.

tn
Exercice 1
Soit le graphe G ci-dessous :

Une seule des réponses proposées est exacte.

1.L'ordre de G est....

a)6 b)5 c)8

2.Le sommet de C est

a)isole b)de degré 2 c)Adjacent au sommet A

3.La somme de degrés des sommets est

a)10 b)12 c)16

4.Le graphe G est

a)Complet b)Connexe c)Non connexe

5. A-B-C-D-B

a)n’est pas une chaine de G b) une chaine de G c)est un cycle de G

6. E-D-C-D-E est….

a)une chaine de longueur 5 b) n’est pas une chaine c)une chaine fermée

Exercice 2
Pour chacune des questions suivantes une seule des trois réponses proposées est exacte, laquelle?

1
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn
Soit G le graphe ci-contre.

1 L'ordre du graphe 𝐺 est :

a) 7 b) 8 c) 9
2 La somme des degrés des sommets est :
a)16 b) 17 c) 18
3 G est un graphe :
a)Complet. b) D'ordre 7 c)Connexe.
4 La chaine A-B-C-G-H-A est :
a) Fermée b)Eulérienne c) Un cycle
5 Le nombre chromatique du graphe G est :
a) 2 b) 3 c) 4
Exercice 3
Pour chacune des questions suivantes une seule des trois réponses proposées est exacte, laquelle ?

Soit G le graphe ci-contre.

1 L'ordre du graphe 𝐺 est:

a) 6 b) 8 c) 9
2 La somme des degrés des sommets est :
a) 20 b) 22 c) 24
3 G est un graphe :
a)Complet. b) D'ordre 7. c)Connexe.
4 La chaine A-B-C-D-E-A est :
a) Fermée b)Eulérienne c) Un cycle
5 Le graphe G admet :
a)Une chaine eulérienne b) Un cycle eulérien c) ni l'une ni l'autre
6 Le nombre chromatique du graphe G est :
a)2 b) 3 c) 4
Exercice 4
Soit le graphique suivant :
1- L'ordre du graphe est :
a- 7 b- 22 c- 11
2- Le nombre d'arêtes du graphe est:
a- 7 b- 22 c- 11
3- le nombre chromatique est:
2
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn
a- 3 b- 4 c- 5
4- Recopier et compléter le tableau suivant:

Sommet 1 2 3 4 5 6 7

Degré

5- Répondre en justifiant la réponse :

a- Le graphe est-il complet ?
b- Le graphe admet-il un cycle eulérien?
c- Le graphe admet-il une chaine eulérienne ?

Exercice 5
Soit le graphique suivant :

1- Donner le degré de chaque sommet.

2- Le graphe G admet-il un cycle eulérien ? Justifier la réponse.
3- Montre que le graphe G admet une chaine eulérienne. Donner un
exemple de chaine eulérienne.
4- Déterminer le nombre chromatique de ce graphe.

Exercice 6
On considère le graphe (𝐆) si dessous :
1- donner l'ordre du graphe (G)
2-donner la distance entre les deux sommets A et C
3-a-recopier et compléter le tableau suivant :

sommet A B C D E

degré

b- le graphe (𝐆) admet-il un cycle eulérien .justifier

c- prouver que (G) admet au moins une chaîne eulérienne
d- donner un exemple de chaîne eulérienne

3
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn
Exercice 7

On considère le graphe G ci-contre :

1. Donner l'ordre du graphe G .

2. Donner une chaine fermée de longueur 4.
3. Le graphe G est-il complet ? Justifier.
4. Donner un sous-graphe complet d'ordre 4.
5. Le graphe G est-il connexe?
6. Donner le degré de chacun des sommets du graphe G.
7.a) Prouver que le graphe G admet une chaine
eulérienne.
b) Donner un exemple de chaine eulérienne.
8. Justifier la non-existence d'un cycle eulérien pour le graphe G .
Quelle arête peut-on alors effacer de ce graphe pour obtenir un graphe
Contenant un cycle eulérien. Donner ce cycle.
9.a) On note 𝛾 (G) le nombre chromatique du graphe G. Donner un encadrement de 𝛾 (G).
b) Déterminer le nombre chromatique du graphe G .
Exercice 8

Un groupe d'antis organise une randonnée dans les Alpes.

On a représenté par le graphe ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent
choisir de passer.
Une arête entre deux sommets coïncide avec l'existence d'un chemin entre les deux sommets.

1 a) Recopier et compléter le tableau suivant :

4
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn

Sommets B C D F N T

Degré des sommets du graphe

b) Justifier que le graphe est connexe.

2) Le groupe souhaite passer par les six sommets en passant une fois et une seule par chaque
chemin.

Démontrer que leur souhait est réalisable. Donner un exemple de trajet possible.
3) Le groupe souhaite associer chaque sommet à une couleur de sorte que les sommets reliés par
un chemin n'ont pas la même couleur. On note 𝑛 le nombre chromatique du graphe.
a) Montrer que 4 ≤ 𝑛 ≤ 6
b) Proposer un coloriage du graphe permettant de déterminer son nombre chromatique.
4) Le groupe se trouve au sommet B et souhaite se rendre au sommet N. Les distances en
kilomètres entre chaque sommet ont été ajoutées sur le graphe.
Indiquer une chaîne qui minimise la distance du trajet. Justifier la réponse.

Exercice 9
Le graphe pondéré ci-contre représente un réseau routier sur chacune de ses arêtes on a marqués la
distance séparant les deux villes reliées par cette arête en Km .

5
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn

En appliquant l’algorithme de Dijkstra compléter ce tableau puis déterminer le chemin le plus

court qui mène de E vers S.

E A B C D S On garde

0 ∞ ∞ ∞ ∞ ∞ 𝐄

Exercice 10
Le graphe pondéré ci-contre représente un réseau routier sur chacune de ses arêtes on a marqués la
distance séparant les deux villes reliées par cette arête en Km .

6
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn

1)Déterminer le poids de la chaine F-G-C-D.

2)Ce graphe admet-il une chaine eulérienne ou un cycle eulérien .Dire pourquoi ?
a) Si oui donner un exemple.
3)En appliquant l’algorithme de Dijkstra compléter ce tableau .

A B C D E F G On garde

0 ∞ ∞ ∞ ∞ ∞ ∞ A

0+6 0+3
F
6(E) 3(A)

a)Déterminer à l'aide de ce tableau la plus courte chaine reliant 𝐴 et 𝐷.

b)Donner le poids de cette chaine

7
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn

Exercice 1 :
1.L'ordre de G est.5

2.Le sommet de C est de degré 2

3.La somme de degrés des sommets est 16

4.Le graphe G est Connexe

5. A-B-C-D-B est une chaine de G

6. E-D-C-D-E est une chaine fermée

Exercice 2 :
1 L'ordre du graphe 𝐺 est :8

2 La somme des degrés des sommets est : 18

Sommet A B C D E F G H Total

Degré 2 2 4 2 2 2 2 2 18

3 G est un graphe connexe.

4 La chaine A-B-C-G-H-A est : Fermée
5 Le nombre chromatique du graphe G est :3
Exercice 3 :

8
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn
L'ordre du graphe 𝐺 est: 6
La somme des degrés des sommets est : 22

Sommet A B C D E F Total

Degré 4 4 4 4 5 3 22

1 G est un graphe :Connexe.

2 La chaine A-B-C-D-E-A est : Fermée

3 Le graphe G admet :Une chaine eulérienne

4 Le nombre chromatique du graphe G est : 4

Exercice 4 :
1- L'ordre du graphe est 7
2- Le nombre d'arêtes du graphe est: 11
3- le nombre chromatique est: b- 4

4-

9
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn

Sommet 1 2 3 4 5 6 7

Degré 4 4 4 2 3 2 3

5-
a- Le graphe n’ est pas complet ( 1 et 4 ne sont pas liés)?
b- Le graphe n’admet pas un cycle eulérien car le degré de sommet 5 est 3 impair
c- Le graphe admet une chaine eulérienne (contient 2 sommets(5 et 7) de degrés impair

Exercice 5 :

1.
Sommet 𝐴 𝐵 𝐶 𝐷 𝐸 Total

degré 2 3 4 3 2 14 = 2 × 7

2- Le sommet B est de degré impair G n’ admet pas un cycle eulérien

3. G est connexe et admet exactement deux sommets de degré impair (B et D) donc G admet
une chaine eulérienne d'extrémités B et D.
B-C-D-B-A-C-E-D
4. a) (l′ ordre du sous, graphe complet 𝐴𝐵𝐶 ) ⩽ 𝛾 (G) ⩽ (degré du sommet C + 1)

3 ⩽ 𝛾 (G) ⩽ 4

b)

sommet 𝐴 B C 𝐷 𝐸

degré 2 3 4 3 2

couleur 𝐶1 𝐶2 𝐶3 𝐶1 𝐶2

10
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn
⇒ 𝛾(G) ⩽ 3 or 𝛾(G) ⩾ 3
⇒ 3 ⩽ 𝛾(G) ⩽ 3 ⇒ 𝛾(G) = 3

Exercice 6 :
1-l’ordre de G est 5
2-La distance entre A et C est 1
3-a-

sommet A B C D E

degré 3 2 3 4 2

b- le graphe (𝐆) n’admet pas un cycle eulérien car le degré de A est impair
c- il y a deux sommets dont le degrés est impair (A et C ) donc G admet au moins une chaine
eulérienne.
d- exemple de chaine eulérienne :
A-D-C-B-D-E-A

Exercice 7 :
1. G est un graphe d'ordre 6 . ( 6 sommets, 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹 )
2. 𝐴 − 𝐵 − 𝐶 − 𝐷 − 𝐴 ou bien 𝐷 − 𝐸 − 𝐴 − 𝐹 − 𝐷.
3. G n'est pas complet car les sommets A et C ne sont pas adjacents.
4.

G' est un graphe complet d'ordre 4.

5a) oui 𝐺 est un graphe connexe. Chaque couple de sommets est reliée par une chaine
11
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn
Sommet 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 Total

Degré g 4 2 2 4 3 3 18 = 2 × 9

7.) a.) G est connexe et admet exactement deux sommets de degré impair (E et F) donc G admet
une chaine eulérienne d'extrémités 𝐸 et 𝐹.
b ) 𝐸 − 𝐷 − 𝐹 − 𝐴 − 𝐵 − 𝐶 − 𝐷 − 𝐴 − 𝐸 − 𝐹.

Sommet 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 Total

degré 4 2 2 4 3 3 18 = 2 × 9

𝑑 0 𝐸 = 3 impair donc G n'admet pas de cycle eulérien.

Sommet 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 Total

degré 4 2 2 4 2 2 18 = 2 × 9

𝐴−𝐵−𝐶−𝐷−𝐹−𝐴−𝐸−𝐷−𝐴 cycle eulérien

9)a) 4 (l′ ordre du sous, graphe complet 𝐴𝐸𝐷𝐹 ) ⩽ 𝛾 (G) ⩽ 5(degré de sommet A + 1)

b)

12
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn
sommet 𝐴 𝐷 𝐸 𝐹 𝐵 𝐶

degré 4 4 3 3 2 2

couleur 𝐶1 𝐶2 𝐶3 𝐶4 𝐶2 𝐶1

⇒ 𝛾(G) ⩽ 4 or 𝛾(G) ⩾ 4
⇒ 4 ⩽ 𝛾(G) ⩽ 4 ⇒ 𝛾(G) = 4

Exercice 8 :

1)a)
Sommets B C D F N T

Degré des sommets du graphe 𝟐 𝟒 𝟒 𝟓 𝟑 𝟒

(Rappel : le degré d'un sommet est égal au nombre d'arêtes dont ce sommet est l'extrémité)
b) Justifier que le graphe est connexe.

Ce graphe est connexe car tous les sommets peuvent être reliés entre eux par (au moins) une
chaine.
Par exemple, la chaîne BCDNTF contient tous les sommets.
2) L'existence d'un parcours permettant au groupe de passer par les six sommets en passant une
fois et une seule par chaque chemin est liée à l'existence d'une chaîne eulérienne.
Puisque deux sommets exactement sont de degré impair et que les autres sont de degré pair, le
théorème d'euler nous permet d'affirmer l'existence d'une telle chaîne eulérienne, donc d'un tel
parcours.
Par exemple, le trajet F-B-C-F-N-T-F-D-C-T-D-N répond au problème.
3) a) Le sommet ayant le plus grand degré est le sommet 𝐹, de degré 5 .

Le cours nous affirme qu'alors 𝑛 ≤ 5 + 1, c'est-à-dire 𝑛 ≤ 6.

De plus, le sous-graphe FCTD, d'ordre 4 , étant complet, on aura 𝑛 ≥ 4 (il faudra au moins 4
couleurs pour le colorier).
b) On utilise l'algorithme de coloration dit « algorithme glouton » pour colorier le graphe :

13
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn

Sommets B C D F N T

Degré des sommets du graphe 𝟐 𝟒 𝟒 𝟓 𝟑 𝟒

Couleur C1 C2 C3 C4 C2 C4

Le nombre chromatique de ce graphe est donc égal à 4

4) On utilise l'algorithme du plus court chemin de Dijkstra pour déterminer une chaîne qui
minimise la distance du trajet enter B et N :

Sommet
B C F D T N
sélectionné

0 ∞ ∞ ∞ ∞ ∞ 𝐁(𝟎)

𝟎 + 𝟏𝟐 0 + 15
∞ ∞ ∞ 𝐂(𝟏𝟐)
= 𝟏𝟐(𝐁) = 15( B)

12 + 3 12 + 2 12 + 4
𝐃(𝟏𝟒)
= 15(C) = 14(C) = 16(C)

T(16)
14 + 5 14 + 3 14 + 12
= 19(D) = 17(D) = 26(D)

16+7=23(T) 𝐍(𝟐𝟑)

La plus courte chaîne reliant le sommet B au sommet N est donc B-C-T-N, de longueur égale à
23 km.

14
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn
Exercice 9

E A B C D S On garde

0 ∞ ∞ ∞ ∞ ∞ 𝐄

0+3 0+1
∞ ∞ ∞ B
3 (E) 1(E)

1+1 1+3 1+5

∞ A
2 (B) 4(𝐵) 6(𝐵)

2+3
6(𝐵) ∞ C
4(𝐵)

4+1 4+3
D
5(𝐶) 7(𝐶)

5+1
𝑆
6(𝐷)

15
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn

Le chemin le plus court E-B-D-S

Exercice 10

Poids de la chaine F-G-C-D est 5+3+3=11

2)

Sommet A B C D E F G Total

Degré 2 2 4 2 3 3 2 18

G est connexe et admet exactement deux sommets de degré impair (E et F) donc G admet une
chaine eulérienne
Ce graphe n’ admet pas un cycle eulérien : tous les sommets de G ne sont pas de degrés pair
3).

16
 3ème Eco Chapitre :Initiation graphes www.mathinfo.tn
A B C D E F G On garde

0 ∞ ∞ ∞ ∞ ∞ ∞ A

0+6 0+3
F
6(A) 3(A)

3+14 3+5
6(A) B
17(F) 8(F)

6+6
G
12(B)

8+3
C
11(G)

11+3

14(C)

D(14)

a)A-F-G-C-D.
b)Le poids est 14

17