École National des Sciences Appliquées - Fès

Département Génie Électrique et Informatique

M09 : Cours de Théorie de graphe

Auteur
Prof. Safae El Haj Benali
safae.elhajbenali@usmba.ac.ma

N.B. : Version provisoire. Merci de me signaler les erreurs !

 1

• Théorie de graphe
 12h de cours.
 8h de TD.
 2h d'evaluation.
 Table des matières

Table des matières 2

1 Eléments de théorie des graphes 4
1 Dénition et concepts de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1 Dénition "intuitive" d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Dénition mathématique d'un graphe . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Ordre d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Orientation d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Multiplicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Degrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.7 Relations entre sommets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.8 Quelques types de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Représentations d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1 Matrice d'incidence sommets-arcs . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Matrice d'adjacence ou d'incidence sommets-sommets . . . . . . . . . . . . . 12
3 Connexité dans les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1 Chaînes et cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Chemins et circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 Fermeture transitive d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.5 Composante connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.6 Forte connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 Le problème du plus court chemin 20
1 Les plus courts chemins d'un sommet à tous les autres . . . . . . . . . . . . . . . . . 21
1.1 Algorithme de Dijkstra-Moore . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 Plus courts chemin entre tous les sommets . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1 Algorithme de Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Ordonnancement, recherche du plus long chemin 27
1 Contexte général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2 Dénitions et propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1 Date de début au plus tôt d'une tâche j . . . . . . . . . . . . . . . . . . . . . 29
2.2 Date de début au plus tard d'une tâche i . . . . . . . . . . . . . . . . . . . . 29
2.3 Les diérentes Marges d'une tâche . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Méthodes d'ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 La méthode M.P.M. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.1 Representation M.P.M. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Calcul de l'ordonnancement par la méthode M.P.M. . . . . . . . . . . . . . . 34
2
TABLE DES MATIÈRES 3

5 La méthode P.E.R.T. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.1 Représentation de P.E.R.T. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2 Dicultés de construction du graphe P.E.R.T. . . . . . . . . . . . . . . . . . 38
5.3 Calcul de l'ordonnancement par la méthode P.E.R.T. . . . . . . . . . . . . . . 38
 [ Premier Chapitre \
Eléments de théorie des graphes

Le problème des ponts de Königsberg :

La ville de Königsberg comprenait 4 quartiers, séparés par des ponts. Les habitants de Königsberg
se demandaient s'il était possible, en partant d'un quartier quelconque de la ville, de traverser tous
les ponts sans passer deux fois par le même et de revenir à leur point de départ.

Fig. 1.1  Problème des ponts de Königsberg (Euler problem 1736)

"Euler" démontra en 1736 qu'il était impossible de traverser chacun des sept ponts de la ville
de Königsberg une fois exactement et de revenir au point de départ.
Euler représenta cette situation à l'aide d'un "dessin" où les sommets représentent les terres et
les arêtes, les ponts comme le montre la gure 1.2.

Fig. 1.2  Graphe associé au problème des ponts de Königsberg

Euler démontra que ce problème n'a pas de solution. Le problème des ponts de Königsberg est
identique à celui consistant à tracer une gure géométrique sans lever le crayon et sans repasser
plusieurs fois sur un même trait.
4
1. DÉFINITION ET CONCEPTS DE BASE 5

La théorie des graphes constitue un domaine des mathématiques qui, historiquement, s'est aussi
développé au sein de disciplines diverses telles que la chimie (modélisation de structures), la biologie
(génome), les sciences sociales (modélisation des relations) ou en vue d'applications industrielles
(problème du voyageur de commerce). Elle constitue l'un des instruments les plus courants et les
plus ecaces pour résoudre des problèmes discrets posés en Recherche Opérationnelle (RO).
Un graphe permet de représenter simplement la structure, les connexions, les cheminements
possibles d'un ensemble complexe comprenant un grand nombre de situations, en exprimant les
relations, les dépendances entre ses éléments (eg, réseau de communication, réseaux ferroviaire ou
routier, arbre généalogique, diagramme de succession de tâches en gestion de projet, etc). En plus
de son existence purement mathématique, le graphe est aussi une structure de données puissante
pour l'informatique.

1 Dénition et concepts de base

1.1 Dénition "intuitive" d'un graphe

Dénition 1.1 Un est un schéma constitué par un ensemble (ici supposé ni) de points
graphe

et par un ensemble de èches reliant chacune deux. Les points sont appelés les du
sommets

graphe, et les èches les du graphe."

arcs

Exemple 1.1 Dans le graphe ci-après, on a :

 un ensemble de sommets : {a, b, c, d, e, f , g, h},
 un ensemble d'arcs : {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Remarque 1.1 "La position des sommets et la forme des arcs sur une gure n'importe pas; seul
importe de savoir comment les sommets sont reliés". Les graphes 1.3 et 1.4 sont dits isomorphes.

Notation 1.1 L'arc 3 va du sommet e au sommet f . On dit qu'il est de la forme (e, f ) et on
écrit par convention que 3 = (e, f ). On remarque que si la forme ( g, c) sut pour désigner l'arc 6
6 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES

Fig. 1.3  Un exemple de graphe

Fig. 1.4  Un Graphe isomorphe au graphe de la gure précédente

de manière univoque, la forme ( f , e) ne sut pas pour désigner l'arc 1 uniquement car 4 = ( f , e)
également.
1.2 Dénition mathématique d'un graphe

Dénition 1.2 Un graphe G = ( X ,U ) est le couple constitué :

1. par un ensemble X = {x , x , ..., x }.
1 2 n

2. par une famille d'éléments U = {u , u , ..., u } du produit cartésien X × X = {(x, y)/ x ∈

X et y ∈ X }.
1 2 m

