CHAPITRE I : LES GRAPHES

I.1. LES NOTIONS FONDAMENTALES DE LA THEORIE DES GRAPHES

DEFINITIONS ET EXEMPLES DES GRAPHES

I.1.1. Définitions

Un graphe G est un couple (X,u) où :

 X est un ensemble non vide et au plus dénombrable dont les éléments

sont appelés « sommets » du graphe G.
 u est une famille d’éléments du produit cartésien XxX = { ( x , y ) / x , y ∈ X }
les éléments de u sont appelés :
- arcs ou
- arêtes

Un arc (x,y) représente une liaison orientée entre l’origine x et l’extrémité y.

u = (x,y) : x y
extrémité extrémité
initiale de u terminale de u

Si on fait abstraction à cette orientation, cet arc devient une arête c’est-à-dire
qu’une arête est un arc non orienté.

v=(x,y)=(y,x)
x y
extrémité extrémité
initiale de v terminale de v

Un arc dont l’extrémité initiale coïncide avec l’extrémité terminale s’appelle

"boucle".

Boucle : u =(x,x) x

Remarques :

 Graphiquement, les sommets seront représentés par les points du plan

affines et les arcs par les segments ou courbes simples orientés.
 L’ordre du graphe G c’est le nombre de ses sommets. Si G = (X,u) et
|X| = X = n, alors on dit que G est un graphe d’ordre n.
 Tout graphe admet une représentation sagittale ou diagramme dans le plan
affine mais cette représentation du point de vue de la forme n’est pas unique.
Dès lors les graphes que nous considérons sont des graphes topologiques
c’est-à-dire même si les représentations ne sont pas de la même forme mais
elles traduisent toujours la même structure du point de vue des relations entre
les sommets.
 Deux arcs u et v sont dits de la même forme ssi ils ont une même
extrémité initiale et une même extrémité finale.

u=(x,y)¿} ¿ ¿sont de la même forme¿

 G = (X,u) est dit un p-graphe d’ordre n ssi G contient n sommets et le
maximum d’arcs de même forme est le naturel p.

I.1.2. Exemples de graphe G = (X,u),

1° Soit G = (X,u), où x={ x 1 , x 2 , x 3 , x 4 , x 5 , x 6 } et u=(u1 , u2 , u3 , u 4 , u5 , u6 ,u7 )

avec
u1 =( x 1 , x2 ) ; u2 =( x 1 , x 2 ); u 3=( x 3 , x 4 ) ; u4 =(x 4 , x5 ) ; u5 =( x5 , x 6 ) ; u6 =( x1 , x 6 ) ; u 7 =( x 2 , x 3 )
La représentation sagittale de G est :
u1
X1
u2

u6
X2
G = (X,u) est un 1-graphe d’ordre 6
u7
u3
X3 u4 X6
X4
u5
X5

2° Soit G = (X,u), où :

X = { a , b , c ,d , e , f } et u=(u 1=(a , b ), u2 =( a , b), u 3=(b , b ),
u4 =(e , f ), u 5=(c , e), u6 =(d , d ), u 7 =(e , d ), u8 =(f , e ), u 9=(f , e), u10=( f , e),u11 =( b , e ), u12=(e , b ))

u2 u3
a
b
G = (X,u) est un 3-graphe d’ordre 6
u1
- Les arcs u1 et u2 sont de la même forme car
u11 u12 u1=(a,b) et u2=(a,b)
u4 - Les arcs u8,u9 et u10 sont aussi de la même
d
u6 u10
f forme.
e
u7 u9
u5 u8

c
THEOREME 1 :

« Si G = (X,u) est un 1-graphe d’ordre n alors dans ce cas et dans

ce cas seulement on a que u ⊂ XxX : u = {u1 ,u2 ,. .. , ur } , r étant le nombre
d’arcs de ce un 1-graphe ».

Preuve :
En effet, il est trivial que ∀ u , v ∈u , u et v sont de forme
différente ssi G = (X,u) est un 1-graphe d’ordre n.
Si par contre G = (X,u) est un p-graphe d’ordre n, avec p=1, c’est qu’alors
qu’il existe dans u au moins 2 arcs de même forme, dès lors u n’est plus un
sous-ensemble de XxX mais plutôt une famille d’éléments XxX.

NOTA :
Nous allons nous arranger de façon à avoir toujours des 1-
graphes, donc u sera toujours un sous-ensemble de XxX.

I.2. AUTRES DEFINITIONS IMPORTANTES LIEES A LA NOTION

DES GRAPHES

I.2.1. Notions de prédécesseur – successeur – voisin

Soit le graphe G = (X,u) et supposons qu’il existe un arc de la

forme (x,y) dans G.

a) Définitions :

 Un sommet y est dit « successeur » d’un sommet x dans G = (X,u) ssi il

existe un arc u =(x,y) : x y

 Un sommet y est dit « prédécesseur » d’un sommet x dans G = (X,u)

ssi il

existe un arc u =(y,x) : y x

 Un sommet y est dit voisin d’un sommet x dans G = (X,u) ssi y est dit
soit :
- un successeur
- un prédécesseur
+
Notons par : Γ G ( x ) =l’ensemble des successeurs du sommet x dans G.
−
Γ G ( x ) =l’ensemble des prédécesseurs du sommet x dans G.
 Γ G ( x ) = l’ensemble des voisins du sommet x dans G.
b) THEOREME 2 :
+ −
Γ G=Γ G ( x )∪Γ G ( x )

La preuve est triviale en vertu de la définition

Un sommet x dans G = (X,u) est un sommet isolé ssi Γ G ( x )=φ c’est-à-dire

ssi le sommet x n’a pas de voisin.

c) Définition d’un graphe par une application (au sens de l’Algèbre)

(Définition 2)

 Si x est un sommet du graphe G = (X,u), alors notons par :

S(x)= »La famille des successeurs de x dans G.

Exemple :

Soit G = (X,u) donné par sa représentation sagittale dans E2 :

X2
X1
G = (X,u) est un 2-graphe d’ordre 5
S(x1) = (x2,x2)
X3 S(x2)=(x3,x5,x1)
X4
S(x3)=(x2,x5)
S(x4)=(x1,x4,x5)
S(x5)=(x3,x5)
X5
 Remarques :

1° Si x ∈ X est sommet isolé de G = (X,u) alors on note S(x)=()

2° Si G = (X,u) est un 1-graphe d’ordre n alors on a dans ce cas et dans ce
cas seulement :
∀ x ∈ X , S(x)=Ensemble des successeurs de x dans G.
3° S G= { S ( x ) / x ∈ X }  : c’est l’ensemble des familles de successeurs de tous les
sommets x ∈ X du graphe G = (X,u).

Si nous reprenons l’exemple précédant, SG = { S( x 1 ), S( x 2 ), S( x 3 ), S( x 4 ), S ( x 5 )}

SG= {(x 2 , x 2 ),( x 1 , x 3 , x5 ),( x 2 , x5 ),( x 1 , x 4 , x5 ),( x 3 , x5 ) }

 Définissons l’application Γ : X → SG : x ↦ Γ ( x )=S ( x ) .

Il va de soi que Γ définie sur X et à images dans SG est une application au
sens de l’Algèbre.

 Définition 2 d’un graphe :

G = (X, Γ ), où X : ensemble au plus dénombrable

Γ  : L’application : Γ  : X → SG : x ↦ SG ( x )

I.2.2. Degré, adjacence et incidence

a) Degré, Demi degré d’un sommet i de G = (X,u)

+
1° Le Demi-degré extérieur du sommet i de G noté d G (i): c’est le nombre
d’arcs ayant le sommet i comme extrémité initiale (c’est-à-dire c’est le
nombre d’arcs partant de i).
i

+
d G (i)=4

