Université Hassan II

École Normale Supérieure de l’enseignement

technique de Mohammedia
Filière Ingénieurs

Fatiha AKEF

1
 Table des matières
• Introduction
• Ch1 : Notions de Base
• Ch2 : Chemins et chaines de longueur extrémal (Méthode de FORD et de
DIJKSTRA)
• Ch3 : Evaluation d’ordonnancement (Méthode PERT)
• Ch4 : Chemins/Circuits/Chaines/Cycles Hamiltoniens (Méthode de DEMOUCRON
et de la MULTIPLICATION LATINE)
• Ch5 : Chemins /Circuits/Chaines/Cycles Eulériens (Méthode d’EULER)
• Ch6 : Flot Maximal dans un réseau de transport (Méthode de FORD-FULKERSON)
• Ch7 : Affectation Optimale (Méthode HONGROISE)
• Ch8 : Arbres de poids extrémal (Algorithme de KRUSKAL)

2
Introduction générale

3
Dans plusieurs types de formation la théorie des graphes va de pair avec les disciplines de
l’organisation et de l’information qui sont : théorie de la décision, recherche opérationnelle,
Théorie des jeux, théorie de l’information… .
La théorie des graphes peut être vue comme une branche de Mathématique qui a connue un
développement relativement autonome par rapport aux branches mathématiques qui sont :
l’arithmétique, la géométrie, l’algèbre et l ’analyse.
La théorie des graphes a été fondée par EULER (1707-1783 Natif Suisse) à partir du moment
où il s’y intéressait à la modélisation des problèmes par des figures constituées de points
(Sommets) et de lignes (arêtes) éventuellement orientés.
EULER a été amené à réfléchir sur le problème dit « les sept ponts de KONIGSBERG ».

4
La ville de KONIGSBERG (actuellement KALININGRAD/RUSSIE) comporte deux iles sur le
fleuve « PREGEL » reliées aux deux rives et l’une à l’autre par sept ponts conformément au
plan suivant :

ILE2 ILE1

Question : Est-il possible de suivre un parcours qui passe par chaque pont une fois et une
seul et qui revient au point de départ ?

5
EULER a emmagasiné ce problème dans une figure simple comportant 4 points et 7 lignes.

R1

I2 I1

R2

Remarque : La forme et la longueur des lignes n’importe pas contrairement à la

géométrie qui elle traite les grandeurs.

6
Si il existait un parcours répondant aux critères de l’énoncé alors on devrait suivre les 7
lignes, de cette figure avec un crayon sans jamais le lever et sans jamais repasser deux
fois sur une ligne.
EULER a montré qu’il était nécessaire que le nombre de lignes issues de chaque 4 points
soit pair donc le parcours recherché n’existe pas.
Mieux, en résolvant le problème particulier des 7 ponts de KONIGSBERG, EULER à établi
une condition nécessaire et suffisante générale d’existence de tel parcours (elle sera
représenté au Ch5).
EULER, dans son exposé présenté en 1736 devant l’académie des sciences SAINT-
PETERSBOURG (RUSSIE), explique que la branche de géométrie qui traite les grandeurs a
été soigneusement étudiée, contrairement à une autre branche, nommée en premier

temps par LIBINITZ « géométrie de situation », cette branche de la géométrie

traite des relations qui dépendent seulement de la position, situation, adjacence …etc,
et non pas de grandeurs et les calculs sur les quantités.
7
Mais on n’a pas donné de définitions satisfaisantes des problèmes qui appartiennent à

cette géométrie, ni des méthodes qu’on doit employer pour résoudre ces problèmes.

C’est ainsi qu’ EULER formalise les premiers concepts, établit et expose les premiers

théorèmes de ce qui allait devenir « la théorie des graphes ».

Deux siècles et demi plus tard la théorie des graphes ne se préoccupe pas que de la

position des points et des lignes, elle prend en compte (à des degrés variés) les

grandeurs et les calculs sur les quantités.

Mais l’idée de Géométrie de situation reste au centre de son identité.

8
Dans les chapitres qui suivent nous aborderons plusieurs familles de problèmes que l’on

peut exprimer et résoudre assez facilement au moyen de modèles et techniques

conçues dans le cadre de la théorie des graphes.

Par exemple :

- Détermination d’itinéraire de longueur optimal.

- Conduite d’un chantier composé de taches indépendantes.