1.3 Ordre d'un graphe

Selon les dénitions précédentes, l'ensemble de sommets est supposé ni.
1. DÉFINITION ET CONCEPTS DE BASE 7

Dénition 1.3 On appelle ordre du graphe G = ( X ,U ) le nombre de sommets du graphe.

Notation 1.2L'ordre de G est donc le cardinal de X et noté | X |.
Exemple 1.2 Le graphe de la gure 1.3 est d'ordre 8.

1.4 Orientation d'un graphe

Dénition 1.4 (Arête) Une est un ensemble de sommets (ensemble de cardinalité 1 ou

arête

2). Une arête est donc un élément de P ( X ) (l'ensemble des parties à deux éléments de l'ensemble
X ).
2

Notation 1.3 La notation {x, y} pourrait être employée mais il faudrait écrire {x} (pour x = y).
Soit un graphe G = ( X ,U ), on notera donc les arêtes sous la forme [x, y] (avec x ∈ X et y ∈ X ).
Dénition 1.5 (Graphe non orienté) Un " graphe non orienté " sera appelé un multi-

graphe et noté G = ( X , E) avec E ⊂ P ( X ).

2

Exemple 1.3 Réseau de piéton.

Remarque 1.2 Dans un multigraphe, il peut y avoir plusieurs arêtes entre deux sommets.

Dénition 1.6 (Arc) Une arc est une paire ordonnée de sommets (x, y).

Dénition 1.7 (Graphe orienté) Un digraphe ou un " graphe orienté " est un graphe dont
toutes les arêtes sont orientées.
Exemple 1.4 Réseau de vol.
1.5 Multiplicité

Dénition 1.8 (Boucle et extrémités)

Un arc de la forme (x, x) est une .
boucle

Soit un arc de la forme (x, y), x et y sont appelés les extrémités de l'arc :
8 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES
 x est l'extrémité initiale de l'arc;
 y est l'extrémité nale de l'arc.

Fig. 1.5  Uu exemple de boucle et d'extrémités

Dénition 1.9 (Multiplicité d'une paire ( x , y)) La multiplicité d'une paire (x , y) est le
nombre d'arcs (du graphe G) ayant comme extrémité initiale x et comme extrémité nale y.
Notation 1.4 La multiplicité d'une paire (x , y) est notée : m (x, y). On pose m (x, y) = m
+ − +
( y, x)
et m (x, y) = m (x, y) + m (x, y).
− +
G G G

 si x 6= y alors m (x, y) est le nombre d'arcs ayant une extrémité en x et une en y.

G G G

 si x = y alors m (x, y) vaut deux fois le nombre de boucles en x.

G
G

1.6 Degrés
a) Degré d'un sommet

Dénition 1.10 Pour un graphe ou un multigraphe, on appelle du sommet x, et on note

degré

d(x), c'est le nombre d'arcs ayant une extrémité en x. Attention! une boucle sur un sommet est
comptée deux fois.

Exemple 1.5 Dans le graphe de la gure 1.3 :

dG ( e) = 5 ,
dG ( c) =? .
Lemme 1.1 (Lemme des poignées de mains) La somme des degrés des sommets d'un mul-
tigraphe est égale à deux fois le nombre d'arêtes.
Exemple 1.6 Dans le graphe 1.6, on a les degrés :
d ( x1 ) = 2
d ( x2 ) = 1
d ( x3 ) = 3
d ( x4 ) = 2
d ( x5 ) = 1
d ( x6 ) = 1
1. DÉFINITION ET CONCEPTS DE BASE 9

Fig. 1.6 

et le nombre d'arete est égale à 5.

b) Degré d'un graphe

Dénition 1.11 Le est le degré maximum de tous ses sommets.

degré d'un graphe

Un graphe dont tous les sommets ont le même degré est dit . Si le degré commun est k,
régulier

alors on dit que le graphe est k-régulier.

Exemple 1.7 Dans l'exemple 1.6, le degré du graphe est 3.

Exercice 1.1 Est-il possible de relier 15 ordinateurs de sorte que chaque appareil soit relié avec
exactement trois autres?

1.7 Relations entre sommets

Dénition 1.12 (Sommets voisins)

 Le sommet y est un du sommet x s'il existe un arc de la forme : (x, y).