−
2°Le Demi-degré intérieur du sommet i note d G (i)  : c’est le nombre d’arcs
ayant i comme extrémité terminale (c’est-à-dire c’est le nombre d’arcs
aboutissant à i).

i
−
d G (i)=5

+ −
3° Le Degré de i dans G noté d G (i)=dG (i )+d G (i)  ; c’est le nombre d’arcs
admettant i comme extrémité.

b) Adjacence et incidence

1°) Adjacence

Soit le Graphe G = (X,u)

 Deux sommets x et y ∈ x avec x ¿ y, sont dits adjacents dans G s’ils

sont reliés par un arc :

x y
  Deux arcs u et v ∈ u sont dits adjacents s’ils ont une extrémité
commune.
b
a u
w
v
c
2°) Incidence

Soit le Graphe G = (X,u) et A ⊂ X

+ −
On définit les ensembles suivants : ω ( A ) et ω ( A ) .
 ω+ ( A ): c’est l’ensemble des arcs ayant leur extrémité initiales dans A
et leur extrémités terminales dans A= X− A .
 ω− ( A ): c’est l’ensemble des arcs ayant leur extrémités terminales dans
A et leurs extrémités initiales dans A= X− A
+ −
 On note ω( A )=ω ( A )Uω ( A ): l’ensemble des arcs incidents à A ⊂ X .

NOTA :

 La notion d’adjacence concerne les sommets ou les arcs

 Un ensemble d’arcs (ou d’arêtes) de la forme ω( A ) est appelé « un
cocycle  » de G = (X,u) ; où A ⊂ X.
 Un graphe est dit régulier si les degrés de tous ses sommets sont
égaux.

c) Soit G=(x, u) et x,y ∈ x

+
- On note par m G ( x , y ): le nombre d’arcs de G ayant x comme
extrémité initiale et y comme extrémité terminale.
−
- On note par m G ( x , y ): le nombre d’arcs de G ayant x comme
extrémité terminale et y comme extrémité initiale.

I.3. QUELQUES TYPES DE GRAPHES

Nous pouvons mettre en évidence quelques types particuliers de

graphes qui joueront un rôle important dans les applications, nous pouvons
citer :
- Le graphe simple
- Le graphe symétrique
- Le graphe anti-symétrique
- Le sous-graphe
 - Le graphe partiel
- Le graphe biparti
- Le graphe complet.

a) Graphe simple

Un graphe simple G = (X,u) est un 1-graphe sans boucle. La

notion de multigraphe : c’est un p-graphe sans boucle (où en général les arcs
sont remplacés par les arêtes).
b) Graphe symétrique

G = (X,u) est un graphe symétrique ssi :

+ −
∀ x , y ∈ x :mG ( x , y )=mG (x , y )⇔∀ x , y ∈ X ,
il y a autant d’arcs de la forme (x,y)
que de la forme(y,x) ou encore ∀ x , y ∈ X , le nombre d’arcs de la forme
(x,y)= le nombre d’arcs de la forme (y,x).

c) Graphe anti-symétrique

G = (X,u) est dit graphe anti-symétrique ssi ∀ arcs (x,y) ∈ u :

+ −
(y,x) ∉ u c’est-à-dire ssi ∀ ( x , y ) ∈ X : mG ( x , y )≠0⇒ mG ( x , y )=0 .
Ou Un 1-graphe G=(x,u) est anti-symétrique ssi ∀ x , y ∈x :
+ −
m G ( x , y )+m G ( x , y )≤1

d) Sous-graphe de G = (X,u)

Soit A ⊂ X, alors le sous-graphe de G est le graphe noté GA

défini par :
- ses sommets sont les éléments de A ⊂ X
- ses arcs sont les arcs de G ayant leurs deux extrémités dans A.

e) Graphe partiel de G=(x,u)

Soit G = (X,u) et v une partie de u, (c’est-à-dire v ⊂ u) ; le

graphe partiel de G relativement à V est le graphe G’=(x,v).

f) Graphe biparti

Le graphe G = (X,u) est dit biparti noté G=(x1,x2,u) ssi x1 ¿ φ

 X 2 ≠φ et X 1 + X 2 =X et ∀ x , y ∈ Xj ,( j=1,2 ): x et y ne sont jamais adjacents.
Autrement dit, un graphe G = (X,u) est dit graphe biparti ssi l’ensemble de ses
sommets peut être partitionner en 2 clases x1 et x2 de sorte que 2 sommets de
la même classe ne soit jamais adjacents.

g) Graphe complet (ou n-clique)

Le graphe G = (X,u) est dit graphe complet (ou est un n-clique) si

+ −
mG(x,y)=m y )+mG ( x , y )≥1 , ∀ x , y ∈ x avec x≠ y ⇔∀ x , y ∈ x avec x≠ y ∃ toujours
G( x,

un arc qui les relient ⇔ ∀ x , y ∈ x  : x et y sont (au moins) adjacents.

Autrement dit, un graphe complet est un graphe où chaque sommet est relié à
tous les autres ou un graphe est dit complet si tous les nœuds (sommets) sont
adjacents 2 à 2. C’est-à-dire ( x , y ) ∈U ⇒ ( y , x ) ∈U .
Exemple : Contre-exemple :
b c
a a

b
c

Un graphe complet simple (c’est-à-dire un 1-graphe simple

complet) est noté Kn et s’appelle un n-clique.

I.4. QUELQUES MATRICES ASSOCIEES AUX GRAPHES

Soit G= ( x , u ), où x={ x 1 x 2 ,. .. , x n } et u=(u1 , u 2 , .. . ,u n ).

i +
Posons : a j =m G ( x i x j )
i
La matrice carré A=(a j ), où i est l’indice des lignes et j est
l’indice de colonnes s’appelle la matrice associée à tout p-graphe d’ordre n. La
i
matrice carré A=( a j ) concerne tout p-graphe (p ¿ 1 ) c’est pour cette raison
que cette matrice est appelée la matrice associée aux p-graphes.

Il existe plusieurs types de matrices associées à 1-graphe selon l’importance

qu’on peut accorder à ce graphe, on peut citer :

1) Matrice d’incidence sommets-arêtes

Exemple : Soit le graphe G = (X,u) suivant :
1 2

C’est un 1-graphe d’ordre 4

3

La matrice d’incidence sommet-arête est la suivante :

A= (a iu )=¿ 1 si ∈ u¿¿¿¿
{
u1 u 2 u3 u 4 u 5 u 6 u 7 u 8
i
1
A=( a j )=2
3
4
[ 1 1 0 0 0 0 1 1
0 1 1 0 0 1 0 0
0 0 0 0 1 0 0 1
0 0 0 1 0 1 1 0
]
2) Matrice d’incidence sommets – arcs

Un graphe peut être représenté par une matrice nxm(n= |X| et

m= |U|) , dite d’incidence pouvant contenir uniquement les valeurs 0,1, -1.
Chaque ligne de la matrice est associée à un nœud (sommet) et chaque
colonne à un arc. Ainsi, une case iditique la relation qu’il existe entre un
sommet et un arc.

 0 Signifie que le sommet et l’arc ne sont pas adjacents ;

 1 signifie que le sommet est l’extrémité initiale de l’arc ;
 -1 signifie que le sommet est l’extrémité terminale de l’arc.

Exemple : Soit le graphe G = (X,u)

2 d 4
a
1
c
e f
h
b
g 5 G = (X,u) est un 2-graphe d’ordre 5.
3

La matrice d’incidence sommets-arcs est :

 a b c d e f g h
