Prof.

Taïcir Loukil
Faculté des Sciences Economiques et de
Gestion de Sfax

Cours de graphes et applications

Taicir Loukil

Objectifs du cours

• Apprendre aux étudiants à modéliser des problèmes concrets

à partir d'un certain nombre de modèles de graphes utiles
dans de nombreuses applications en recherche opérationnelle,
aide à la décision et intelligence artificielle.

• Comprendre les principaux algorithmes utilisables pour

résoudre les problèmes posés, savoir les mettre en œuvre de
façon efficace et évaluer leur complexité.

Taicir Loukil
2

1
 Plan du cours

• Chapitre I : Principaux algorithmes de résolution du problème de

plus court chemin
• Chapitre II : Programmation dynamique discrète et lien avec le
problème du plus court chemin
• Chapitre III : Algorithme de résolution du problème du flot
maximum
• Chapitre IV :Algorithme Hongrois pour la résolution du problème
d'affectation
• Chapitre V :l'algorithme du simplexe pour résolution du problème
du transport
• Chapitre VI :Problèmes généraux de flot à coût minimum.
Algorithme des arcs non conformes.
Taicir Loukil
3

• Références :
• 1. Fournier, J. C. (2011). Théorie des graphes et
applications: Avec exercices et problèmes. Lavoisier.
• 2. Fournier, J. C. (2007). Graphes et
applications. Hermès science publications-Lavoisier.

Taicir Loukil
4

2
 Introduction à la
Théorie des graphes

Taicir Loukil

Origines de la théorie des graphes

Le problème des sept ponts de Königsberg Résolu par Leonhard

Euler en 1736 est à l’origine de la théorie des graphes.

Ce problème consiste à déterminer s'il existe ou non une

promenade dans les rues de Königsberg permettant, à partir
d'un point de départ au choix, de passer une et une seule fois
par chaque pont, et de revenir à son point de départ, étant
entendu qu'on ne peut traverser le Pregel qu'en passant sur
les ponts.

Taicir Loukil
6

3
6

Taicir Loukil

Konigsberg

Taicir Loukil
8

4
 Pourquoi les graphes ?

• S’ouvrir à de nouveaux raisonnements, s’entraîner à

avoir un autre regard mathématique
• Montrer des mathématiques non classiques liées à des
problèmes concrets
• Sensibiliser à l’algorithmique
• Ouvrir un grand champ de modélisation conduisant à
des solutions efficaces pour de nombreux problèmes
• Laisser place à l'initiative des étudiants, avec un temps
nécessaire de tâtonnements et d’essais

Taicir Loukil
9

Quelques problèmes…
• Problèmes d’ordonnancement
• Problèmes de flot maximal
• Problèmes d’affectation
• Programmes de transport :dépôts de marchandises, clients avec
besoins, capacité des canaux illimitée (transformations d’arbres…)
• Problème du voyageur de commerce: visite de villes, avec
retour… (chemin hamiltonien de coût minimal)
• Problème du « sac à dos »: n objets, chaque objet ayant une
« utilité », sac de capacité m…
• Etc.

Taicir Loukil
10

5
 Définitions et Terminologies
Graphe : Un graphe G est défini par G=(V,U), où V est un ensemble
de sommets et U l’ensemble d'arcs(ou arêtes) ; Un arc (ou arête)
est un couple de sommets, donc, un élément du produit cartésien
VxV

Extrémité d’un arc : soit u = (x, y) un arc, x est dit extrémité

initiale de u et y est dit extrémité finale de u.

Successeur : on dit que y est successeur de x s’il existe un arc ayant

x comme extrémité initiale et y comme extrémité terminale.
L’ensemble des successeurs d’un sommet x est noté U+ (x).
Taicir Loukil
11

• Graphe non orienté : • Graphe orienté :

12 Taicir Loukil

6
 • Degré d’un sommet : nombre d’arêtes reliées à ce sommet
Le sommet A est de degré 3 : (B, C et D aussi)

Taicir Loukil
13

Graphe Pondéré : Un graphe pondéré est défini par le

triplet (V,U,C) où C est la fonction de coût de U dans IR.
Par convention Cu représente le coût ou le poids de l’arc
(ou de l’arête) u.
Graphe Connexe : Un graphe connexe est un graphe dont
tout couple de sommets peut être relié par une chaine de
longueur n>=1
Ordre du Graphe : le nombre de sommets du Graphe

Taicir Loukil
14

7
 Degré d’un sommet : nombre d’arêtes reliées à ce sommet
