1

Les graphes 4iéme Eco [Lycée abou –ishak jebeniana ]

1-Graphes non orientés

Un graphe est constitué de sommets qui sont reliés par des arêtes

*Deux sommets reliés par une arête sont adjacents

*Le nombre de sommets dans un graphe est L’ordre du graphe

*Le degré d’un sommet est le nombre d’arêtes dont ce sommet est une extrémité

Exemple

Le graphe G est d’ordre 5

Les sommets A et B sont adjacents

Les sommets B et D ne sont pas adjacents

Le degré du sommet A est : deg (A)=3

Théorème

La somme de degrés d’un graphe non orienté est égale au double du nombre d’arrêtes du graphe

Dans le graphe G

Deg(A)+deg(B)+deg(C)+deg(D)+deg(E) =3+2+3+2+2=12 = 2 x (6 ) , ( 6 étant le nombre des arêtes )

Dans ce cas deg (A) =4

Il faut compter le boucle 2 fois A

 Matrice associée à un graphe non orienté C

La matrice associée à un graphe non orienté est définie par

1 𝑠𝑖 𝑆𝑖 𝑒𝑡 𝑆𝑗 𝑠𝑜𝑛𝑡 𝑎𝑑𝑗𝑎𝑐𝑒𝑛𝑡𝑠
𝑀 = (𝑎𝑖𝑗 )1≤𝑖,𝑗≤𝑛 = {
0 𝑠𝑖𝑛𝑜𝑛

Lycée abou –ishak : [Link]

 2

0 1 0 1 1
1 0 1 0 0
𝑀= 0 1 0 1 1
1 0 1 0 0
(1 0 1 0 0)

On a ordonné les sommets par ordre alphabétique

Remarque « La matrice associée a un graphe non orienté est SYMETRIQUE »

Un sous graphe de G est un graphe G’ constitué de quelques sommets de G ainsi que les arêtes qui

les relient

 G’ est un sous graphe de G

 Un graphe est complet est un graphe dont tous les sommets sont adjacents

Rémarque « L a matrice d’adjacence d’un graphe complet admet des zéros sur la diagonale et des 1

partout »

 Le graphe G’’ est un graphe complet

 Une chaine est une liste ordonnée de sommets telle que chaque sommet est adjacent au

suivant

Exemple A-B-C-D

 Un graphe est connexe si chaque deux sommets de ce graphe sont reliés par une chaine

Exemple G, G’ et G’’ sont des graphes connexes

Par contre  N’est pas un graphe

connexe

Lycée abou –ishak : [Link]

 3

 La longueur d’une chaine est le nombre des arêtes qui la compose

La longueur de la chaine A-B-C-D est égale à 3

 Une chaine est dite fermée si l’origine et l’extrémité de la chaine sont confondues

Exemple A-B-C-D-A

 Un cycle est une chaine fermée dont toutes les arêtes sont distinctes

 Une chaine est dite Eulérienne si elle contient une et une seule fois chaque arrête du graphe

 Un cycle Eulérien est une chaine Eulérienne dont l’origine et l’extrémité sont confondues

 Un graphe est dit Eulérien s’il contient une chaine Eulérienne ou un cycle Eulérien

Remarque : Un graphe eulérien si l’on peut dessiner sans jamais lever le crayon et sans passer

deux fois par la même arête.

.
Théorème d’Euler : 1. Un graphe admet un cycle eulérien si et seulement si il est connexe et n’a
aucun sommet de degré impair.

2. Un graphe admet une chaîne eulérienne entre les sommets x et y si et seulement si il est connexe
et si x et y sont les deux seuls sommets de degré impair (l’origine et l’extrémité de la chaine)

Exemple

Sommet A B C D E F
degré 2 3 4 4 2 3

 Ce graphe n’admet pas un cycle Eulérien (il

admet un sommet de degré impair)
 Ce graphe admet une Chaine Eulérienne de B
à F (les seuls sommets de degré impair)

Lycée abou –ishak : [Link]

 4

Prenant le cas de la matrice du graphe G

0 1 0 1 1
1 0 1 0 0
𝑀= 0 1 0 1 1
1 0 1 0 0
(1 0 1 0 0)

En effet la somme de terme de la première ligne ( ou de la première colonne « grâce a la symétrie »)

Est égale au degré du sommet A ; soit deg (A) = 0+1+0+1+1 =3

Idem deg(B)=2 , deg(C)=3 , deg(D)=2 et deg (E) =2

Le graphe G admet deux sommet de degré impair donc elle admet une chaine Eulérienne reliant A à
C qui est : A—B—C—D—A— E—C

Coloriage d’un graphe

Définition

Colorier un graphe revient a colorer chaque sommet du graphe de sorte que deux sommets
adjacents ne porte pas la même couleur

Vocabulaire et notation

On note  (G) le nombre de couleurs minimal utilisé pour colorer un graphe

 (G) = nombre chromatique du graphe G

Propriété

 (G) est supérieur ou égal à l’ordre de tous les sous graphes complets de G

 (G) est inférieur ou égal à    1 ou  est le plus grand degré de ses sommets

Algorithme de WLESH-POWELL pour colorer un graphe

Ça consiste à ordonner les sommets dans l’ordre décroissant de leurs degrés

1- Colorer le sommet de plus haut degré avec une couleur et tous les sommets qui ne lui sont pas
adjacents ni adjacent l’un à l’autre avec la même couleur
2- Passer au deuxième sommet non coloré et refaire le même travail
EXEMPL E
Encadrer  (G) et colorer le graphe G

Lycée abou –ishak : [Link]

 5

Sommet
Degré
Couleur
choisie

3 ≤ 𝛾(𝐺) ≤ 5 + 1 ( 3 est le plus grand ordre d’un sous graphe complet possible de( G )et 5 = le
plus grand degré de sommets du G , en effet deg(C)=4)
On colore le sommet (a) par le rouge par exemple
 Trivialement si le graphe est complet d’ordre n alors  (G) =n
Graphe orienté

Un graphe orienté est un graphe dont les arêtes sont orientées

On parle alors des arcs qui a une origine et une extrémité

Lycée abou –ishak : [Link]

 6

On Note d  ( X )  le nombre d’arcs sortant du sommet X

d  ( X )  le nombre d’arcs rentrants au sommet X

Figure 1 (G1)
d  ( A)  2 ; d  ( A)  1
Matrice associée a un graphe orienté
Un graphe G de n sommets S1 , S2 , S3 ........Sn
La matrice associée a G est M  (aij )1i , j  n tel que aij = nombre d’arcs orienté de Si vers
Sj
Pour G1
0 1 1 0 0
0 0 0 0 0
𝑀= 0 0 0 1 0 la matrice d’un graphe orienté n’est pas en general symétrique
1 0 0 0 0
(0 0 0 0 0)
d  ( A)  0+1+1+0+0=2 (somme de termes de la première ligne )
d  ( A)  0+0+0+1+0=1 (somme de termes de la première colonne)
THEOREME
Un graphe orienté admet un cycle orienté Eulérien si et seulement si d  ( X )  d  ( X ) pour tous les
sommets du graphe

Un graphe orienté admet une chaine orientée Eulérienne si et seulement si d  ( X )  d  ( X ) sauf pour
d  ( A)  d  ( A)  1
deux sommets exactement (A et B ) ona A et B sont les extrémités de la chaine
d  ( B)  d  ( B)  1

Sommet A B C D

Lycée abou –ishak : [Link]

 7

d(X ) 2 2 1 1
d(X ) 1 1 2 2
Un graphe orienté NON Eulérien

Sommet A B C D E
 2 2 2 2 2
d (X )
d(X ) 2 2 2 2 2
Un graphe qui admet un cycle Eulérien ( en effet d  ( X )  d  ( X ) ) pour tout sommet X

Propriété : Soit une matrice d'adjacence A d'un graphe G non orienté d'ordre n dont les
sommets sont numérotés de 1 à n.
Le nombre de chaîne de longueur k reliant le sommet i au sommet j est égal au terme aij
de la matrice A k , k  *
.
Exemple:
La matrice associée au graphe ci-contre
est :

Lycée abou –ishak : [Link]

 8

0 1 1 0 0
 
1 0 1 1 1
A  1 1 0 1 0
 
0 1 1 0 1
0 0 
 1 0 1

4
0 1 1 0 0   11 13 11 14 9
   
1 0 1 1 1   13 26 19 19 13 
A  1
4
1 0 1 0    11 19 19 14 14 
   
0 1 1 0 1  14 19 14 19 11 
0 0   9 13 11 
 1 0 1 14 11

Il ya 14 chaines de longueur 4 reliant le sommet (4) au sommet (1)

Définitions

 La distance de deux sommets distincts est la longueur de la plus courte chaine joignant ces deux
sommets (exemple dans le graphe G la distance entre A et E = 1 , entre A et C =2
Par convention la distance d’un sommet a lui-même est nulle
 Le diamètre d’un graphe est la plus grande des distances entre deux sommets du graphe

Théorème
 La distance entre deux sommets i et j est le plus petit entier n tel que le terme d’indice i,j de la

matrice An est non nul .

Le diamètre du graphe est le plus petit entier naturel n tel que la matrice  A  I n  ait ses termes
n

strictement positifs.

Algorithme de D I J K S T R A
C’est un algorithme qui permet la recherche de la plus courte chaine
Exercice
1-Déterminer le poids de la chaine E-C-D-F-B
2-En appliquant l’algorithme de DIJKSTRA déterminer les plus courtes chaines reliant le sommet
E à n’importe quel sommet du graphe

Lycée abou –ishak : [Link]

 9

E A B C D F G S Sommet
sélectionné

3-Donner les plus courtes chaines et le poids de chacune, reliant

 EàS
 EàF

Lycée abou –ishak : [Link]

 10

BAC2022

Lycée abou –ishak : [Link]