1
A=( aij )= 2
3
4
5
[ 1 1 0 0 0 0 0 0
−1 0 −1 1 0 0 0 0
0 −1 1 0 −1 0 −1 0
0 0 0 −1 1 1 0 −1
0 0 0 0 0 −1 1 1
3) Matrice d’incidence sommets-sommets (ou Matrice d’adjacence)
]
Un graphe peut être représenté par une matrice nxn (n= |x|) dite
d’adjacence, pouvant contenir uniquement les valeurs 0 ou 1. Chaque ligne et
colonne de la matrice représentent un sommet. Ainsi, une case indique la
relation qu’il existe entre deux sommets.

- 0 signifie que les 2 sommets ne sont pas reliés par un arc.

- 1 signifie que les 2 sommets reliés par un arc.

Exemple : Le graphe précédent sera représenté par la matrice suivante :

1 2 3 4 5

I.5. CONNEXITE ET FORTE CONNEXITE

[ ]
1 0 1 1 0 0
A=( aij )= 2 0 0 0 1 0
3 0 1 0 0 0
4 0 0 1 0 1
5 0 0 1 1 0

I.5.1. Etude de la connexité

a) Chaîne

Une chaîne de longueur q est une séquence de q arêtes notée

Lq=(u1,u2,…,uq) tel que chaque arête ur(2 ¿ r≤q−1 ) ait une extrémité
commune avec l’arête ur-1 et l’autre extrémité avec l’arête ur+1(ur-1 ¿ ur et ur+1
¿ ur). Autrement dit, une chaîne de longueur q est une succession de q
arêtes tel que l’extrémité de l’arête précédente coïncide avec l’extrémité de la
suivante (sauf l’extrémité initiale et l’extrémité terminale de la séquence). La
longueur de la chaîne est le nombre d’arêtes qui la composent.

Exemple : Soit G = (X,u).

 X2 u3 X5

u4
u1 u6
u2
X3
u5
X1 u7 L 4=(u1,u3,u6,u7) est une chaîne de
X4
longueur 4.

NOTA :
- Une chaîne simple est une chaîne qui ne contient pas 2 arêtes
égales ;
- Une chaîne élémentaire est une chaîne qui en le parcourant on ne
rencontre pas 2 fois le même sommet.

Exemple :
L4=(u1,u3,u6,u7) est une chaîne simple (et est aussi une chaîne élémentaire).
L4=(u2,u3,u4,u7) est une chaîne élémentaire (et simple)
Contre-exemple :
L5=(u2,u3,u4,u7, u6) n’est pas une chaîne élémentaire car on rencontre x5 2 fois
dans son parcours.

THEOREME 3 :

« Toute chaîne élémentaire est simple mais la réciproque est fausse ».

b) Cycle

Un cycle de longueur q est une chaîne de longueur q dont les 2

extrémités (initiales et terminales) coïncident.

Exemple : Soit le graphe G = (X,u).

X2 u3 X5

u4
u1 u6
u2
X3
u5
X1 u7
X4

C5=(u3,u4,u7,u5,u1) est un cycle de longueur 5.

NOTA : Un cycle sera simple s’il résulte d’une chaîne simple et un cycle
élémentaire est une chaîne élémentaire dont les 2 extrémités coïncident.

c) Graphe connexe – composant connexe

c.1) Graphe connexe

 Le graphe G = (X,u) est dit graphe connexe si ∀ couples de
sommet distincts i, j  ∈ X , ∃ une chaîne joignant i et j.
Autrement dit, un graphe est connexe si l’on peut atteindre n’importe quel
sommet à partir d’un sommet quelconque en parcourant différentes arêtes.

Exemple : Soit G = (X,u)

b u3 c

u2 u4
a u1 u5
e G = (X,u) est un graphe connexe
d

u8 u6

u7
u9 g h

f
La relation ℜ définie sur X par :

∀ i,j
∈X:iℜ j⇔¿ {−soit i=j¿ {ou¿¿¿
Est une relation d’équivalence. Les classes d’équivalence modulo ℜ (induite
par ℜ sur X) de x:x1,x2,…,xr forme une partition de X.

C.2) Composante connexe

Une composante connexe d’un graphe G = (X,u) est un sous-

graphe GA=(A,uA) avec A ⊂ X, connexe maximal (pour l’inclusion) : il n’est
pas possible d’ajouter à A d’autres sommets en conservant la connexité du
sous-graphe.

Les sous-graphes G1, G2, …, Gr engendrés par les sous-ensembles

x1, x2, …,xr sont appelés les r-composantes connexes du graphe G.

d
i k
Exemple :
c
b g3
X h
a b f

j
e j
Le graphe ci-haut possède 3 composantes connexes dont un sommet isolé.
r=3.

Remarques  :

1°) Chaque composante connexe est un graphe connexe.

2°) Le nombre r de composantes connexes de G = (X,u) est appelé le nombre
de connexité de G = (X,u).
3°) Un sommet isolé (de degré 0) constitue toujours une composante connexe
à lui seul.

THEOREME 4 :

« G = (X,u) est un graphe connexe ssi son nombre de connexité r est égale à 1.
C’est-à-dire ssi G = (X,u) n’a qu’une seule composante connexe ».

I.5.2. Graphe fortement connexe et composantes fortement connexes

a) Chemin et circuit

1°) Un chemin de longueur q est une séquence de q arcs tels

que l’extrémité initiale du suivant coïncide avec l’extrémité terminale de l’arc
précédent sauf l’extrémité initiale du chemin et l’extrémité terminale du
chemin.
u1 u2 u4
Exemple  : X 1 u3 X4
X 2 X 5 X 3

Est un chemin de longueur q=4.

NOTA :
- Un chemin simple est celui qui ne contient pas 2 fois le même arc.
- Un chemin élémentaire est celui qui ne passe pas 2 fois par le
même sommet (c’est-à-dire en le parcourant on ne rencontre pas
2 fois le même sommet).

Exemple et contre-exemple : X4
u1 X 2 u2
u3
Soit G = (X,u) X 1 u4
X 5

u7 u5 u6
X 3
X 6
  (u1,u2,u3,u6) est un chemin simple mais (u1,u2,u3,u4) n’est pas un chemin
simple car il passe 2 fois par l’arc u2.
 (u1,u2,u3,u6) est un chemin élémentaire mais (u1,u2,u3,u4) n’est pas un
chemin élémentaire car il passe 2 fois par sommet x2.

THEOREME 5 :

« Tout chemin élémentaire est simple mais la réciproque est fausse ».

2°) Un circuit de longueur q est un chemin fermé (dont les 2

extrémités initiales et terminales) coïncident.

Exemple : u1 X 2
u2
X 1
X 3
u4
u5
u3

X4

(u1,u2,u3,u5) et (u1,u4,u5) sont de circuits de longueur respective 4 et 3.

NOTA :

 Un circuit simple est celui qui résulte d’un chemin simple.

 Un circuit élémentaire est un chemin élémentaire dont les 2 extrémités
coïncident.

Exemple  :
b
a u2
u6
c
(u2,u4,u5,u1) est un chemin simple
u1 u3
u4 (u1,u2,u6,u7,u5) est aussi un chemin simple et
u7
aussi un chemin élémentaire.
d u5
e

THEOREME 6 : « Tout circuit élémentaire est simple mais la réciproque est
fausse ».

b) Graphe fortement connexe

G = (X,u) est dit graphe fortement connexe si

∀ i , j∈ X ,avec i≠ j ,∃ un chemin les reliant.

Exemple : Soit G = (X,u) donné par sa représentation sagittale :

u6

u1 b u3
a c
u2 u4

u5
G = (X,u) est un graphe fortement connexe d’ordre 3.

c) Composants fortement connexes et le nombre de connexité forte

Considérons la relation ℜ définie sur x comme suit :