Adjacences: Deux arcs sont dits adjacents s'ils ont une extrémité en
commun. Et deux sommets sont dits adjacents si un arc les relie.
Boucle : est un arc qui part d’un sommet vers le même sommet
Chaîne : Une chaine de longueur n est une suite de n arêtes qui
relient un sommet i à un autre j ou à lui- même.
Cycle : Un cycle est une chaine qui permet de partir d’un sommet
et revenir a ce sommet en parcourant une et une seule fois les
autres sommets.
Distance entre deux sommets i et j est la longueur de la chaine la
plus courte qui les relie

Taicir Loukil
15

• CYCLE : On peut partir d’un sommet et revenir a ce sommet

en parcourant une et une seule fois les autres sommets

Taicir Loukil
16

8
  Chemin : c’est une chaine bien orientée
 Circuit : est un cycle "bien orienté", à la fois cycle et chemin.
 Chaine eulérienne: une chaine est dite eulérienne est une chaine
comportant exactement une fois toutes les arêtes du graphe.
 Cycle eulérien : si le sommet de départ d’une chaine eulérienne
et celui d’arrivé on parle de cycle eulérienne
 Graphe eulérien : Un graphe admettant une chaine eulérienne
est dit Graphe eulérien
 Cycle hamiltonien : c’est un cycle passant une seule fois par tous
les sommets d’un graphe et revenant au sommet de départ

17

Un chemin est:

 Élémentaire: s’il ne comporte pas plusieurs fois le même sommet.

 Simple: s’il ne comporte pas plusieurs fois le même arc (arête).

 Eulérien: passe une et une seule fois par chaque arc (arête) du
graphe. Il est simple et il contient tous les arcs (arêtes).

 Hamiltonien: passe une et une seule fois par chaque sommet du

graphe. Il est élémentaire et passe par tous les sommets.

NB. La longueur d’un parcours est égale au nombre d’arcs (d’arêtes)

qui le composent.

Taicir Loukil
18

9
 • Chaîne hamiltonienne : Chaîne passant par tous les

sommets d’un graphe ABCD (ABDC, ACBD

aussi)

Taicir Loukil
19

• Chaîne eulérienne : Chaîne passant par toutes les arêtes d’un

graphe (BACBDC)

Taicir Loukil
20

10
 Exemple 1: Somme des degrés des sommets d ’un
graphe

Un tournoi d’échec oppose n personnes. Chaque joueur

doit rencontrer tous les autres participants.

Représenter cette situation par un graphe pour :

• n= 4

• n= 5

• n= 6
Combien doit-on prévoir de rencontres ?
Taicir Loukil
21

n=4
n=5
n=6
Propriété : La somme des degrés d’un GNO est égale à deux
fois le nombre d’arêtes.
n = 4 :  d = 4  3 = 12. Il y aura 6 matchs.

n = 5 :  d = 5  4 = 20. Il y aura 10 matchs.

n = 6 :  d = 6  5 = 30. Il y aura 15 matchs.

Taicir Loukil
22

11
 • Sous graphe : Soit G = (X, U) un graphe et A  X. Le sous
graphe GA engendré par A est le graphe GA = (A, UA) dont
l’ensemble des sommets est A et l’ensemble des arcs UA sont
les arcs de G joignant deux sommets de A.

• Graphe partiel : soit le graphe G = (X, U), soit U’ un sous

ensemble d’arcs U’ inclus dans U, le graphe partiel G’
engendré par U’ est le graphe ayant même ensemble de
sommets que G et dont l’ensemble des arcs est inclus dans
l’ensemble des arcs de G. G’= (X, U’).

Taicir Loukil
23

Exemple : Existe-t-il un cycle

eulérien ??

CDBCABEC

Taicir Loukil
24

12
 Théorème d’Euler (1766)

• Graphe eulérien  Tous les sommets

du graphe ont un degré pair

OUI NON
Taicir Loukil
25

Dictionnaire des précédents

(graphe orienté)

Taicir Loukil

26 Taicir Loukil

13
 Matrice d’un graphe orienté
Matrice d’adjacence : Un graphe simple (orienté ou non) peut être
représenté par sa matrice d’adjacence sommets-sommets M = (aij ). M est
une matrice carré n×n où aij est défini comme suit:

ai j =1 si (x ,x )  U et 0 sinon

Taicir Loukil
27

• Liste d’adjacence : U graphe peut être représenté par le

dictionnaire des suivants ou des précédents. Cette représentation
consiste en une table à simple entré où chaque ligne correspond à
un sommet et la liste de ses successeurs ou de ses prédécesseurs

• Matrice d’incidence : soit G un graphe orienté sans boucles