- Transport de marchandises ou de fluides à travers des réseaux de communication ou

distribution.

- Détermination de meilleure tournée de livraison ou visite.

- Affectation de moyens pour réaliser au mieux un ensemble de taches.

9
 Chapitre 1
CONCEPTES ET NOTIONS DE BASES

10
I. NOTION NON ORIENTEE
1. Graphe non Orienté :

Formellement c’est un triplet (X, U, Ø)

X, U sont des ensembles avec X non vide
et Ø c’est une application définie par :

Ø:U X^X
u {a,b} = {b,a}
^ : C’est le produit non ordonné de X par X (ensemble des paires d’éléments de X)
• Les éléments de X^X seront noté {a,b} = {b,a}
• Les éléments de X sont appelés des sommets ou nœuds
• Les éléments de U sont appelés des arêtes
• a et b sont les extrémités de u

11
Représentation :
b

a {a,b} = {b,a}

Exemple :

1. on dit que a et b sont des sommets adjacents (de même pour a et c)

2. On dit que U1 et U2 sont des arêtes adjacentes

12
 3. U1 est incident en a et en b / U2 est incident dans en a et en c

4. Le degré de x∈X, noté δ(x) est le nombre d’incidentes en x

• Exemple : δ(a)=2 et δ(b)=1

Cas particulier :
a b a
U: Lorsque a = b U:
U est une boucle

a : est dit un point isolé et δ(a)=0

13
Définitions :

1. Si X et U sont finis alors le Graphe est fini ;

2. Un graphe est complet si tous les sommets sont liés
∀ x≠y, il existe au moins une arête d’extrémités x et y ;
3. Un Graphe est Simple si ∀ x≠y, il existe une et une seul arête entre x et y ;

2. Théorème :

Dans un graphe fini le nombre de sommets de degré impair est toujours pair.

Exemple :

14
 a
Les sommets de degré impair sont :a, e
(2 sommets = Nombre pair) c b

e
Preuve : d

Il est évident que est toujours pair, car chaque arête contribue à 2 degrés

or

Avec : Degré des sommets impairs

: Degré des sommets pairs

Alors

Et puisque est toujours pair on conclu que le nombre des

est pair.

15
 3. Chaines, Cycles:

Une chaine d’un graphe (X, U, Ø) est un ensemble fini d’arêtes de la forme :

X0 u1 X1 u2 X2 Xn-1 Un Xn

• La suite (x0 , x1 , …., xn ) est un parcours de sommets de la chaine

• La suite (u1, u2,…., un) est un parcours d’arêtes de la chaine
• x0 et xn sont les extrémités de la chaine
• l’entier « n » mesure la longueur de la chaine en nombre d’arêtes
• si x0 et xn représentent le même sommet la chaine est dite un cycle

4. Sous –Graphe :

C’est la donnée d’un sous-ensemble de sommets et d’arêtes dont les extrémités

appartiennent a ce sous-ensemble

16
 5. La Connexité :
Un Graphe (non orienté) est connexe ssi :

Il existe une chaine entre x et y.

Soit R la relation définie dans X par :

R : est une relation d’équivalence : réflexive, symétrique, transitive. (évident)

17
Exemple :

Le quotient X/R fournit les classes d’équivalence

X4

Les sous-graphes (évidement connexes) relatifs à chacune de ces classes sont appelées :

« Composantes connexes » du graphe considéré.

18
 II- NOTION ORIENTÉE :
1. Graphe Orienté :

Formellement c’est un triplet (X, U, Δ) X≠0

et :U Xx X
u (a,b) ≠ (b,a)

x : c’est le produit cartésien ou produit ordonné des éléments de X (ensemble des

couples d’éléments de X)

 les éléments de X : sont des sommets ou des noeuds

 les éléments de U: sont des arcs (ou arêtes orientées)

19
Représentation :
b
(a,b)
a

a : extrémité initiale de U ‘’aussi’’ a père de b

b : extrémité finale de U ‘’aussi’’ b fils de a
• Si a = b → boucle
• On note Г(x) l’ensemble des fils de x
Г : fonction de succession

b  U est un arc incident en a extérieurement (ou

U: positivement)
 U est un arc incident en b intérieurement (ou
a
négativement)

20
→ le nombre d’arcs incidents positivement en a s’appelle le demi-degré positif en a et se note
δ+(a)
→ le nombre d’arcs incidents négativement en a s’appelle le demi-degré négatif en a et se note
δ-(a)