∀i, j∈X:iℜ j⇔¿ {− soit i=j¿ {ou¿¿¿

Il va de soi que ℜ est une relation d’équivalence. Les classes d’équivalences
module ℜ forment une partition de X en X1, X2,….., Xn.
Les sous-graphes G1,G2,…., Gn, engendrés par les classes d’équivalence sont
des graphes fortement connexes, on les appelle les composantes fortement
connexes de G = (X,u).

THEOREME 7 : « G = (X,u) est fortement connexe ssi r=1  G = (X,u) n’a
qu’un seule composante fortement connexe. C’est-à-dire ∀i , j∈ X , ∃ un
circuit passant par i et j ; En notant que si i=j, le circuit passant par i et j est
de longueur 0 (la réflexibilité de l’Algèbre) ».

Une boucle orientée est un circuit de longueur 1.

Remarques :

1. La suppression d’un sommet x  X de G = (X,u) entraîne la

suppression de ses arcs adjacents tandis que la suppression d’un arc
n’entraîne pas celle de ses extrémités.
2. On appelle « Isthme », un arc d’un graphe G = (X,u) dont la
suppression engendre un autre graphe G’ = (X,u’) qui est non-connexe.

d) Point d’articulation

Un point d’articulation de G = (X,u) est un sommet dont la

suppression augmente le nombre de composante connexe de G.

Exemple : Considérons G = (X,u) donné par sa représentation sagittale :

e
a
u4
u3
d u9 u7
b u11 u2 u6 h

u5 c f u8
g
G = (X,u) est un graphe d’ordre 8, il est connexe (car il n’a qu’une seule
composante connexe) c’est-à-dire G = (X,u) est un graphe connexe d’ordre 8.
Le nombre de connexité vaut 1.
Si on supprime le sommet d  G = (X,u) est non- connexe car le nombre de
connexité vaudra r=2.

I.6. ARBRES ET ARBORESCENCE

I.6.1. Arbres

a) Définition

Un arbre est un graphe connexe sans cycle.

Une forêt est un graphe dont chaque composante connexe est un
arbre.

Exemple  :

Les 3 graphes suivants sont des arbres. Pris ensemble ils constituent une
forêt.
b) Les notions de branches et de cordes
Soit G = (X,u) un graphe et notons part T= (X,u’), un arbre qui
est un graphe partiel de G, alors :
- Les arêtes appartenant à u’ sont appelées les branches de T (ou
relativement T)
- Les arêtes de u ∉ u’ (c’est-à-dire  (u/u’) sont appelées cordes
relativement T.

Exemple : Soit G = (X,u) un graphe connexe, on peut en extraire un Arbre.

u1 b
u8
a u2 e
u3 u9
u6
u5 d
u11
c
u12
u4 u7
u16
f
T= (X,u’), où u’= (U1, U5, U6, U11, U7) : ce sont les branches tandis que (U2,
U3, U4, U12, U11, U9) : ce sont des cordes.
a

b
c

f
d Est un arbre extrait du graphe G = (X,u)
e
précédent.
c) Quelques propriétés caractéristiques des arbres
Considérons un graphe G = (X,u) d’ordre n alors ces propriétés
de caractérisation d’un arbre sont équivalentes :
(1) G est connexe et ne possède pas de cycle ;
(2) G est connexe et possède exactement (n-1) arcs (ou arêtes) ;
(3) G ne contient aucun cycle et possède exactement (n-1) arcs (ou
arêtes) ;
(4) G est connexe, mais perd cette propriété si n’importe qu’elle arête (ou
arc) est supprimé.
Etc.
NOTA : G = (X,u) admet un graphe partiel T=(X, u’) qui est un arbre ssi G =
(X,u) est connexe.

I.6.2. Arborescence

a) Définition

Soit G = (X,u), on dit que le sommet r  X est une racine de G si

∀ x ∈ X , (avec x ≠r) ∃ un chemin de r à x.
Un graphe G = (X,u) est une arborescence de racine r ssi :

{G et un arbre¿ {et ¿¿¿¿

C’est-à-dire Arborescence = Arbre ayant une racine

Exemple : a

b
c j

d
k
i
e h
f
l
g
C’est une arborescence de racine a.

Nota : Un sommet pendant est un sommet sans successeur. En informatique

on les appelle des « feuilles » ou « feuillets ».

b) Graphe quasi – fortement connexe

G = (X,u) est dit quasi – fortement connexe si ∀ (x , y )∈ XxX , ,

avec (x  y),  un sommet z relié à x et à y par 2 chemins :
L’un entre z et x et l’autre entre z et y.
a b

Exemple : - Soit G = (X,u) d

r
h
k
c
Est un graphe quasi- fortement connexe.
j
e
g
f

i
- Toute arborescence (arbre ayant une racine) est un graphe quasi
–fortement connexe. l

THEOREME 8 :

 Tout circuit est un cycle mais la réciproque est fausse

 Un graphe fortement connexe est quasi- fortement connexe mais la
réciproque est fausse
 Tout graphe quasi – fortement connexe est connexe mais la réciproque
est fausse.

c) Caractérisation d’une arborescence c’est-à-dire les caractéristiques pour

qu’un graphe admet une arborescence comme graphe partiel

c.1. Première caractérisation

G = (X,u) admet une racine ssi il est quasi – fortement connexe.

c.2. Deuxième caractérisation

Soit G = (X,u), un graphe d’ordre n, avec n>1 alors les énoncés

(ou propriétés) suivant sont équivalents :
 (1) G est quasi – fortement connexe et sans cycle ;
(2) G est quasi – fortement connexe et admet (n-1) arcs ;
(3) G est un arbre admettant une racine r;
(4) Il existe un sommet r qui est relié à tout autre sommet par un chemin
unique issu de r ;

c.3. Troisième caractérisation

G = (X,u) admet un graphe partiel qui soit une arborescence ssi

G est quasi- fortement connexe.

I.7. GRAPHE PONDÉRÉ – RÉSEAU – RÉSEAU DE TRANSPORT

1) Graphe pondéré

Soit G = (X,u)

 On dit que G est pondéré si à tout arc (i,j)  u on associe un nombre

réel Cij ;
C=( C ij )( i, j ) ∈u
 La matrice est appelée « la matrice de pondération ».
 Le triplet G = (X,u,C) est un graphe pondéré.
NOTA :
- (i,j)  u, la pondération Cij est une valeur numérique résultant d’une
mesure
- Cette mesure peut être :
o Une distance du sommet i au sommet j ;
o Un coût sur l’arc (i, j) ;
o Une pénalité, exemple : Paiement associé à l’arc (i, j) ;
o Une probabilité de transition du sommet i au sommet j ;
o Une durée (temps) entre i et j ;
o Etc.

- Cette mesure est un réel c’est-à-dire peut être positif ou négatif.

2) Réseau

Un réseau est graphe pondéré sans boucle.

Nous considérons un réseau :

(1).
 ℜ = (X,u,) : un graphe pondéré sans boucle ni circuit à valeur
négative

3) Réseau de transport

ℜ = (X,u,) est un réseau de transport  (1) et Cij ≥0 , ∀ ( i , j ) ∈ u ⇔ (1)

et Cij ¿0,∀ i , j∈ X ; avec Cij ¿ M si(2)(i,j) ∉ u . Où M>>0.

M peut être la somme de toutes les pondérations du réseau de transport.

Nota : Dans la suite, lorsqu’on parlera du réseau de transport, on sous-

entendra un réseau sans circuit. Nous allons aussi considérer un réseau de
transport quasi-fortement connexe.
 I.7 : PROBLEME DE CHEMINEMENT OPTIMALE
DANS UN RESEAU :
ALGORITHME DE TREE BUILDER

I.7.1 GENERALITES

a) Introduction

Il existe deux types de problème de cheminement optimal dan un

réseau :

- Le problème de cheminement à valeur minimale appelé