comportant n sommets et m arcs. La matrice d’incidence
sommets- arcs de dimension n×m est défini par M= (bij)

bij =1 si xi est extrémité initiale de Uj

-1 si xi est extrémité terminale de Uj

0 sinon Taicir Loukil

28

14
 Connexite-forte connexite
Graphe connexe : Soit G = (X, U) un graphe non orienté. G est dit connexe si 
x, y  X, il existe une chaîne joignant x et y.
Composante connexe : La composante connexe d’un sommet x est l’ensemble
des sommets qui lui sont reliés par une chaine. On note Cs (x) = {y  X/ il
existe une chaîne entre x et y} {x} la composante simplement connexe de x.
Isthme et Point d’articulation : Un isthme (resp. point d’articulation) est une
arête (resp.sommet) dont la suppression augmente le nombre de
composantes connexes.
Graphe fortement connexe : Un graphe orienté est fortement connexe si  x, y
 X, il existe un chemin de x à y et un chemin de y à x.
Composante fortement connexe : La composante fortement connexe d’un
sommet x est Cf(x) = {y  X / il existe un chemin de x vers y et un chemin
de y vers x} U {x}
Taicir Loukil
29

Connexité
• Graphe non
• Graphe connexe :
connexe :
Tous les sommets sont
Il existe des sommets
reliés entre eux
non reliés entre
eux

30 Taicir Loukil

15
 Isomorphismes :
Graphes isomorphes : on dit que le graphe non orienté (resp. orienté) G =(X, U)
et G’ = (X’, U’) sont isomorphes s’il existe une correspondance un à un entre les
sommets de G et G’, tel que le nombre d’arêtes (resp. arcs) reliant chaque paire
de sommets dans G est égal au nombre d’arêtes (resp.d’arcs) reliant la paire de
sommets correspondants dans G’. Plus précisément mathématiquement :

Deux graphes G = (X, U) et G’ = (X’, U’) sont dits isomorphes s’il existe une
bijection BX : X => X’ et une bijection BU : U => U’ ayant la propriété suivante:

Soit u  U, (u = (x, y)) alors BU (u) a pour extrémité initiale BX(x) et extrémité
terminale BX(y) Taicir Loukil
31

Coloriage des sommets d’un graphe non orienté

Nombre chromatique :
affecter tous les sommets d’un graphe d’une couleur de telle
sorte que deux sommets adjacents ne portent pas la même
couleur.

Le nombre nécessaire de couleur = Nombre chromatique

Taicir Loukil
32

16
 Exemple
Couleur 1 :A , C
couleur 2 : B, D

Nombre chromatique = 2?

Taicir Loukil
33

Application : Planning d’examens

• Une université doit organiser les horaires des examens de
rattrapage. On suppose qu’il y a 7 épreuves à planifier,
numérotées de 1 à 7 :
• Les paires de cours suivantes ont des étudiants en
commun : 1 et 2, 1 et 3, 1 et 4, 1 et 7, 2 et 3, 2 et 4,
2 et 5, 2 et 7, 3 et 4, 3 et 6, 3 et 7, 4 et 5, 4 et 6, 5
et 6, 5 et 7 et 6 et 7.
• Comment organiser ces épreuves de façon qu’aucun
étudiant n’ait à passer deux épreuves en même temps et
cela sur une durée minimale ?
Taicir Loukil
34

17
 Aquariophilie
• A, B, C, D, E, F, G et H désignent huit poissons ; dans
le tableau ci-dessous, une croix signifie que les poissons
ne peuvent cohabiter dans un même aquarium :

Taicir Loukil
35

Problèmes d’ordonnancement
B
3 4 4 E
A 3 C 8 8 2 fin

0 0 3 3 3 10 10
5
5 7 3
3 3 5 2 F

D Dates au plus tôt

Dates au plus tard
Chemin(s) critique(s)

Sommets = tâches à réaliser

Arcs = relation d’antériorité (valuation : durée de la tâche initiale)

Taicir Loukil
36

18
 Autres domaines d’application…
• Géographie (cartographie), architecture (plans), linguistique
(sémantique), etc.
• Le WEB (graphe des liens, calcul de pertinence dans les moteurs de
recherche, etc.)
• Graphes « petits mondes » (Kevin Bacon)
• Les réseaux optiques (producteurs-consommateurs, bande passante, etc.)
• Bases de données (dépendances)
• Bases de connaissances
• Techniques de compilation
• Imagerie numérique (scènes, compression)
• Grammaires de graphes (aspects dynamiques)
• Etc.

Taicir Loukil
37

19