→ δ+(a) = δ-(a) = 0 « a » isolé

→ X et U finis, le Graphe orienté est fini, on peut définir δ :

δ(a)= δ+(a) + δ-(a) δ degré dans le graphe non orienté associé

Remarque:
∑ 𝜹+(x)= ∑ 𝜹-(x)

Chaque arc contribue à un

demi-degré positif et un
demi-degré négatif

21
 2 . Chemins / circuits :

Un chemin d’un graphe orienté (X,U, Δ) est un ensemble fini d’arcs de la forme

 X0 : extrémité initiale l’entier « n » mesure la longueur du

 Xn : extrémité finale chemin en nombre d’arcs
Si X0 et Xn représentent le même sommet le chemin et un circuit

3 . Sous Graphe :

C’est la donnée d’un sous ensemble de sommets et d’arcs dont les extrémités
appartiennent à sous ensemble

22
 4 : Forte connexité :

Un graphe orienté est fortement connexe si et seulement si :

Pour tout couple de sommets distincts x et y il existe un chemin joignant x à y et il existe
un chemin joignant y à x.

→ On définit la relation R suivant :

𝑥=𝑦
∀ 𝑥, 𝑦 ∈ 𝑋 ; 𝑥R𝑦 → 𝑜𝑢 𝑖𝑙 𝑒𝑥𝑖𝑠𝑡𝑒 𝑢𝑛 𝑐ℎ𝑒𝑚𝑖𝑛 𝑗𝑜𝑖𝑔𝑛𝑎𝑛𝑡 𝑥 à 𝑦
𝑒𝑡 𝑖𝑙 𝑒𝑥𝑖𝑠𝑡𝑒 𝑢𝑛 𝑐ℎ𝑒𝑚𝑖𝑛 𝑗𝑜𝑖𝑔𝑛𝑎𝑛𝑡 𝑦 à 𝑥
R est une relation d’équivalence :
- Réflexive (par définition)
- Symétrique (par définition)
- Transitive (évident)

23
Exemple:
Le Quotient X/R Fournit les classes d’équivalence {C1, C2, C3}
C1

Les sous-graphes (évidement fortement connexes) relatifs à

chacune de ces classes sont appelées : C3
C2
« Composantes fortement connexes » du graphe considéré. X4

24
 Chapitre 2
Chemins et chaines de Longueur extrêmale
« Méthode de Ford et de Dijkstra »

25
POSITION GÉNÉRAL DU PROBLEME

• On s’intéresse ici aux graphes finis, valués à chaque arc (arrêt) (x,y) on associe

un nombre réel noté l(x,y) et dit longueur de l’arc (x,y)

• Dans le contexte qui suit on appelle longueur d’un chemin la somme des

valeurs associés aux arcs (arrêtes) qui le compose.

• On recherche des chemins (chaines) de longueur Minimal ou Maximal entre

deux sommets. On pourra dire chemin Minimal (chaine Minimal) au lieu de

chemin de longueur Minimal (de même pour Max).

26
I. MÉTHODE DE FORD

1. Hypothèses et Notations :

Pour cette méthode on considère les graphes finis, orientés, connexes, valués,
sans circuit de longueur négative.
Soit {X0, X1, X2, …., XN} l’ensemble des sommets du graphe.
NOTATION :
On fixe X0
1. π(Xi) : désigne le plus court chemin depuis X0 vers Xi pour i allant de 0 à N.
2. Pi : désigne les pères de Xi pour i allant de 0 à N.
3. L(Pi, Xi) : désigne la longueur de l’arc (Pi, Xi).
BUT : Fournir tous les plus courts chemins π(Xi) pour i allant de 0 à N.

27
2. Algorithme de FORD :

Initialisation :
π(X0) π(X1) ..... π(XN)
0
+∞ +∞ +∞

POUR i = 0,1, ….., N Faire

Tant que Pi existe faire
>
SI π(Xi) π(Pi) + l(Pi, Xi)
Alors π(Xi) π(Pi) + l(Pi, Xi)
FINSI
FIN TANT QUE
FINPOUR

28
2. Algorithme de FORD :

Initialisation :

π(X0) π(X1) ... π(XN)

0 +∞ +∞ +∞

Pour i = 1, ….., N Faire