successeur

 Le sommet y est un du sommet x s'il existe un arc de la forme : ( y, x).

prédécesseur

 Le sommet y est un ouvoisin du sommet x s'il existe un arc de la forme (x, y)

adjacent

ou de la forme ( y, x) (autrement dit si y est un successeur ou un prédécesseur de x ).

 Un sommet est un sommet qui n'a qu'un seul voisin.
pendant

Notation 1.5 L'ensemble des successeurs du sommet x est noté : Γ (x). +

L'ensemble des prédécesseurs du sommet x est noté : Γ (x). −

L'ensemble des voisins ou des sommets adjacents du sommet x est noté :Γ(x) = Γ (x) + Γ (x).
+ −

Exemple 1.8 Dans le graphe de la gure 1.3 :

Γ( e) = Γ+ ( e) + Γ− ( e) = { f , h} ∪ { f , d } = { f , d, h}.
10 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES
1.8 Quelques types de graphes
a) p-graphe

Dénition 1.13 Soit un graphe G = ( X ,U ), si le nombre d'arcs qui va d'un sommet x à un

sommet y de X est inférieur ou égal à p (pour tous les sommets x et y de U ) alors on dit que G
est un p-graphe.

Notation 1.6 est un p-graphe ⇐⇒ ∀(x, y) ∈ X / |{u ∈ U, u = (x, y)}| ≤ p.

G = ( X ,U ) 2

Exemple 1.9 Le graphe de la gure 1.3 est un 2-graphe (m ( f , e) = 2).

+
G

b) Graphe simple

Dénition 1.14 Un graphe simple est un multigraphe :

 sans boucles;
 tel qu'il n'y ait jamais plus d'une arête entre deux sommets quelconques

Fig. 1.7  Uu exemple de graphe simple

c) Graphe complet

Dénition 1.15 Un graphe est complet si chaque sommet du graphe est relié directement à
tous les autres sommets.

d) Graphe biparti
2. REPRÉSENTATIONS D'UN GRAPHE 11

Fig. 1.8  Uu exemple de graphe complet

Dénition 1.16 Un graphe est biparti si ses sommets peuvent être divisés en deux ensembles
X et Y , de sorte que toutes les arêtes du graphe relient un sommet dans X à un sommet dans Y
(dans la gure 1.9, on a X = {1, 3, 5} et Y = {2, 4, 6}, ou vice versa).

Fig. 1.9  Uu exemple de graphe biparti

Exercice 1.2 Un tournoi oppose 6 équipes. Chaque équipe doit aronter toutes les autres.
1. Construisez un graphe représentant toutes les parties possibles.
2. Quel type de graphe obtenez-vous?
3. Si chaque équipe ne joue qu'un match par jour, combien de jours faudra-t-il pour terminer
le tournoi?

2 Représentations d'un graphe

Nous aimons bien communiquer par des dessins, mais les machines n'en sont pas encore là : il
faut donc trouver d'autres façons de représenter les graphes.
La solution consiste à utiliser des matrices, et il y a diérentes méthodes.

2.1 Matrice d'incidence sommets-arcs

Dénition 1.17 La matrice d'incidence ou d'incidence sommets-arcs d'un graphe G( X ,U )