traditionnellement problème de plus court chemin PCC.
- Le problème de chemin à valeur maximal appelé traditionnellement
problème de plus long chemin PLC.

Le problème consiste à chercher le plus court chemin (ou le plus

long chemin) entre :

 un sommet de départ donné et un sommet d’arrivée donné ;

 un sommet et tous les autres ;
 un sommet de départ et un sommet d’arrivée.

b) Problème de plus court chemin (PCC)

Soit G =(x,u) et ℜ =(x,u, C ) un réseau de transport quasi-

fortement connexe et sans circuit (ou encore un réseau de transport connexe
et sans cycle) où ( ij )1≤i, j≤n  ; n =|X|  ; Cij ≥0 ∀ i , j ∈ X avec
C= C
Cij ≡ M >>0 , ∀ ( i , j ) ∉ U .
Le problème de « chemin à valeur minimal : PCC » s’énonce
comme suit :
« Etant donné le réseau R ci-dessus, trouver un chemin μ0 allant d’un
sommet x à un autre sommet y tel que la quantité numérique :

ℓμ = ∑ C ij
0 (1)
(i , j )∈ μ0
soit
NOTA :
1. L’interprétation de ce problème ainsi énoncé est déterminée par le
sens physique des nombres (pondération) Cij .
En effet, si le Cij est le temps nécessaire pour passer du sommet i au
sommet j alors (1) est l’itinéraire du temps minimum pour aller de x à y.
Si Cij est le prix (coût) du trajet entre i et j alors le problème de PCC
consiste à trouver le chemin le moins cher entre x et y.
Si Cij est la distance entre i et j alors (1) est le problème de trouver le chemin
le plus coût entre x et y.

2. Quelque soit la signification physique de Cij , on parle par convention

de trouver le plus court chemin (PCC) entre x et y.

c) Problème de plus long chemin (PLC)

Soit ℜ =(x,u, C ) le réseau de transport quasi-fortement

; n =|X| et ∀ (i , j)∈u  :
C = ( C ij )1≤i, j≤n
connexe et sans circuit positif, où
Cij ¿≠0 ; avec par convention Cij =0 (ou – M) ∀ (i , j)∉u .
Le problème de « chemin à valeur maximal : PLC »  s’énonce comme
suit : « Etant donné un réseau  ci-dessus trouve un chemin μ0 allant
d’un sommet x à un autre sommet y tel que la qualité numérique :

ℓμ =
0
∑ C ij (2)
(i , j )∈ μ0
soit

NOTA : Quelque soit la signification physique des quantités Cij , le problème

(2) est par convention le problème de plus long chemin PLC entre les
sommets x et y du réseau.

d) Arborescence des PCC (ou PLC) dans un réseau

Soit G =(x,u) et ℜ =(x,u, C ) un réseau de transport quasi-

fortement connexe (ou connexe).

1. Etant donné un sommet x (origine, entrée, source ou racine) dans le réseau

ℜ =(x,u, C ) ci-dessus ,construire une arborescence des PCC entre X0 et
tous les autres sommets y ∈ X.
2. Etant donné un sommet X0 (origine, entrée, source) dans le réseau ℜ
=(x,u, C ) ci-haut, construire une arborescence des PLC entre X0 et tous les
autres sommets y ∈ X.
e) Algorithme de résolution des problèmes de chemin optimaux
 Il existe plusieurs algorithmes de résolution des problèmes de
cheminement optimaux mais tous basé sur le principe d’optimalité de Richards
BELLMAN, on peut en citer 2 groupes :

 Les algorithmes "Tree builder";

 Les algorithmes Matriciels;
Les algorithmes Tree builder comme le mot l'indique permettent
de construire l'arbre à valeur optimale entre la racine (source) et les autres
sommets du réseau. Les algorithmes matriciels par contre cherche le chemin à
valeur optimale entre tous les couples de sommet (x,y) ∈ XxX .
Dans ce travail, nous ne considérons que le premier groupe d'algorithme c'est-
à-dire les algorithmes Tree builder.

I.7.2. ALGORITHME TREE BUILDER

I.7.2.1. La technique de base des algorithmes "Tree builder"

Elle consiste à donner à chaque sommet une étiquette ℓ j , la

valeur de cette étiquette est la valeur d'un chemin possible entre l'origine et le
sommet j. une étiquette ℓ j associé au sommet j c'est-à-dire ℓj ¿ j est
déclarée provisoire ou définitive.

Une étiquette est déclarée provisoire si elle peut encore être

amélioré c'est-à-dire augmenter ou diminuer mais elle est déclarée définitive si
elle ne peut plus être amélioré.
Autrement dit:

o Pour le PCC: ℓ j est déclarée provisoire si elle représente un majorant

du PCC;
o Pour PLC: ℓ j est déclarée provisoire si elle représente un minorant du
PLC;

Considérons ℜ =(x,u, C ) : un graphe pondéré quasi-fortement connexe et

sans circuit.

11 Numéroter arbitrairement les sommets de ℜ mais le sommet considéré

comme origine (entrée, source ou racine) sera numéroté 0 ou 1 ou encore s.
22
Initialisation de chaque procédure:

Au début on pose:
 PCC PLC

