Les Graphes

Mustapha Lourika

CPGE Salmane Al Farissi-Salé

MP-2TSI

2024 - 2025
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Introduction

De manière générale, un graphe permet de représenter la structure, les

connexions d'un ensemble complexe en exprimant les relations entre ses
éléments : réseau de communication, réseaux routiers, interaction de
diverses espèces animales, circuits électriques, etc...
Les graphes constituent donc une méthode de pensée qui permet de
modéliser une grande variété de problèmes en se ramenant à l'étude de
sommets et d'arcs.

1/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Dénition

Dénition
Un graphe G est un couple formé de deux ensembles :
Un ensemble : S = {s1 , s2 , . . . , sn } dont les éléments sont dits des
sommets.
Un ensemble :A = {a1 , a2 , . . . , an } dont les éléments sont dits des
arêtes (ou arcs). A ⊂ S × S
Donc un graphe G = (S, A) est ensemble ni de sommets reliés par des
arêtes (graphe non orienté) ou par des arcs (graphe orienté)

2/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Graphes non orientés

Dénition :
Un Graphe non orienté G = (S, A) est déni par :
Un ensemble S de sommets
Un ensemble A d'arêtes tq : (x, y) = (y, x) avec x, y ∈ S (A est
l'ensemble des parties d'un ou de deux éléments de S)

Exemple :

soit G = (S, A) un graphe non orienté

Figure  Graphe non orienté

3/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Graphes orientés

Dénition :
Dans le cas des graphes orientés les arêtes du graphe sont orientées.
Un Graphe orienté G = (S, A) est déni par :
Un ensemble S de sommets
Un ensemble A ⊂ S × S
Un arc a = (s1 , s2 ) est aussi noté s1 → s2 , s1 est l'origine de a est s2
l'extrémité.

4/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Graphes

Ordre d'un Graphe :

L'ordre d'un Graphe G = (S, A) est le nombre de ses sommets (cardinal de
S).

Exemple :

Figure  Graphe non orienté

Figure  Graphe orienté
5/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Graphes

Degré d'un Sommet : (Graphe non orienté)

Le degré d'un sommet s, noté d(s) est le nombre d'arêtes dont le sommet s
est une extrémité.

6/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Graphes

Degré d'un Sommet : (Graphe non orienté)

Le degré d'un sommet s, noté d(s) est le nombre d'arêtes dont le sommet s
est une extrémité.

d(A) = 1, d(B) = 3, d(C) = 2, d(D) = 2, d(E) = 2

6/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Graphes

Degré d'un Sommet : (Graphe orienté)

On appelle degré sortant d'un sommets, noté d+ (s) (resp. degré entrant
d'un sommet s, noté d− (s)) le nombre d'arcs dont s est un prédécesseur
(resp. un successeur).

7/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Graphes

Degré d'un Sommet : (Graphe orienté)

On appelle degré sortant d'un sommets, noté d+ (s) (resp. degré entrant
d'un sommet s, noté d− (s)) le nombre d'arcs dont s est un prédécesseur
(resp. un successeur).

d+ (A) = 2, d+ (B) = 1, d+ (C) = 1, d− (C) = 2

7/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Graphes

Degré d'un Graphe :

Le degré d'un Graphe est le degré maximum de tous ses sommets S
Pour G = (S, A) on a d(G) = max{d(s) ∈ S}

d(G) = 3

8/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Graphes

Graphe Simple :
Un graphe non orienté G = (S, A) est simple s'il ne contient pas de boucle,
et s'il ne comporte jamais plus d'une arête entre deux sommets.

Figure  Graphe simple

Figure  pas simple
Figure  Graphe simple

9/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Graphes
Graphe Complet :
Un graphe orienté simple est dit complet s'il comporte un arc (si , sj ) et un
arc (sj , si ) pour tout couple de sommets diérents si , sj ∈ S . De même, un
graphe non-orienté simple est dit complet s'il comporte une arête {si , sj }
pour toute paire de sommets diérents si , sj ∈ S .

10/20
Figure  Graphe complet
Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI
Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Représentation des Graphes

Représentation des Graphes :

Il existe deux façons classiques pour représenter un graphe G = (S, A) :
par un ensemble de listes d'adjacences.
par une matrice d'adjacences.

11/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Représentation des Graphes

Représentation des Graphes :

Il existe deux façons classiques pour représenter un graphe G = (S, A) :
Si le Graphe est peu dense : |A| << |S|2 =⇒ Liste d'adjacences

Si le Graphe est dense : |A| ≈ |S| =⇒2

Matrice d'adjacences

12/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Représentation des Graphes

Liste d'Adjacences :

Dans un graphe, la liste d'adjacence peut être représentée de deux manières

principales : par un dictionnaire ou une liste de listes.
Dictionnaire : Chaque sommet est une clé, et la valeur associée est
une liste de ses voisins.
Liste de listes : Chaque sommet est représenté par un indice et
l'indice correspondant dans une liste contient les voisins du sommet.

13/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Représentation des Graphes

14/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Représentation des Graphes

Matrice d'Adjacences :
La représentation par matrice d'adjacence d'un graphe G = (S, A) consiste
alors en une matrice |S| × |S|(
1 si (i, j) ∈ A
M = (ai,j ) telle que : ai,j =
0 sinon.

15/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Représentation des Graphes

16/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Parcours en Largeur (BFS : Breadth First Search)

Parcours en Largeur

L'algorithme va parcourir les sommets accessibles depuis le sommet s en

commençant par ceux situés à la distance 1, puis ceux situés à la distance 2,
etc ...

17/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Parcours en Largeur (BFS)

Principe

Mettre le n÷ud source dans la le ;

retirer le n÷ud du début de la le pour le traiter ;
mettre tous ses voisins non explorés dans la le (à la n) ;
si la le n'est pas vide reprendre à l'étape 2.

18/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Parcours en Largeur (BFS)

Parcours en Largeur (BFS)

19/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes
 Itroduction Terminologie Quelques Types de Graphes Implémentation Parcours des Graphes

Parcours en Largeur (BFS)

20/20

Mustapha Lourika CPGE Salmane Al Farissi-Salé MP-2TSI

Les Graphes