É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 )}.

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.