sans boucle est une matrice telle que chaque colonne correspond à un arc de G et chaque ligne à
12 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES
un sommet de G ; si u = (i, j) ∈ U , la colonne u a tous ses termes nuls, sauf :
(
a iu = +1,
a ju = −1,

Exemple 1.10 On donne comme exemple la matrice d'incidence sommets-arcs du graphe partiel
sans boucle engendré par l'ensemble des arcs du graphe de la gure 1.3 privé de l'arc 5 (la boucle)
1 2 3 4 6 7 8 9
 
a 0 0 0 0 0 0 0 0
b  0 0 0 0 0 0 0 +1 
 
 
c  0
 0 0 0 −1 0 0 0 
d  0
 0 0 0 0 +1 +1 0 

e
 
 −1 +1 +1 −1 0 −1 0 0 
 
f  +1
 0 −1 +1 0 0 0 0 

g  0 0 0 0 +1 0 0 0 
 

h 0 −1 0 0 0 0 −1 −1

2.2 Matrice d'adjacence ou d'incidence sommets-sommets

Dénition 1.18 La matrice d'adjacenceou d'un graphe

d'incidence sommets-sommets

G ( X ,U ) est une matrice carrée où chaque ligne correspond à un sommet de G et chaque colonne
correspond également à un sommet de G. Le terme général de la matrice est : a tel que
 a = m (x , x ) signie que le sommet x est adjacent au sommet x .
ij
+

 a = 0 sinon.
ij G i j i j

En cas de boucle (pour le sommet i, par exemple), on place un 1 sur la diagonale (en position
ij

(i, i)).

Exemple 1.11 On donne comme exemple la matrice d'incidence sommets sommets associée au
3. CONNEXITÉ DANS LES GRAPHES 13

a b c d e f g h
 
a 0 0 0 0 0 0 0 0
b 0 0 0 0 0 0 0 1
 
 
c 0 0 1 0 0 0 0 0

graphe de la gure 1.
 
d 0
 0 0 0 1 0 0 1
e
 
0 0 0 0 0 1 0 1
 
f 0
 0 0 0 2 0 0 0
g 0 0 1 0 0 0 0 0
 

h 0 0 0 0 0 0 0 0

Remarque 1.3 La matrice d'adjacence d'un graphe non orienté est symétrique : a ij = a ji .

3 Connexité dans les graphes

3.1 Chaînes et cycles

Dénition 1.19 Une dans G, est une suite de la forme (x , u , x , u , ..., x , u , x )

chaîne

ayant pour éléments alternativement des sommets (x ) et des arêtes (u ), commençant et se

0 1 1 2 k−1 k k

terminant par un sommet, et telle que les extrémités de u soient x et x , i = 1, ..., k.

i i
i i −1 i

Six0 = a et xk = b, on dira que la chaîne relie a et b. En plus, on dira que la chaîne a une
longueur k (c'est le nombre d'arêtes de la chaîne). Une chaîne doit comporter au moins une arête.
Le graphe 1.10 contient les chaînes ( x1 , u3 , x3 , u4 , x4 ) et ( x4 , u4 , x3 , u2 , x2 , u1 , x1 ), entre autres.

On ne change pas une chaîne en inversant l'ordre des éléments dans la suite correspondante,
ainsi les chaînes ( x1 , u3 , x3 , u4 , x4 ) et ( x4 , u4 , x3 , u3 , x1 ) sont identiques.

 On appelle distance entre deux sommets la longueur de la plus petite chaîne les reliant.
 Le diamètre d'un graphe la plus longue des distances entre deux sommets.
 Une chaîne est élémentaire si chaque sommet y apparaît au plus une fois.
 Une chaîne est simple si chaque arête apparaît au plus une fois. Dans le graphe 1.10,
( x1 , u 1 , x2 , u 2 , x3 ) est une chaîne simple et élémentaire.
 Une chaîne telle que x0 = xk est appelée chaîne fermée. Dans le graphe 1.10,
( x2 , u 2 , x3 , u 4 , x4 , u 4 , x3 , u 2 , x2 ) est une chaîne fermée.
 Une chaîne fermée simple est appelée cycle si seul le sommet de départ apparaît deux fois
dans la chaîne. Dans le graphe 1.10, ( x2 , u2 , x3 , u4 , x4 , u5 , x2 ) est un cycle.

Théorème 1.1 Un graphe est biparti si et seulement s'il ne contient aucun cycle de longueur
impaire.
14 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES

Fig. 1.10 

3.2 Chemins et circuits

Ce sont les mêmes dénitions que les précédentes mais en considérant des concepts orientés.

 Un chemin conduisant du sommet a au sommet b est une suite de la forme

( x0 , u1 , x1 , u2 , ..., xk−1 , u k , xk ). Sur le digraphe 1.11, on peut voir par exemple le chemin
( x3 , u2 , x2 , u1 , x1 ). Par convention, tout chemin comporte au moins un arc.
 On appelle distance entre deux sommets d'un diraphe la longueur du plus petit chemin
les reliant. S'il n'existe pas de chemin entre les sommets x et y, on pose d ( x, y) = ∞. Par
exemple, sur le digraphe 1.11, d ( x1 , x2 ) = 2, d ( x4 , x3 ) = 1, d ( x3 , x4 ) = ∞.
 Un circuit est un chemin avec x0 = xk . Le digraphe 1.11 contient un circuit en partant de
x1 .
 Les notions de longueur, de chemins et de circuits sont analogues à celles des chaînes et des
cycles pour le cas non orienté.

Fig. 1.11 

Théorème 1.2 (Nombre de chemins de longueur k)

, élément à la position (i, j) de la puissance k
A k ( i, j ) ième
de A, est aussi le nombre de chemins
de longueur k qui mènent de x à x .i j
3. CONNEXITÉ DANS LES GRAPHES 15

Le terme de parcours regroupe les chemins, les chaînes, les circuits et les cycles. Un parcours
est :
 élémentaire : si tous les sommets qui le composent sont tous distincts ;
 simple : si tous les arcs qui le composent sont tous distincts ;
 hamiltonien : passe une fois et une seule par chaque sommet du graphe ;
 eulérien : passe une fois et une seule par chaque arc du graphe1 ;
 préhamiltonien : passe au moins une fois par chaque sommet du graphe ;
 préeulérien ou chinois : passe au moins une fois par chaque arc du graphe.

Remarque 1.4 Le problème du voyageur de commerce est voisin du problème hamiltonien. Il

consiste à trouver un circuit hamiltonien de coût minimal dans un graphe valué.

3.3 Fermeture transitive d'un graphe

Le calcul de la fermeture transitive permet de répondre aux questions concernant l'existence de
chemins entre x et y dans G et ceci pour tout couple de sommets ( x, y).

Dénition 1.20 On appelle fermeture transitive d'un graphe G = ( X ,U ), le graphe G = f

( X ,U ) tel que pour tout couple de sommets ( x , x ) ∈ X , l'arc/arête ( x , x ) appartient à U si

f 2 f

et seulement s'il existe un chemin/chaine de x vers x .

i j i j
i j

Le calcul de la fermeture transitive d'un graphe peut se faire en faisant la somme booléenne
des "puissances" successives de sa matrice d'adjacence. Considérons par exemple le graphe orienté
suivant :
Soit le graphe d'ordre 7 suivant :
la matrice d'adjacence associé est :

Fig. 1.12 
16 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES

 
0 1 0 0 0 0 0
0 0 0 0 0 1 1
 
 
 

 0 0 0 1 0 0 0 

A= 0 0 0 0 1 0 0
 

 

 0 0 0 0 0 0 1 


 1 0 0 0 1 0 0 

0 0 1 0 0 0 0

Dans cette matrice, A ( i, j) = 1 ssi il existe un chemin de longueur 1 pour aller de i à j. Pour
qu'il existe un chemin de longueur 2 pour aller d'un sommet a à un sommet b, il faut qu'il existe
un sommet i tel qu'il existe un chemin de longueur 1 de a vers i et un autre chemin de longueur
1 de i vers b. Pour tester cela, il s'agit de parcourir simultanément la ligne a et la colonne b de la
matrice A et de regarder s'il y a un 1 à la même position dans la ligne a et la colonne b. Ainsi, en
multipliant cette matrice par elle-même, on obtient la matrice A 2 des chemins de longueur 2 :

 
0 0 0 0 0 1 1
1 0 1 0 1 0 0
 
 
 

 0 0 0 0 1 0 0 

2 
A = 0 0 0 0 0 0 1


 

 0 0 1 0 0 0 0 


 0 1 0 0 0 0 1 

0 0 0 1 0 0 0

Dans cette matrice, A 2 ( i, j) = 1 ssi il existe un chemin de longueur 2 pour aller de i à j. Par
exemple, A 2 (a, g) = 1 car il existe un chemin (< a; b; g >) de longueur 2 allant de a à g. De façon
plus générale, A k est la matrice des chemins de longueur k.
En additionnant A et A2, on obtient la matrice A + A2 des chemins de longueur inférieure ou
égale à 2 :

 
0 1 0 0 0 1 1
1 0 1 0 1 1 1
 
 
 

 0 0 0 1 1 0 0 

A + A2 =  0 0 0 0 1 0 1
 

 

 0 0 1 0 0 0 1 


 1 1 0 0 1 0 1 

0 0 1 1 0 0 0

Selon le même principe, on calcule la matrice A + A2 + A3 + A4 + A5 des chemins de longueur

inférieure ou égale à 5 :
3. CONNEXITÉ DANS LES GRAPHES 17

 
1 1 1 1 1 1 1
1 1 1 1 1 1 1
 
 
 

 0 0 1 1 1 0 1 

2 3 4 5 
A+A +A +A +A = 0 0 1 1 1 0 1


 

 0 0 1 1 1 0 1 


 1 1 1 1 1 1 1 

0 0 1 1 1 0 1

Si on recommence une fois de plus, et que l'on calcule la matrice A + A 2 + A 3 + A 4 + A 5 + A 6

des chemins de longueur inférieure ou égale à 6, on constate que cette matrice est égale à celle
des chemins de longueur inférieure ou égale à 5. Par conséquent A + A 2 + A 3 + A 4 + A 5 est la
matrice d'adjacence de la fermeture transitive G f du graphe G de départ, on constate qu'un nouvel
arrangement des colonnes et des lignes permet de faire apparaître des matrices carrées, uniquement
formées des 1, s'appuyant sur la diagonale principale.
 
1 1 1 1 1 1 1
1 1 1 1 1 1 1
 
 
 

 1 1 1 1 1 1 1 

A + A2 + A3 + A4 + A5 =  0 0 0 1 1 1 1
 

 

 0 0 0 1 1 1 1 


 0 0 0 1 1 1 1 

0 0 0 1 1 1 1

La fermeture transitive du graphe G = ( X ,U ) est le graphe G f = ( X ,U f ) tel que :

Uf = {(a, a), (a, b), (a, f ), (a, g), (a, c), (a, d ), (a, e), ( b, b), ( b, a), ( b, f ), ( b, g), ( b, c), ( b, d ),
( b, e), ( g, g), ( g, c), ( g, d ), ( g, e), ( c, c), ( c, d ), ( c, e), ( c, g), ( d, d ), ( d, e), ( d, g), ( d, c),
( e, e), ( e, g), ( e, c), ( e, d ), ( f , f ), ( f , a), ( f , b), ( f , g), ( f , c), ( f , d ), ( f , e)}.

3.4 Connexité
La notion de connexité exprime la possibilité d'aller de n'importe quel sommet du graphe à
n'importe quel autre sommet du graphe.

Dénition 1.21 Un multigraphe connexe est un graphe tel que pour toute paire de sommets x
et y, il existe une chaîne reliant x et y.
Exemple 1.12 Le plan d'une ville doit être connexe.
Ce graphe 1.13 est non connexe.
3.5 Composante connexe
18 CHAPITRE 1. ELÉMENTS DE THÉORIE DES GRAPHES

Fig. 1.13  Exemple de graphe non connexe

Dénition 1.22 Une composante connexe est un sous graphe connexe de taille maximale.

Remarque 1.5 il est toujours possible de partitionner un graphe en composantes connexes. Par
exemple, sur la gure 1.3, si on considère le multigraphe alors il est scindé en 3 composantes
connexes : {a}, { g, c}, {e, f , d, h, b}.

Notons que si l'on calcule la fermeture transitive d'un graphe connexe, on obtient un graphe
complet. De même, si l'on calcule la fermeture transitive d'un graphe comportant k composantes
connexes, on obtient un graphe contenant k sous-graphes complets (un pour chaque composante
connexe).

3.6 Forte connexité

Cas des graphes orientés : On retrouve ces diérentes notions de connexités dans les graphes
orientés, en remplaçant naturellement la notion de chaine par celle de chemin : on parle de graphe
fortement connexe au lieu de connexe, de composante fortement connexe au lieu de composante
connexe.

Dénition 1.23 Un digraphe est dit fortement connexe si entre toute paire de sommets, il
existe un chemin de x vers x et un chemin de x vers x .
Soit G = ( X ,U ) un graphe. Si quels que soient x , x ∈ X , il existe un chemin de x vers x et un
i j j i

chemin de x vers x , alors le graphe est fortement connexe. Sinon on dénit des composantes
i j i j

fortement connexes.
j i
3. CONNEXITÉ DANS LES GRAPHES 19

Exemple 1.13

Dénition 1.24 On appelle composante fortement connexe tout sous-graphe induit maximal
fortement connexe (maximal signie qu'il n'y a pas de sous-graphe induit connexe plus grand
contenant les sommets de la composante).
Exemple 1.14 Par exemple, le graphe orienté suivant contient 2 composantes fortements connexes :
la première est le sous-graphe déni par les sommets {a, b, c, d} et la seconde est le sous-graphe déni
par les sommets {e, f , g}.

Comme pour les graphes non orientés, une façon de déterminer si un graphe orienté est fortement
connexe consiste à calculer sa fermeture transitive : si la fermeture transitive du graphe est le graphe
complet, alors il est fortement connexe.
Exemple 1.15 Revenons à l'exemple du graphe 1.12, a chacune des sous matrices carrées unités
de la matrice A + A + A + A + A correspond une composante fortement connexe : { A, B, F } et
2 3 4 5

{C, D, E, G } sont les ensembles de sommets des deux composantes fortement connexes du graphe
de la gure 1.12.
 [ Deuxième Chapitre \
Le problème du plus court chemin

Les problèmes de cheminement dans les graphes (en particulier la recherche d'un plus court
chemin) comptent parmi les problèmes les plus anciens de la théorie des graphes et les plus importants
par leurs applications.
On se place dans le cas des graphes orientés valués G = ( X ,U ). Mais les résultats et algorithmes
présentés se généralisent facilement aux cas des graphes non orientés valués en transformant le
graphe non-orienté en un graphe orienté en remplaçant une arête entre deux sommets par deux arcs
de sens inverse entre ces sommets.

Dénition 2.1 Soit G = ( X ,U ) un graphe valué; on associe à chaque arc u = (i, j) une longueur
d ( u) ou d . Le problème du plus court chemin entre i et j consiste à trouver un chemin µ( i, j )
de i à j tel que :
ij

d ( u) soit minimale.
X
d (µ) =
u∈µ

Interprétation de d (µ ) : coût de transport, dépense de construction, temps nécessaire de par-

cours, ...

Dans la recherche d'un plus court chemin de x à y, trois cas peuvent se présenter :
• Il n'existe aucun chemin de x à y (par exemple, si x et y appartiennent à deux composantes
fortement connexes diérentes de G ).
• Il existe des chemins de x à y mais pas de plus court chemin.
• Il existe un plus court chemin de x à y.

Exemple 2.1 On considère le graphe suivant : Il existe des chemins de x à y (et même une innité),

mais il n'existe pas de plus court chemin de x à y (il sut d'emprunter le cycle de poids négatif
autant de fois que nécessaire). Il existe un plus court chemin de x à z mais pas de chemin de z à x.
20
1. LES PLUS COURTS CHEMINS D'UN SOMMET À TOUS LES AUTRES 21

