INITIATION AUX GRAPHES

3ème ECONOMIE & GESTION

A.S. : 2021-2022

− I-Notion de graphe
1. Représentation d’une situation à l’aide d’un graphe

Activité : 1 p : 85

3 4

1 5

2 6

1 On a alors les schémas : (2) et (3).

2 4 personnes au maximum peuvent être invitées ensemble sans risque de problème
sont : 1, 3, 4 et 6.
vvvGFGvvv

Vocabulaire :
• Le schéma ci-dessus représente un graphe.
• Les points 1, 2, 3, 4, 5, 6 sont les sommets de ce graphe.
• Les lignes lorsqu’il y en a reliant deux sommets sont appelées des arêtes.
• L’ordre d’un graphe est égal au nombre de ses sommets.
• On dit que deux sommets sont adjacents s’ils sont reliés par une arête.
• Le degré d’un sommet est le nombre d’arêtes dont ce sommet est une extrémité.

Activité : 3 p : 86

1 2

1 3 4

D
MECHERGUI Saber

B A

2 a F E C
b Le nombre d’arêtes ayant pour extrémité D est égal à 2
Le nombre d’arêtes ayant pour extrémité F est égal à 0.

Page 1/7 Lycée Utique

 3ème ECONOMIE & GESTION
Définition :

✓ Un graphe est complet si chaque sommet est adjacent à tous les autres.
A.S. : 2021-2022

✓ Un sommet est isolé s’il n’est adjacent à aucun autre sommet.

Notation :
• Un graphe complet d’ordre n est noté Kn .

Activité : 4 p : 86

G1 et G3 sont susceptibles de décrire une même situation.

vvvGFGvvv

G4 et G6 sont susceptibles de décrire une même situation.

2. Lemme de poignées de main

Activité : 1 p : 87

1 G1 3 G3

Sommet 1 2 3 Sommet 1 2 3 4 5
a a
Degré 2 2 2 Degré 2 4 2 4 2

b La somme des degrés de tous les b La somme des degrés de tous les
sommets est égale à 6. sommets
est égale à 14.
c Le nombre darêtes égale à 3.
c Le nombre darêtes égale à 7.
2 G2
4 G4

Sommet A B C D E Sommet a b c d e f g
a a
Degré 2 3 2 3 2 Degré 3 3 4 4 2 4 2
MECHERGUI Saber

b La somme des degrés de tous les b La somme des degrés de tous les
sommets est égale à 12. sommets est égale à 22.
c Le nombre darêtes égale à 6. c Le nombre darêtes égale à 11.

Théorème
La somme des degrés des sommets d’un graphe est égale à deux fois le nombre des arêtes
de ce graphe.

Page 2/7 Lycée Utique

 3ème ECONOMIE & GESTION
Activité : 4 p : 88
A.S. : 2021-2022

1 2 3 4

3 4 1 5

2 6

Il est impossible de construire les graphe ayons 5 ou 7 sommets : car le nombre des
1
arêtes = somme des degrés des sommets.
2

Théorème
Le nombre de sommets de degré impaire d’un graphe est pair.

3. Circulation sur un graphe

vvvGFGvvv

Activité : 1 p : 88

1 A−B−C−E ou A−D−G−F−E
2 C−F ou C−G−F ou C−F−E−C−F
3 A−B−C−E−F−C−G−F−D−A−G−D
4 Non

Définition :

• Une chaine dans un graphe G est une suite finie : s0 , a1 , s1 , a2 , s2 , a3 , s3 ..., an , sn

débutant et finissant par un sommet, alternant sommets et arêtes de telle manière que
chaque arête soit encadrée par ses sommets extrémités.

• La longueur d’une chaine est le nombre d’arêtes qui la décomposent.

• Une chaine est dite fermée si son origine et son extrémité sont confondues.

• Un cycle est une chaine fermée composée d’arêtes toutes distinctes.

MECHERGUI Saber

Application : p : 89

1 La longueur de cette chaine est égale à 10.

2 A−E−B−C−X−Y ⇒ La longueur est égale à 10.

Page 3/7 Lycée Utique

 3ème ECONOMIE & GESTION
Activité : 2 p : 89

S−P−E−C−A−B
A.S. : 2021-2022

Définition :
Un graphe est dit connexe si on peut relier deux quelconques de ses sommets par une
chaine.

Application : p : 89

G1 , G3 et G6 sont connexe

Activité : 3 p : 89
vvvGFGvvv

1 1

2 3 2 3