Tant que Pi existe faire
Si π(Xi) > π(Pi) + l(Pi, Xi)
Alors π(Xi) π(Pi) + l(Pi, Xi)
Fin si
Fin tant que
Fin pour

29
3. Exemple Par FORD :

Soit le graphe suivant :

X3
2 7
X1
X5

3 6 6 2
2

X0 X4
8 1
X2

30
Correction :

Initialisaton :

π(X0) π(X1) π(X2) π(X3) π(X4) π(X5)

0
+∞ +∞ +∞ +∞ +∞

X1

P1 = X0
π(X1) >? π(X0) + l(X0, X1)
+∞ > 0 + 3
Alors π(X1) 3

31
X2 X2 posède deux pères donc deux études à faire :

1) P2 = X0
π(X2) >? π(X0) + l(X0, X2)
+∞ > 0 + 8
Alors π(X2) 8
2) P2 = X3
π(X2) >? π(X3) + l(X3, X2)
Nous avons besoin de π(X3)
X3 X3 possède aussi deux pères donc deux études à faire :

1) P3 = X0
π(X3) >? π(X0) + l(X0, X3)
+∞ > 0 + 6
Alors π(X3) 6

32
2) P3 = X1
π(X3) >? π(X1) + l(X1, X3)
6 >? 3 + 2
Alors π(X3) 5

Retour à X2

π(X2) >? π(X3) + l(X3, X2)

8 >5+2
π(X2) 7

X4 X4 possède aussi deux pères donc deux études à faire :

1) P4 = X1
π(X4) >? π(X1) + l(X1, X4)
+∞ > 3 + 6
Alors π(X4) 9

33
 2) P4 = X2
π(X4) >? π(X2) + l(X2, X4)
9> 7 + 1
Alors π(X4) 8

X5 X5 possède aussi deux pères donc deux études à faire :

1) P5 = X3
π(X5) >? π(X3) + l(X3, X5)
+∞ > 5 + 7
Alors π(X5) 12
2) P5 = X4
π(X5) >? π(X4) + l(X4, X5)
12> 8 + 2
Alors π(X5) 10

34
π(X0) π(X1) π(X2) π(X3) π(X4) π(X5)

0 +∞ +∞ +∞ +∞ +∞

3 8 6 9 12

7 5 8 10

35
II. Méthode de MORE-DIJKSTRA
1. Hypothèses et Notations :

On considère les graphes finis, orientés, connexes et valués positivement

NOTATION :
On fixe X0
1. π(Xi) : désigne le plus court chemin depuis X0 vers Xi pour i allant de 0 à N.
2. Fi : désigne un fils de Xi pour i allant de 0 à N.
3. Γ(Xi) : l’ensemble de tous les fils de Xi pour i = 0,1, 2, …. N
4. L(Xi, Fi) : désigne la longueur de l’arc (Xi, Fi).
BUT : Fournir tous les plus courts chemins π(Xi) depuis X0 vers Xi

36
2. Exemple Par MORE Dijkstra :

X2
4 X4

7 5
2
X1
5 1
X5
1

2 3
X3
7
X6

37
 Initialisaton :

π(X1) π(X2) π(X3) π(X4) π(X5) π(X6)

0
+∞ +∞ +∞ +∞ +∞

Sélection de X1

et
donc
𝜋 𝑋2 ← min { 𝜋 𝑋2 ; 𝜋 𝑋1 + 𝐿 𝑋1 ; 𝑋2 } = 7

𝜋 𝑋3 ← min { 𝜋 𝑋3 ; 𝜋 𝑋1 + 𝐿 𝑋1 ; 𝑋3 } = 1

38
Sélection de X3

𝑆 = 𝑋1 ; 𝑋3 et 𝑆ҧ = 𝑋2 ; 𝑋4 ; 𝑋5 ; 𝑋6
Γ 𝑋3 = 𝑋2 ; 𝑋5 donc Γ 𝑋3 ∩ 𝑆ҧ = 𝑋2 ; 𝑋5
𝜋 𝑋2 ← min { 𝜋 𝑋2 ; 𝜋 𝑋3 + 𝐿 𝑋3 ; 𝑋2 } = 6
𝜋 𝑋5 ← min { 𝜋 𝑋5 ; 𝜋 𝑋3 + 𝐿 𝑋3 ; 𝑋5 } = 3