Dénition 2.2 Un circuit de longueur négative est appelé circuit absorbant .

Et alors, une condition nécessaire et susante d'existence de plus court chemin est donnée par
le résultat suivant.

Théorème 2.1 Dans un graphe orienté valué fortement connexe G = ( X ,U ), il existe un plus
court chemin entre tout couple de sommets si et seulement s'il n'existe pas de circuit absorbant
dans G.

On supposera que le graphe G ne comporte pas de circuit absorbant.

1 Les plus courts chemins d'un sommet à tous les autres

On va maintenant étudier 2 algorithmes qui permettent de résoudre des problèmes de recherche
de plus courts chemins à origine unique :
 l'algorithme de Dijkstra résout ce problème lorsque tous les coûts sont positifs ou nuls,
 l'algorithme de Ford-Bellman résout ce problème lorsque les coûts sont positifs, nuls ou
négatifs, sous réserve qu'il n'y ait pas de circuit absorbant (de coût négatif).
Les deux algorithmes procèdent de la même façon, l'idée est d'associer à chaque sommet xi ∈ X
une valeur d ( xi ) qui représente une borne maximale du coût du plus court chemin entre x0 et xi .
Ainsi, au départ,
 d ( x0 ) = 0, et
 d ( xi ) = +∞ pour tout sommet xi 6= x0 .