6
4 5
4 5
2−1−3−2−4−5−3
4−2−1−3−2−6−4−5−6−3−5

Définition :

• Une chaine eulérienne est une chaine satisfaisant aux conditions suivantes :

✓ elle contient toutes les arêtes du graphe.

✓ chaque arête n’est décrite qu’une seule fois.

• Un cycle eulérien est une chaine eulérienne fermée.

MECHERGUI Saber

Remarque :
Une chaine eulérienne ne peut pas contenir plusieurs fois la même arête, mais elle peut
passer plusieurs fois par le même sommet.

Page 4/7 Lycée Utique

 3ème ECONOMIE & GESTION
Théorème

✓ Un graphe connexe G admet une chaine eulérienne, si et seulement si, tous ses
A.S. : 2021-2022

sommets sont de degré pair ou deux uniquement de ses sommets sont de degré impair (ce
sont les extrémités de la chaine).

✓ Un graphe connexe G admet un cycle eulérien, si et seulement si, tous ses sommets
sont de degré pair.

− II-Coloriage d’un graphe

Activité : 1 p : 91

G B

C H
vvvGFGvvv

D A

E F

Vocabulaire :
Colorier un graphe consiste à affecter une couleur à chacun de ses sommets de sorte que
deux sommets adjacents ne portent pas la même couleur.

ALGORITHME DE WELSH ET POWELL

UN ALGORITHME POUR COLORER UN GRAPHE

✓ Étape 1 :
Ordonner les sommets dans l’ordre décroissant de leurs degrés

✓ Étape 2 :
MECHERGUI Saber

Dans la liste ainsi ordonnée, on attribue la couleur C1 au premier sommet

de la liste, puis en suivant la liste on attribue cette même couleur aux
sommets qui ne lui sont pas adjacents et qui ne sont pas adjacents entre eux.

✓ Étape 3 :
On attribue une deuxième couleur C2 au premier sommet non coloré de la
liste, et on recommence comme dans l’étape 2 tant qu’il reste des sommets
non colorés de la liste.

Page 5/7 Lycée Utique

 3ème ECONOMIE & GESTION
Application : 2 p : 92
A.S. : 2021-2022

1 1

2 3 2 3

6
4 5
4 5
Sommet 2 5 1 3 4
Couleur C1 C2 C3 C3 C3 7
Sommet 4 5 3 6 1 2 7
Couleur C1 C2 C1 C3 C3 C2 C3

Activité : 2 p : 92
vvvGFGvvv

Sommet B G C D E F A H
1 a
Couleur C1 C1 C2 C3 C2 C3 C2 C3
b le nombre de couleurs utilisées est égal à 3.
2 Oui
C D

A B G H

E F

Remarque :
L’algorithme de Welsh et Powell ne donne pas le nombre minimal de couleurs nécessaires
pour le coloriage d’un graphe.

Définition :

Le nombre chromatique d’un graphe G est le nombre minimal de couleurs nécessaires

MECHERGUI Saber

pour son coloriage : on le note γ (G).

Activité : 4 p : 93

1 γ (G) = 3 2 γ (G) = 5 3 γ (G) = n

Page 6/7 Lycée Utique

 3ème ECONOMIE & GESTION
Théorème

Le nombre chromatique d’un graphe complet dordre n est égal à n.

A.S. : 2021-2022

Activité : 5 p : 93

1 On a un seul sous graphe complet 2 On a :

d’ordre 4 B E
B
A C G
A C
D F
D

Définition :
vvvGFGvvv

Un sous graphe dun graphe G est composé de quelques sommets de G et de toutes les
arêtes qui les relient.

Théorème

• Le nombre chromatique d’un graphe est supérieur ou égal à l’ordre de tous ses
sous-graphes complets .

• Soit G un graphe et k le plus grand degré de ses sommets. γ (G) ≤ K + 1

• Quatre couleurs suffisent pour colorier n’importe quelle carte géographique de façon
que deux pays voisins ne soient pas coloriés par la même couleur.

− III-Recherche dune plus courte chaine

Définition :

• Un graphe pondéré est un graphe dont les arêtes sont affectées de coefficients
positifs.

•
MECHERGUI Saber

Le poids d’une chaine est la somme des coefficients des arêtes qui la composent.

• Une plus courte chaine entre deux sommets est, parmi les chaines qui les relient
une chaine de poids minimum.

Activité : 2 p : 95

A − C − D son poids est égal à 5.

Page 7/7 Lycée Utique