ℓj=¿{0,si j=1¿ {C1j,si (1, j )∈u¿ ¿¿¿ ℓj=¿{0, si j=1¿ {C1j,si (1, j)∈u¿ ¿ ¿
Où M>>0
I.7.2.2. Principe d'optimalité de Richards BELLMAN

Tout chemin optimal (minimal ou maximale) dans un graphe

pondéré ne peut être constituer que des chemins partiels optimaux. En
général ce principe s'énonce comme suit: "Toute politique optimale ne peut
être constituer que des sous-politiques optimales".

NOTA:
 La démonstration de ce principe se fait trivialement par l'absurde.
 Ce principe comprend l'énoncé direct et sa réciproque.

Ce principe donne lieu à 2 types d'analyses:

Analyse prospective : c'est cet analyse qui donne la valeur du

chemin optimal.
Analyse rétrospective : c'est cet analyse qui permet de construire
le chemin optimal c'est-à-dire elle permet
de trouver de manière rétrospective tous
les arcs de l'arborescence faisant partis du
chemin optimal.
Ce principe se formalise par l'équation de Richards BELLMAN.
- considérons ℜ =(x,u, C ) connexe et sans circuit (quasi-fortement
connexe).
- Supposons que le sommet considéré comme entré (racine) soit numéro
1 et que les autres sommets soient arbitrairement numérotés 2,3,…,
n=|X| . ∀ j∈ X
j≠1, ∃ un certain arc final (k , j) dans le
avec
chemin optimal de 1 à j ⇒ ∀ k ≠ j :ℓ j =ℓ k +C kj .

On a alors les équations suivantes :

PCC PLC

Nota {:ℓ =0 ¿ ¿¿
(1)¿ (1b) ¿ { ℓ1=0 ¿ ¿¿
1
avec j=2,3,…,n j=2,3,…,n
 - A chaque itération on ne considère que les sommets qui peuvent être
amélioré à cette itération c'est-à-dire on ne considère que le sommet
dont les étiquettes sont déclarées provisoire.
- Le système (1) pour le PCC ou le système (1b) pour le PLC constitue les
équations de Richards BELLMAN. Tous les algorithmes Tree builder se
base sur ses équations pour trouver les étiquettes déclarer définitives.
¿
Une fois les étiquettes définitives trouvées on le note ℓ j ou ℓ j .
Après l’analyse prospective on ordonne les étiquettes comme suit :
ℓ ¿j < .. .<ℓ ¿i ¿ ℓ¿i1 ¿ ℓ¿j
2 .

I.7.2.3. Algorithme de FORD

a) Principe

Soit ℜ =(x,u, C ) un réseau d’ordre n vérifiant les hypothèses

classiques. L’algorithme se présente comme suit :

1 Numéroter les sommets dans un ordre quelconque ; mais l’entrée (origine

ou source) étant numéroté 1 (ou s ou encore 0).

2 Poser (étape d’initialisation) :

PCC PLC

ℓ(0)i =¿ {0, si i=1¿¿¿¿ ℓ(0)i =¿ {0, si i=1¿¿¿¿

3 A chaque étape (itération) k+1, (k=0,1,2,…,m) avec m fini.
Pour (i, j )∈ u .
PCC PLC
−si ℓ(kj )−ℓ(i k )>C ij , −si ℓ(kj )−ℓ(i k )<C ij , alors
alors remplacer remplacer
ℓ(jk +1) par ℓ(jk +1)=ℓ(i k )+C ij ℓ(jk ) par ℓ (kj +1)=ℓ(i k )+C ij
−sin on ℓ(jk +1)=ℓ(jk ) −sin on ℓ(jk+1)=ℓ(jk )

On arrête les itérations (procédures) lorsque aucune ℓ j ne peut plus être

4
améliorées, c'est-à-dire lorsque toutes les étiquettes sont déclarées
définitives.
5 Vérification : S’il existe des arcs (i, j ) avec i> j et i≠1 , il faut recommencer
toutes les opérations à partir de j. ce retour permet de ne rien oublier et de
rendre tous les ℓ j définitives (optimaux).

Nota :

- L’algorithme de FORD procède par l’analyse prospective pour trouver

toutes les étiquettes définitives (optimales) c'est-à-dire trouver les
valeurs de chemins partiels optimaux.
- Une fois toutes les étiquettes sont déclarées définitives, on exploite
l’analyse rétrospective pour construire les branche de l’arborescence
optimal c'est-à-dire construire les chemins partiels optimaux en partant
chaque fois du sommet ik (PCC ou PLC) ayant la plus grande étiquette.

Remarque :
A chaque itération, l’algorithme de FORD et ses variantes entre- autres :
BELLMAN KALABA, DIJKSTRA, BELLMAN-FORD, … ne considèrent que les
sommets dont les étiquettes peut être améliorer à cette étape c'est-à-dire
ne considèrent que les successeurs de sommet dont les étiquettes ont été
déclarées définitive à l’itération précédente.

b) Algorithme de FORD pour le PCC

∏(io)← 0, ∏(i)←M ∀ i ∈ X, i≠io

∀ i ∈ X, P(i)←i, le prédécesseur de i est i
K←0, compteur d’itération.
2. Itération courante

Modif ← faux ‘aucune modification de ∏(i) n’est possible’

+
∀ i ∈ X, ∀ j ∈
Γi
si ∏(j) - ∏(i) > Cij
alors ∏(j)←∏(i) + Cij
P(j)←i
Modif← Vraie
fin si
TEST FIN
Si Modif = Faux ‘ aucune amélioration des marques lors de l’étape K’
fin
sinon
K←K+1
 si K=N
fin car circuit de longueur négative
Sinon aller en 2.
.

L’algorithme de DIJKSTRA
- Un graphe G =(x,u) ;
- Un sommet de départ s. on associe à chaque sommet x le coût du
meilleur chemin connu appelé poids(x). on mémorise également pour
chaque sommet le voisin par lequel on « arrive » pour réaliser le
meilleur chemin connu ;
- Soit s l’ensemble de tous les sommets ;
- Π l’ensemble des sommets optimaux.

Initialisation
poids (s )←0
poids (x )←+∞ pour x≠s
Π ←φ
Début
tant que Π≠s
Choisir un sommet x ∉ Π de poids minimum
Π ← Π∪ { x }
pour tout voisin y de x ∉ Π
Si poids(x)+valeur (x,y)<poids(y)
Alors poids(y) ← poids(x)+valeur(x,y)
Mémoriser en y que l’on vient de x
finsi
fin pour tout
fin tant que
Fin

Cet algorithme donne tous les plus courts chemins de s vers tous les autres
sommets.
I.8. PROBLEME D’ORDONNANCEMENT : METHODE
MPM ET METHODE PERT

I.8.1. GÉNÉRALITÉS SUR L’ORDONNANCEMENT

A. Objectif de l’ordonnancement

Les problèmes d’ordonnancement sont apparus au départ dans la

planification de grands projets. Le but était de gagner du temps sur leur
réalisation. De tels projets sont constitués de nombreuses étapes, également
appelées tâches. Des relations temporelles existent entre ces dernières. Par
exemple :

 Une étape doit commencer à une date précise ;

 Un certain nombre des tâches doivent être terminées pour pouvoir
démarrer une autre ;
 Deux tâches ne peuvent être réalisées en même temps (elles utilisent
une même machine par exemple) ;
 Chaque tâche nécessite une certaine quantité de main d’œuvre. Il faut
donc éviter, à chaque instant, de dépasser la capacité totale de main
d’œuvre disponible.

Toutes ces contraintes ne sont pas à prendre en compte dans la

résolution du problème. Ici, nous allons nous intéresser uniquement aux types
de contraintes.
On cherchera à déterminer une planification, ordonnancement des
étapes qui minimise le temps total de réalisation du projet. A partir de cette
planification, nous verrons que le temps de certains étapes peut
éventuellement être modifié sans entraîner un retard du projet, alors que
d’autres, les étapes dites « critiques », retardent entièrement le projet au
moindre retard local.
 En toutes généralité, le problème d’ordonnancement se pose
comme suit : Etant donné un objectif à atteindre et dont la réalisation suppose
l’exécution d’un multiple tâche, lesquelles tâches sont soumises à des
nombreuses contraintes déterminer l’ordre et le calendrier d’exécution de ses
multiples tâches.

B. Contraintes

Parmi les nombreuses contraintes qui peuvent s’opposer à des

nombreuses opérations (tâches) dans un ordre donné et à des dates
souhaitées, on peut citer les suivantes :
i. Les contraintes potentielles :
Elles sont divisées en deux :

- Contraintes de succession ou d’antériorité :

Une tâche j ne peut commencer que lorsque une tâche i est

achevée ou terminée.

i j

Ou en générale, une tâche j ne peut commencer qu’un certain laps de temps

après que la tâche i est commencée.

- Contraintes de date ou de localisation temporaire :

Une tâche ne peut commencer avant une certaine date

indépendamment du fait qu’elle doit succéder à d’autres tâches.

ii. Contraintes cumulatives et contraintes disjonctives  :

On ne tiendra pas compte de ces 2 contraintes dans le cadre de
ce travail.

C. Le P.C.O

Dans notre cas nous proposons d’étudier un cas particulier de

problème d’ordonnancement c’est celui appelé « Problème central
d’ordonnancement » (P.C.O).

Dans le P.C.O seul les contraintes potentielles sont prises en

compte particulièrement les contraintes de successions : l’exécution de la
tâche j ne peut être commencer que lorsque la tâche i qui lui est antérieur est
achevé.
 D. Les méthodes de résolution du P.C.O

Jusqu’aux années 1950 avant le développement de la théorie de

graphe le P.C.O était résolu empiriquement par le diagramme de GANTT de
1918-1957.
Actuellement, il existe deux méthodes scientifiques et techniques basées sur la
théorie de graphe pour résoudre le P.C.O :
- La méthodes Française : Méthode de Potentiel Métra (MPM) en 1958.
- La méthode Américaines : PERT : « Programm Evaluation and Research
Task » en 1958.

I.8.2. LA MÉTHODE DES POTENTIELS MÉTRA : MPM

La solution aux P.C.O est donnée par le graphe potentiel (MPM) pondéré et
aussi un réseau de transport quasi-fortement connexe, un cas particulier du
réseau de transport.

a. Eléments du graphe MPM

Le graphe MPM est constitué des éléments suivants :

 Chaque tâche représente un sommet (ou nœud) ;

 Chaque arc représente une contrainte de succession (o
d’antériorité).
 La pondération (ou potentiel) d’un arc donne le temps qui doit
s’écouler au minimum entre le début de la tâche origine de l’arc et
le début de la tâche extrémité de l’arc.

Exemple  :
3
a b

Ce schéma signifie que la tâche a doit précéder la tâche b et il

doit s’écouler au minimum 3 unités de temps entre le début de la tâche a et le
début de la tâche b.

NOTA : Ici, nous ne considérons que les contraintes potentielles de

successions dans le temps.

Conséquences : La pondération de chaque arc sera donc égale à la durée de

la durée de la tâche origine de l’arc c'est-à-dire que la valeur numérique (ou
potentiel) associé à un arc (i,j) est égal à la durée de la tâche i au bout duquel
peut commencer la tâche j.

b. Construction du graphe MPM

Après une analyse approfondie du projet par le bureau d’étude,

on dresse le dictionnaire des précédents c'est-à-dire un tableau de la forme
que voici :

- Dans la première colonne du tableau, la liste de toutes les tâches à

réaliser ;
- Dans la deuxième colonne, on donne la liste pré-requise pour que les
tâches de la première colonne soient débutées ;
- La troisième colonne donne la durée de la tâche.

Exemple :

Soit le tableau suivant :

X P(x) Durée de x
a - 4
b a 6
c - 4
d - 12
e b,c,d 10
f b,c 26
g a 7
h e,g 10
i f,h 3

 Notation:

 P(x) est l’ensemble des tâches qui précède immédiatement les tâches
qui sont dans x.
+
 Γ G ( x) est l’ensemble des successeurs de x.
−
 Γ G ( x) est l’ensemble de prédécesseurs de x.
− −
Dans l’exemple précédent, Γ G (b) =a ; Γ G (e) =b,c,d.
Nota : Dans la construction du graphe potentiel il est nécessaire pour des
raisons de clarté d’ordonner les différentes tâches par niveau.

 Niveau
Niveau 0 : C0 : C’est l’ensemble des tâches de niveau zéro (0). Ce sont les
tâches n’ayant pas de prédécesseurs, tâches non soumises à des contraintes
d’antériorités.
Dans l’exemple précédent, C0= {a,c,d}.

Niveau 1 : C1 : Pour obtenir les tâches de niveau 1 on doit rayer dans le
tableau de précédent toutes les tâches de niveau 0 de la colonne P(x). Les
tâches x correspondant aux lignes P(x) entièrement rayées sont de niveau 1.
Dans l’exemple précédent, C1= {b,g}.

En général, pour obtenir les tâches de niveau k, on raye dans

P(x) toutes les tâches appartenant à Ck-1 (de niveau k-1), où k=1,2,3,…, les
tâches x correspondant aux lignes P(x) entièrement rayées sont de niveau k.

L’algorithme suivant permet de déterminer le niveau de chaque

tâche :
(a ) poser d i =|Γ −i | ∀ i∈ X
k=0 , s=x
(b ) Soit S k ={i∈ s/d i =0 }
∀ i ∈ Sk faire
r (i )=k
∀ j ∈ Γ +i , d j ←d j −1
(c ) S ←S−S k et k ←k+1
si |S|=0 , fin , sin on aller en (b ).

Dans l’exemple précédent :

Niveau 2 : C2={e,f} ;

Niveau 3 : C3={h} ;
Niveau 4 : C4={i}

NOTA :
- Les ensembles Ck, (k=0,1,2,…)sont 2 à 2 disjoints.
- Les sommets du graphe potentiels seront placés de gauche à droite en
fonction de leur niveau. Les sommets de même niveau seront placés de
gauche à droite à un même niveau sur un vertical de manière aussi à
limiter les nombres d’intersection entre arcs.

Chaque sommet sera représenté par un rectangle :

Tx Tx*
X
Où :
- X  : est le sommet qui désigne le nom de la tâcvhe ;
- Tx  : désigne la date de début de la tâche x ;
- Tx* : désigne la date au début au plus tard de la tâche x.
NOTA :
o L’intervalle [Tx,Tx*] se nomme intervalle de flottement pour la
tâche x.
o Pour tracer le graphe potentiel, autres les éléments cités, on doit
introduire une tâche supplémentaire qui n’est pas dans le
dictionnaire de précédent z. c’est une tâche relié à toutes les
sommets quoi n’ont pas de successeurs c'est-à-dire sommet
suivant cette tâche permettra de dater la fin de travaux.

c. Détermination du calendrier au plus tôt

On affecte comme pondération, la durée de la tâche origine de

l’arc, car les contraintes sont seulement celle de succession.
Soit dx le potentiel (ou pondération) de tous les arcs ayant comme extrémité
initiale la tâche x c'est-à-dire si (x,y) est un arc ; alors : dx=Cxj.

Etape 0 : On pose Tx=0, ∀ x ∈C 0 .

Etape 1 : ∀ x ∈C k (k=1,2,…) Tx=la valeur (longueur) du PLC d’un sommet de
niveau 0 à ce sommet x.

En effet, le fait de choisir pour Tx la longueur (valeur) du PLC garantit que

toutes les contraintes d’antériorités ont été respectées. Il va de soit que T x est
déterminé par l’algorithme de FORD ou ces variantes relatives au PLC.
Pour l’exemple précédent, le calendrier au plus tôt se présente comme suit :

Niveau 0  : T a=T c =T d =0
Niveau 1  : T g =T a +4=4 ; T b =T a +4=4

T f =max ¿ {T c +4=4 ¿ ¿ ¿
Niveau 2  :

T h=¿ {T e +10=22 ¿ ¿¿¿

Niveau 3  :

T i =¿ {T f +24=34 ¿ ¿¿¿
Niveau 4  :
Niveau final : (C5 =C f ) : T z =T +3=37i
 NOTA : z désignant la tâche finale d’où Tz est la date à laquelle l’ensemble
des travaux peut s’achever au plus tôt.

d. Détermination du calendrier au plus tard et chemin critique

Il s’agit de déterminer pour chaque tâche x une date de début au

plus tard Tx tel que Tz (date de fin de travaux au plus tôt) ne soit pas retardé,
on procède à cet effet par analyse rétrospective.
¿
Etape 1 : on pose T z =T z
¿ ¿ ¿
∀ x≠z : T x = min ( T y −( x , y ))= min (T y −d x ) (1)
Etape 2 : ( x , y )∈ U +x y ∈Γ +G ( x)

Où : ux+ : est l’ensemble d’arcs incidents extérieurement à x.

Soit x un sommet dont tous les sommets successeurs ont déjà

leur date de début au plus tard fixée, alors Tx*= (1).
¿
La tâche x sera une tâche critique ssi T x =T x c'est-à-dire qu’une
tâche critique est une tâche dont la date de début au plus tôt correspond à la
date de début au plus tard. On appelle chemin critique, un chemin passant par
les tâches critiques.

NOTA :
- L’ensemble des arcs ayant contribués à la détermination de T z constitue
le chemin critique.
- Les tâches situées sur le chemin critique sont appelées les tâches
critiques.

En effet, tous retard pris dans l’exécution de l’une de tâches

critiques c'est-à-dire de l’un de tâche située sur le chemin critique retardera la
fin des travaux. Dès lors les tâches critiques nécessitent une attention
particulière.
Exemple :
Construction du graphe potentiel correspondant à l’exemple précédent :

Niveau 0 : C0= {a,c,d} ; niveau 1 : C1= {b,g} ; niveau 2 : C2={e,f} ; niveau 3 :
C3={h} ; niveau 4 : C4={i} ; niveau final : Cf={z}.

0 0
4
a 6
4
4 1
24
4 0
4 b 3
1
0 6 6 7 0 2 10 3 3
6 2 4 7
c f
4 10
17

4g 3
7
 2 2 4
d
4
i
1 h
4

Le chemin critique est celui en rouge et les tâches critiques sont : a,b,f,i.

e. Détermination des marges

Il y a deux types des marges : une marge totale et une marge

libre pour chaque tâche x.

1°) Marge totale relativement à la tâche x  :

MT x = T ¿x −T x
C'est-à-dire MTx est le retard maximum que l’on peut prendre
dans la mise en exécution de la tâche x sans remettre en cause les dates au
plus tard de succession ou suivante (fin des travaux).

2°) Marge libre de la tâche x  :

¿ ¿
ML x min( T y −T x −d x )= min ( T y −T x −C xy )
(x , y ) ∈ U +x
+
y ∈ Γ G (x )

MLx est le retard maximum que l’on peut se permettre dans la

mise en route de la tâche x sans remettre en cause la date au plus tôt
d’aucune autre tâche.

I.8.3. LA MÉTHODE PERT

a. Historique

A la fin des années cinquante, la marine Américaines conçoit une

nouvelle technique d’ordonnancement qui devait conduire à des gains de
temps importants dans la réalisation de ses missiles ogive nucléaire POLARIS :
C’est la technique PERT (Programm Evaluation and Review Technique). Cette
technique a permis de coordonner les travaux de près de 6 000 constructeurs
dans le délai imposé par le gouvernement Américain.

Le projet POLARIS représentait entre autre :

- 250 fournisseurs
- 9 000 sous-traitants
- 7 ans de réalisation

L’utilisation de la méthode PERT a permis de ramener la durée

globale de réalisation du projet de 7 à 4 ans. Cette méthode s’est ensuite
étendue à l’industrie Américaine puis à l’industrie occidentale.
La méthode PERT est « une méthode consistant à mettre en ordre sous forme
de réseau plusieurs tâches qui grâce à leur dépendance et à leur chronologie
concourent toutes à l’obtention d’un produit finit ».

Nota : La méthode PERT permet de résoudre le problème central

d’ordonnancement par le graphe PERT. Dans ce travail, nous ne considérons
que les graphes PERT temps c'est-à-dire graphe PERT temps déterministe.

b. Elément du graphe PERT

- Chaque opération (tâche) est représentée par un arc. A cet arc on

associe une pondération, une valeur numérique qu est la durée de cette
opération.
- Les sommets du graphe PERT représentent des pondérations ou le
début de certaines autres opérations.

Bref, les sommets du graphe PERT représentent les éléments déterministes.

Chaque opération représente la fin des opérations.
La disposition des arcs doit traduire la succession ou au contraire
la simultanéité des opération. Si l’extrémité finale d’un arc coïncide avec
l’extrémité initiale d’un autre, cela signifie que l’opération associée au premier
arc doit être achevée pour que celle associer au 2ème arc puisse débuter.

Exemples :
1. Succession des opérations
x y
2 3
1 2 3
 L’opération y de durée 3 unités de temps ne peut débuter
qu’avant que l’opération x de durée 2 unités de temps puisse être achevée.
Cela veut dire que y débute nécessairement à la fin de x sinon il n’y aura pas
de souplesse.
2. simultanéité des opérations
2
x
2 y
1 3
6
z 3

Ceci signifie que y doit attendre que x puisse s’achever.

L’opération z peut être exécuter en même temps que les opérations x et y.

c. Construction du graphe PERT

Chaque sommet se présente comme suit :

t
x
X

Où : X  : désigne le numéro de l’étapet (événement) ;

tx  : désigne la date attendue *de l’événement x ou la date au plus tôt de
x

l’événement x.
tx*  : désigne la date limite ou la date au plus tard de l’événement x.

NOTA :
- La notion de niveau (voir la méthode MPM) n’a pas de sens pour la
méthode PERT car les tâches sont représentées par les arcs dans la
méthode PERT alors que les niveaux correspondaient à des sommets
dans la méthodes MPM.
- Dans la méthode PERT ce qui est souhaitable c’est l’ordonnancement
des arcs.
- Dans la méthode PERT on ajoute toujours un sommet initial d’où partent
les tâches (opérations) dont la mise en route n’est soumise en aucune
contrainte d’antériorité et on ajoute aussi un sommet final auquel
aboutissent toutes les tâches (opérations) n’ayant plus des successeurs.
Ce sommet est l’événement qui marque la liaison ou la fin de l’œuvre.
- Dans cette méthode on est souvent obligé d’ajouter une tâche virtuelle
de durée 0. cette tâche virtuelle n’a qu’un seul but celui de traduire la
relation d’antériorité. Cette opération se note par un arc en pointillé.
 - Bien que pour la méthode PERT la notion de niveau est sans objet, le
dictionnaire de précédent est quand même nécessaire ; c’est pour
traduire la contrainte d’antériorité et les durées de chaque tâche
(opérations).
- L’objet de la méthode PERT est la construction du graphe PERT dans le
but de trouver les tâches critiques, le chemin critique, les dates
optimales, le début au plus tôt et le début au plus tard de chaque
opération.

d. Détermination du calendrier au plus tôt (ou les dates attendues) : tx

A chaque sommet x on affecte une date t x, la date au plus tôt ou

la date attendue de x et c’est égale à la valeur du plus long chemin (PLC)
allant du sommet initial à ce sommet x. On peut à cet effet utiliser l’algorithme
de FORD du PLC.

e. Détermination du calendrier au plus tard (ou des dates limites) : tx*

tx* est la date limite de réalisation de l’événement x, elle doit être

déterminer de manière à ne pas retarder la date au plus tôt de la fin de tous
les travaux.
A cet effet, soit z l’événement final et soit t z* la tâche (ou
opération) joignant les événements x et y, alors :

11 ¿
On pose t z =t z

22 ¿
∀ sommet x dont les successeurs ont leurs t x calculées par :
t ¿x = min ( t ¿y −d k ) ; où d k ¿ C xy
y ∈ Γ +G ( x ) (cfr analyse rétrospective de
BELLMEN).
f. Détermination des marges

- Marge totale (Mt)

Idem que pour la méthode MPM : ∀ sommet x.

Mt ( x )=tx*-tx

- Marge libre (Ml)

Cette marge est obtenue par analyse rétrospective, par :

 ¿ ¿
Ml ( x )= min ( t y −t x −d k )= min ( t y −t x −C xy )
y ∈ Γ +G( x ) y ∈Γ +
G
(x)

g. Les tâches (opérations) critiques et chemin critique

Dans la méthode PERT, les tâches critiques sont celles qui sont
comprises entre les sommets dont tx*=tx et le chemin critique est le chemin qui
passe par ces tâches critiques.

Exemple :
X P(x) Durée de x
a - 4
b a 6
c - 4
d - 12
e b,c,d 10
f b,c 26
g a 7
h e,g 10
i f,h 3

Le graphe PERT de ce dictionnaire des précédents est le suivant :

d 12
0 14
0 4
12
1 e
a 10
22
4 0 24
7 5
X
4 4
4 g
h 10
2

c 37
i 37
b 7
34
6 34 3
f 6

24
10
10
3
Les tâches critiques sont : a,b,f,i et le chemin critique est le chemin en rouge.

Remarques :

- Comme pour la méthode MPM, les tâches critiques dans la méthode

PERT ne doivent d’aucun retard dans leur réalisation sinon tout le projet
subirait une prolongation de la fin des travaux.
De manière tout à fait générale, dans la méthode MPM comme dans la
méthode PERT on peut agir sur les tâches hors du chemin critique mais en
respectant les marges fixées et cela en vue d’optimiser le rendement.