L'algorithme diminue alors progressivement les valeurs d ( xi ) associées aux diérents sommets,
jusqu'à ce qu'on ne puisse plus les diminuer, autrement dit.

Pour diminuer les valeurs de d , on va itérativement examiner chaque arc ( xi , x j ) du graphe,

et regarder si on ne peut pas améliorer la valeur de d ( x j ) en passant par xi . Cette opération de
diminution est appelée "relâchement de l'arc ( xi , x j )".

Les algorithmes de Dijkstra et Bellman-Ford procèdent tous les deux par relâchements successifs
d'arcs. La diérence entre les deux est que dans l'algorithme de Dijkstra, chaque arc est relâché
une et une seule fois, tandis que dans l'algorithme de Bellman-Ford, chaque arc peut être relâché
plusieurs fois.

1.1 Algorithme de Dijkstra-Moore

Soit un graphe G = ( X ,U ) connexe dont toutes les valuations sont positives. L'algorithme de
Moore 1957 et Dijkstra 1959 permet d'obtenir le plus court chemin d'un sommet A à tous les autres.
Cet algorithme fonctionne en au plus | X | − 1 itérations.
22 CHAPITRE 2. LE PROBLÈME DU PLUS COURT CHEMIN

Algorithme
1. Attribuer le poids 0 au point initial.
2. Attribuer aux sommets adjacents du point initial le poids des arêtes qui les relient (en
indiquant la provenance) et aux autres un poids inni.
3. Prendre le poids le plus petit et le considérer comme dénitif.
4. Recommencer le processus à partir du point dont on vient de trouver le poids dénitif ( en
faisant la somme des poids et en choisissant le poids minimal),
ç-à-d faire d(x ) ← d(x ) + d(x , x ) où x est le sommet tel que d(x ) soit minimale et
j i i j i i
x j ∈ Γ { x i }.
+