Sélection de X5

𝑆 = 𝑋1 ; 𝑋3 ; 𝑋5 et 𝑆ҧ = 𝑋2 ; 𝑋4 ; 𝑋6
Γ 𝑋5 = 𝑋2 ; 𝑋4 donc Γ 𝑋5 ∩ 𝑆ҧ = 𝑋2 ; 𝑋4
𝜋 𝑋2 ← min { 𝜋 𝑋2 ; 𝜋 𝑋5 + 𝐿 𝑋5 ; 𝑋2 } = 5
𝜋 𝑋4 ← min { 𝜋 𝑋4 ; 𝜋 𝑋5 + 𝐿 𝑋5 ; 𝑋4 } = 8
39
Sélection de X2

𝑆 = 𝑋1 ; 𝑋3 ; 𝑋5 ; 𝑋2 et 𝑆ҧ = 𝑋4 ; 𝑋6
Γ 𝑋2 = 𝑋6 ; 𝑋4 donc Γ 𝑋2 ∩ 𝑆ҧ = 𝑋6 ; 𝑋4
𝜋 𝑋4 ← min { 𝜋 𝑋4 ; 𝜋 𝑋2 + 𝐿 𝑋2 ; 𝑋4 } = 8
𝜋 𝑋6 ← min { 𝜋 𝑋6 ; 𝜋 𝑋2 + 𝐿 𝑋2 ; 𝑋6 } = 6
Sélection de X6

𝑆 = 𝑋1 ; 𝑋3 ; 𝑋5 ; 𝑋2 ; 𝑋6 et 𝑆ҧ = 𝑋4
Γ 𝑋2 = 𝑋5 ; 𝑋3 donc Γ 𝑋6 ∩ 𝑆ҧ = ∅

40
Sélection de X4

𝑆 = 𝑋1 ; 𝑋3 ; 𝑋5 ; 𝑋2 ; 𝑋6 ; 𝑋4 et 𝑆ҧ = ∅
On s’arrête

π(X1) π(X2) π(X3) π(X4) π(X5) π(X6)

0 +∞ +∞ +∞ +∞ +∞

7 1 8 3 6
6
5

41
2. Algorithme de MORE-DIJKSRTA :

Initialisation

π(X0) π(X1) ... π(XN)

0 +∞ +∞ +∞

𝑺 ← 𝑿𝟎
ഥ
𝑺 ← 𝑿𝟏 , 𝑿𝟐 , … , 𝑿𝑵
j ← 0

42
Tant que ഥ
𝑺 ≠ ∅ faire

Pour tout 𝑿𝒊 fils de 𝑿𝒋 appartenant à ഥ

𝑺 Faire
𝝅 𝑿𝒊 ← 𝐦𝐢𝐧 𝝅 𝑿𝒊 , 𝝅 𝑿𝒋 + 𝑳(𝑿𝒋 , 𝑿𝒊 )
Déterminer 𝑿𝒋 ∈ ഥ 𝑺 tel que
𝝅 𝑿𝒋 = 𝐦𝐢𝐧 𝝅 𝑿𝒊

ഥ
𝑺 ←ഥ
𝑺 − 𝑿𝒋
𝑺 ← 𝑺 ∪ 𝑿𝒋
Fin tant que

43
Traiter l’exemple suivant par les deux méthodes précédentes :

7 3

A
1 E
5
7
9
C
8
D

Recherche du plus court chemin du point A vers tous les autres sommets

44
EXERCICE :
On considère le graphe G suivant :

1 2
A C E

2
4 5 15

B D F
1 4

45
PREMIÈRE PARTIE : METHODE DE MOORE-DIJKSTRA

1. Décrire l’algorithme de base de MOORE-DIJKSTRA

2. Utiliser l’algorithme de MOORE-DIJKSTRA sur le graphe G pour obtenir tous les plus courts
chemins à partir du sommet A

DEUXIEME PARTIE : MÉTHODE DE FORD

1. Décrire l’algorithme de base de FORD

2. Utiliser l’algorithme de FORD sur le graphe G pour obtenir tous les plus courts chemins à
partir du sommet A

46
A B C D E F

0 +∞ +∞ +∞ +∞ +∞

5 1 5 2 7

4 1 3 2 7
A—C—D—B A—C A—C—D A—E A—C—D—E

47
Chapitre 3

Méthode PERT

48