5. Réitérer jusqu'a ce que le sommet extrémité ait un poids dénitif

Exemple 2.2 Trouver le chemin minimale partant de A vers G.

on a le tableau résumant les itérations de l'algorithme de Dijkstra

A B C D E F G Sommets
init 0 2;A 1;A - - - -
1 - 3;C 1;A 5; C 4; C 6;C -
2 - 2;A - 3; B 5; B - -
3 - - - 3; B 6; D 9;D 8; D A
4 - - - - 4; C 5;E - C
5 - - - - - 5;E 7;F E
6 - - - - - - 7;F F
G
Exercice 2.1 On considère un réseau de télécommunications, composé d'émetteurs/récepteurs
pouvant s'envoyer des messages, avec une certaine abilité de communication, c'est à dire une
certaine probabilité pour que la communication ne soit pas interrompue. On modélise ce problème à
l'aide du graphe orienté et valué suivant 2.1, où la valuation d'un arc est une valeur réelle comprise
entre 0 et 1 et indiquant la probabilité pour que la communication se passe sans problème.
1. LES PLUS COURTS CHEMINS D'UN SOMMET À TOUS LES AUTRES 23

Fig. 2.1  Modélisation du réseau de télécommunications

1.2 Algorithme de Bellman-Ford

L'algorithme de Dijkstra ne marche pas toujours quand le graphe contient des arcs dont les coûts
sont négatifs. Considérons par exemple le graphe suivant :

Pour aller de a à f , l'algorithme de Dijkstra va trouver le chemin < a, c, e, f >, de poids 3, alors
que le chemin < a, b, d, e, f > est de poids 2.
L'algorithme de Bellman-Ford (1958-1962) permet de trouver les plus courts chemins à origine
unique dans le cas où le graphe contient des arcs dont le coût est négatif, sous réserve que le graphe
ne contienne pas de circuit absorbant.

Algorithme
1. On numérote les sommets dans un ordre quelconque (sauf le x ), 1

2. λ = +∞ sauf λ = 0,
i 1

3. pour tout sommet x pour lequel λ − λ > d(x , x ), d représentant la valuation de l'arc et
λ ∈ Γ ( x ), remplacer λ par λ + d ( x , x ),
j j i i j
−
i j j i i j

4. s'arrêter lorsque aucun λ ne peut plus être modié.

i
24 CHAPITRE 2. LE PROBLÈME DU PLUS COURT CHEMIN
Exemple 2.3 Le but est de trouver un chemin de A vers B associé à la valuation totale la plus
faible.

Par exemple nous avons

ACDB = 2 + 3 + 2 = 7
AEDB = 5 + 2 + 2 = 9
AEFB = 5 + 2 + 1 = 8

en executant l'algorithme on obtient le tableau suivant

A C D E F G B Sommets
init 0 +∞ +∞ +∞ +∞ +∞ +∞
1 0 2; A +∞ 5; A +∞ 3; A +∞ A
2 0 2; A 5; C -4; C -6; C 3; A 11; G C
3 0 2; A -10; F -4; C -6; C 3; A -5; F F
4 0 2; A -10; F -4; C -6; C 3; A -8; D D
B
ainsi le Chemin de valeur minimale est : ACFDB coût : -8
Théorème 2.2 Les valeurs nales des distances sont obtenues en au plus | X | − 1 itérations prin-
cipales (consistant à consulter les prédécesseurs de tous les sommets).

Remarque 2.1 Si au bout de | X | itérations, les valeurs λ continuent à être modiées, c'est que
le graphe possède un circuit de longueur strictement négative.
j

2 Plus courts chemin entre tous les sommets

2.1 Algorithme de Floyd-Warshall
Si l'on souhaite calculer tous les plus courts chemins entre tous les couples de sommets possibles,
on pourrait aussi utiliser la résolution du problème précédent, mais dans ce cas, on n'obtiendrait
pas un algorithme optimal. Il faudra utiliser dans ce cas un algorithme spécique à ce problème, par
exemple, l'algorithme de Floyd-Warshall.
2. PLUS COURTS CHEMIN ENTRE TOUS LES SOMMETS 25

Soient les matrices : D = (d i j ) ; C = ( c i j )

d i j = d ( i, j ) si ( i, j ) ∈ U
(

= +∞ sinon
A l'initialisation :
d ii = 0
c i j = 0 si d i j = +∞
(

= i sinon
En n d'algorithme :
d i j = longueur du plus court chemin entre i et j
c i j = prédécesseur de j sur le plus court chemin de i à j

L'algorithme utilisé est celui de Floyd (1962). Il consiste en trois boucles imbriquées sur i, j, k
de 1 à n et on calcule :
d i j = min( d i j , d ik + d k j ).

Algorithme
pour k = 1 à n
pour i=1 à n sauf k
pour j = 1 à n sauf i
si d > d + d
ij ik kj
d i j ← d ik + d k j
ci j ← ck j
Fin
Fin
Fin

Fig. 2.2  Procédure de Floyd-Warshall

Exemple

2.4   
0 5 1 2 − 1 1 1
 5 0 3 ∞   2 − 2 0 
D (0) =  C (0) = 
   
 
 1 3 0 4   3 3 − 3 
2 ∞ 4 0 4 0 4 −
26 CHAPITRE 2. LE PROBLÈME DU PLUS COURT CHEMIN
   
0 5 1 2 − 1 1 1
 5 0 3 7   2 − 2 1 
D (1) =  C (1) = 
   
 
 1 3 0 3   3 3 − 1 
2 7 3 0 4 1 1 −
   
0 5 1 2 − 1 1 1
(2)
 5 0 3 7 
(2)
 2 − 2 1 
D = C =
   
 
 1 3 0 3   3 3 − 1 
2 7 3 0 4 3 1 −
   
0 4 1 2 − 3 1 1
(3)
 4 0 3 6 
(3)
 3 − 2 1 
D = C =
   
 
 1 3 0 3   3 3 − 1 
2 6 3 0 4 3 1 −
   
0 4 1 2 − 3 1 1
 4 0 3 6   3 − 2 1 
D (4) =   = D̂ C (4) =   = Ĉ
   
 1 3 0 3   3 3 − 1 
2 6 3 0 4 3 1 −
 La distance du plus court chemin du sommet A au sommet B :
d (de D̂ ) =4
Le chemin le plus court du sommet A au sommet B : on cherche dans Ĉ la valeur de C = 3
12

ceci dit, pour aller du sommet A au sommet B on doit passer par le sommet intermediaire
12

C , de plus on a C = 3 et C = 2.
d'où le chemin le plus court du sommet A au sommet B est A → C → B.
13 32

 La distance du plus court chemin du sommet B au sommet D :

d (de D̂ ) =6
Le chemin le plus court du sommet B au sommet D : on cherche dans Ĉ la valeur de C = 3
24

ceci dit, pour aller du sommet B au sommet D on doit passer par le sommet intermediaire
24

C , de plus on a C = 3 et C = 1, ce qui veut dire que pour aller de C à D on doit passer

par A et on calcule C = 1 et C = 4 d'où le chemin le plus court du sommet B au sommet
23 34

D est B → C → A → B.
31 14

Exercice 2.2 Appliquer l'algorithme de Floyd-Warshall au graphe suivant :