1.

Concepts de base
Graphes

Solen Quiniou
[Link]@[Link]

IUT de Nantes

Année 2024-2025 – BUT 1 (Semestre 2)

[Mise à jour du 27 janvier 2025]
Plan du cours
1 Introduction

2 Concepts de base

3 Concepts fondés sur les chemins, chaînes, circuits et cycles

S. Quiniou (IUT de Nantes) Graphes 2 / 62

Plan du cours
1 Introduction

2 Concepts de base

3 Concepts fondés sur les chemins, chaînes, circuits et cycles

S. Quiniou (IUT de Nantes) Graphes 3 / 62

Introduction
La théorie des graphes permet de représenter de nombreux problèmes
courants en informatique mais également en ingénierie, en sciences sociales,
en intelligence artificielle. . . en représentant ces problèmes en termes de
relations binaires entre objets.

On distingue les sommets (villes, par exemple) et les arcs ou arêtes

(communication entre les sommets) qui mettent en relation les sommets. On
associe parfois des caractéristiques aux arcs pour exprimer des distances,
des coûts. . .

Le type des problèmes que l’on peut poser concerne, par exemple, la
recherche d’itinéraires optimaux (problème classique du voyageur de
commerce : visiter toutes les villes avec un cheminement optimal).

S. Quiniou (IUT de Nantes) Graphes 4 / 62

Quelques exemples de graphes

Graphe à partir des entrées de Wikipédia et de la Graphe des transports en commun lyonnais
notion « influencé par » [Link]

[Link] visualisation_des_liens_amis_facebook_mondiaux

poster- new- [Link]

Graphe des liens d’amitié sur Facebook Graphe des interactions entre protéines
[Link] [Link]- [Link]/feuillesprobleme/ [Link]

feuille6/enonces/courseazero/[Link]

S. Quiniou (IUT de Nantes) Graphes 5 / 62

Exemples d’applications
Réseaux de communication : routier, ferroviaire, informatique. . .
▶ Réseau routier
⋆ Sommets : villes
⋆ Arcs : routes (éventuellement en sens unique)
▶ Réseau informatique
⋆ Sommets : ordinateurs
⋆ Arcs : connexions (physiques ou distantes)

Relations sociales : familiales, hiérarchiques, amicales. . .

▶ Sommets : individus
▶ Arcs : relations entre individus

Organisation logistique
▶ Sommets : événements
▶ Arcs : un arc entre deux événements s’ils ne peuvent pas avoir lieu en
même temps

...
S. Quiniou (IUT de Nantes) Graphes 6 / 62
Remarque
Le formalisme des graphes permet d’exprimer de nombreux problèmes
souvent de manière simple mais qui peuvent être difficiles à résoudre.

Les objectifs de ce cours sont les suivants :

étant donné un graphe, vérifier s’il possède certaines propriétés ;
étant donné un graphe, déterminer une sous-partie possédant certaines
propriétés ;
appliquer des algorithmes connus pour traiter des problèmes classiques.

S. Quiniou (IUT de Nantes) Graphes 7 / 62

Plan du cours
1 Introduction

2 Concepts de base
Graphes orientés
Graphes non orientés
Sommets adjacents, prédécesseurs et successeurs
Sommets source et puits
Degrés des sommets
Représentation des graphes
Sous-graphes et graphes partiels
Isomorphisme de graphes
Quelques graphes particuliers

3 Concepts fondés sur les chemins, chaînes, circuits et cycles

S. Quiniou (IUT de Nantes) Graphes 8 / 62

Graphes orientés
Définition
Un graphe orienté est un couple G = (S, A) où :
S est un ensemble fini d’éléments appelés sommets ;
▶ |S| = n est l’ordre du graphe
A est un ensemble fini de couples de sommets appelés arcs
et on a A ⊆ S × S.
▶ |A| = m est la taille du graphe

Un arc est noté (x, y ) ou x → y .

Définitions
Si a = (s1 , s2 ) ∈ A est un arc de G, les sommets s1 et s2 sont les extrémités
de a :
s1 est le début (ou l’origine) de a ;
s2 est la fin (ou l’extrémité finale) de a.

Si les deux extrémités d’un arc sont égales, l’arc est une boucle.
S. Quiniou (IUT de Nantes) Graphes 9 / 62
Graphes orientés
Exemple
4 S = {1, 2, 3, 4, 5}.
A = {(1, 3), (1, 5), (2, 1), (3, 1), (4, 1),
(4, 4), (5, 1), (5, 2)}.
1
Le sommet 1 est l’origine de l’arc (1, 3).
Le sommet 3 est la destination de l’arc
3 5 (1, 3).
L’arc (4, 4) est une boucle.

S. Quiniou (IUT de Nantes) Graphes 10 / 62

Graphes non orientés
Définition
Un graphe non orienté est un couple G = (S, A) où :
S est un ensemble fini d’éléments appelés sommets ;
A est un ensemble fini de couples de sommets appelés arêtes.

Une arête est notée {x, y }.

S. Quiniou (IUT de Nantes) Graphes 11 / 62

Graphes non orientés
Exemple
4
S = {1, 2, 3, 4, 5}.
1
A=
{{1, 3}, {1, 5}, {2, 1}, {4, 1}, {4, 4}, {5, 2}}.
3 5

Remarque
Soit un graphe orienté G = (S, A).
Son graphe non orienté associé est le graphe (non orienté) G′ = (S, A′ )
ayant le même ensemble de sommets S et dont l’ensemble d’arêtes vérifie :

{x, y } ∈ A′ ⇔ (x, y ) ∈ A ou (y , x) ∈ A

S. Quiniou (IUT de Nantes) Graphes 12 / 62

Sommets adjacents et voisins – graphes non orientés
Définition
Soit {s, t} une arête d’un graphe G. On dit que les sommets s et t sont
adjacents ou que s est un voisin de t.

Exemple
4
Les sommets 1 et 3 sont adjacents.
1
Le sommet 5 est un voisin du sommet 1.

3 5

S. Quiniou (IUT de Nantes) Graphes 13 / 62

Prédécesseurs et successeurs – graphes orientés
Définition
Soit G = (S, A) un graphe orienté.
L’ensemble des successeurs du sommet s est :
Γ+ (s) = {t ∈ S|(s, t) ∈ A}.
L’ensemble des prédécesseurs du sommet s est :
Γ− (s) = {r ∈ S|(r , s) ∈ A}.
L’ensemble des voisins du sommet s est : Γ(s) = Γ+ (s) ∪ Γ− (s).

S. Quiniou (IUT de Nantes) Graphes 14 / 62

Prédécesseurs et successeurs – graphes orientés
Exemple

3 5

L’ensemble des successeurs du sommet 1 est : Γ+ (1) = {3, 5}.

L’ensemble des prédécesseurs du sommet 1 est : Γ− (1) = {2, 3, 4, 5}.

S. Quiniou (IUT de Nantes) Graphes 15 / 62

Sommets source et puits
Définitions
Soit G = (S, A) un graphe orienté.
Une source de G est un sommet n’ayant aucun prédécesseur.
L’ensemble des sources de G est noté sources(G) = {s ∈ S|d − (s) = 0}.
Un puits de G est un sommet n’ayant aucun successeur. L’ensemble des
puits de G est noté puits(G) = {s ∈ S|d + (s) = 0}.

Exemple
b a

c sources(G) = {a, b}

d f e puits(G) = {d, g}

S. Quiniou (IUT de Nantes) Graphes 16 / 62

Propriétés
Propriété
Soit G = (S, A) un graphe orienté.
G est sans circuit ssi G−1 est sans circuit.
Les sources (respectivement les puits) de G sont les puits
(respectivement les sources) de G−1 .

Propriété
Tout graphe sans circuit possède au moins une source et un puits.

Preuve
Considérons un chemin c de G qui soit maximal au sens suivant : c = [x1 , . . . , xk ] et il n’existe
pas de sommet y de G tel que [y , x1 , . . . , xk ] ou [x1 , . . . , xk , y ] soient des chemins de G.
Un tel chemin c existe puisque G est sans circuit.
Cela signifie que x1 est une source de G et xk est un puits de G.

S. Quiniou (IUT de Nantes) Graphes 17 / 62

Degré des sommets – graphes non orientés
Définitions
Soit G un graphe non orienté.
Le degré d’un sommet s est noté d(s) et correspond au nombre d’arêtes dont
l’extrémité est s (en comptant 2 fois les boucles).
d(s) correspond au nombre de voisins de s.

Exemple
4

d(1) = 4.
3 5
d(4) = 3.

S. Quiniou (IUT de Nantes) Graphes 18 / 62

Degrés des sommets – graphes orientés
Définitions
Soit G un graphe orienté.
Le degré entrant d’un sommet s est noté d − (s) et correspond au
nombre d’arcs dont l’extrémité finale est s, c’est-à-dire au nombre de
prédécesseurs de s : d − (s) = |Γ− (s)|.
Le degré sortant d’un sommet s est noté d + (s) et correspond au
nombre d’arcs dont l’origine est s, c’est-à-dire au nombre de successeurs
de s : d + (s) = |Γ+ (s)|.
Le degré total d’un sommet s est noté d(s) et correspond au nombre
d’arcs dont l’origine ou l’extrémité finale est s, (en comptant deux fois les
boucles) : d(s) = d − (s) + d + (s).

S. Quiniou (IUT de Nantes) Graphes 19 / 62

Degrés des sommets – graphes orientés
Exemple

3 5

d − (1) = 4 d + (1) = 2 d(1) = 6

d − (4) = 1 d + (4) = 2 d(4) = 3

S. Quiniou (IUT de Nantes) Graphes 20 / 62

Représentation sagittale
La représentation sagittale d’un graphe est une représentation sous forme
de dessin. Cette représentation n’est pas unique.

3 5

Comment représenter un graphe pour coder efficacement un algorithme ? Le

choix dépend de l’algorithme !

S. Quiniou (IUT de Nantes) Graphes 21 / 62

Représentation par matrice d’adjacence
Définition
Soit G = (S, A) un graphe orienté dont on a numéroté les sommets de 1 à n.
La matrice d’adjacence de G est la matrice M = (mij ), de taille n × n, avec
(
1 si (i, j) ∈ A,
mij =
0 sinon.

Exemple
 
4 0 0 1 0 1
 1 0 0 0 0 
 
 
1 M=
 1 0 0 0 0 

 1 0 0 1 0 
 
3 5
1 1 0 0 0

Matrice d’adjacence
2

Une définition similaire s’applique aux graphes non orientés.

S. Quiniou (IUT de Nantes) Graphes 22 / 62
Représentation par matrice d’adjacence
Avantages
Facile à utiliser et à construire ;
Accès rapide à une arête (ou un arc) particulière (temps constant).

Inconvénients
Occupation de n2 cases mémoire quel que soit le nombre d’arêtes (ou
d’arcs) du graphe.

S. Quiniou (IUT de Nantes) Graphes 23 / 62

Représentation par liste des successeurs
Définition
Soit G = (S, A) un graphe orienté dont on a numéroté les sommets de 1 à n.
La liste des successeurs de G est la liste des successeurs (respectivement
voisins, pour les graphes non orientés) de chaque sommet et est donnée
sous la forme d’une liste chaînée.

Exemple
4

1
1 3 5
2 1
3 1
3 5
4 1 4
5 1 2
2

Liste des successeurs

S. Quiniou (IUT de Nantes) Graphes 24 / 62
Représentation par liste des successeurs
Avantages
Occupation minimale de la mémoire : codage uniquement des arêtes (ou
arcs) présentes dans le graphe ;
Accès rapide au successeur d’un sommet.

Inconvénients
Plus complexe à mettre en œuvre que la matrice d’adjacence ;
Accès plus long aux prédécesseurs d’un sommet, par exemple.

S. Quiniou (IUT de Nantes) Graphes 25 / 62

Sous-graphe
Définition
Soit G = (S, A) un graphe (orienté ou non). Un sous-graphe de G est un
graphe G′ = (S ′ , A′ ) tel que S ′ ⊂ S et A′ ⊂ A.

Exemple
4

1 4
1

5
3 5

2
2

Sous-graphe

S. Quiniou (IUT de Nantes) Graphes 26 / 62

Sous-graphe induit
Définition
Un sous-graphe G′ = (S ′ , A′ ) d’un graphe G = (S, A) est un sous-graphe
induit par S ′ si A′ est formé de tous les arcs (ou de toutes les arêtes) de G
ayant leurs extrémités dans S ′ :

∀x, y ∈ S ′ , (x, y ) ∈ A′ ⇔ (x, y ) ∈ A.

Exemple
4

3 5

3
2
Sous-graphe induit par
S ′ = {1, 3, 4}
S. Quiniou (IUT de Nantes) Graphes 27 / 62
Graphe partiel
Définition
Soit G = (S, A) un graphe et A′ ⊂ A un ensemble d’arcs ou d’arêtes. Un
sous-graphe G′ = (S ′ , A′ ) est un graphe partiel induit par A′ si

x ∈ S ′ ⇔ {∃y |(x, y ) ∈ A′ ou (y , x) ∈ A′ }.

Exemple
4

1
3 4

3 5

2
Graphe partiel induit par
A′ = {(3, 1), (4, 1), (4, 4)}
S. Quiniou (IUT de Nantes) Graphes 28 / 62
Sous-graphe couvrant
Définition
Un sous-graphe G′ = (S ′ , A′ ) d’un graphe G = (S, A) est un sous-graphe
couvrant s’il contient tous les sommets de S : S ′ = S.

Exemple
4

1 5 3

3 5 2 4

2 1

Sous-graphe couvrant

S. Quiniou (IUT de Nantes) Graphes 29 / 62

Isomorphisme de graphes
Définition
Deux graphes orientés G = (S, A) et G′ = (S ′ , A′ ) sont isomorphes s’il existe
une application bijective f : S → S ′ telle que

∀x, y ∈ S, (x, y ) ∈ A ⇔ (f (x), f (y )) ∈ A′ .

L’application f est alors un isomorphisme de graphes orientés.

Une définition similaire s’applique aux graphes non orientés.

Exemple
A
L’application f est un isomorphisme
3 4 B
entre les deux graphes :

 1 7→ A
C 

2 5  2→ 7 C



D f = 3 7→ E
1 


 4 7→ B


E
5 7→ D


S. Quiniou (IUT de Nantes) Graphes 30 / 62

Graphe simple
Définition
Soit G = (S, A) un graphe (orienté ou non). G est un graphe simple s’il ne
comporte aucune boucle.

Exemple

3 5

Dans un graphe simple, on a au plus un arc (ou une arête) entre 2 sommets.

S. Quiniou (IUT de Nantes) Graphes 31 / 62

Graphe complet
Définition
Soit G = (S, A) un graphe orienté. G est un graphe complet si
A = S × S.
Soit G = (S, A) un graphe non orienté. G est un graphe complet si toute
paire de sommets apparaît dans A.

Exemples
1 1

2 2

3 3

Graphe complet orienté Graphe complet non-orienté

S. Quiniou (IUT de Nantes) Graphes 32 / 62

Graphe complémentaire
Définition
Soit G = (S, A) un graphe.
Le graphe complémentaire Ḡ de G a les mêmes sommets que G mais deux
sommets sont adjacents dans Ḡ si et seulement s’ils ne le sont pas dans G.

Exemple
1
4

3 5
5

2
4

G Ḡ

S. Quiniou (IUT de Nantes) Graphes 33 / 62

Graphe réciproque et graphe symétrique
Définition
Soit G = (S, A) un graphe orienté.
Le graphe réciproque de G est le graphe G−1 = (S, A−1 ) où
A−1 = {(x, y ) ∈ S × S|(y , x) ∈ A} ;
Le graphe symétrique de G est le graphe GS = (S, A ∪ A−1 ).

Exemple
4

1 1
1

3 5 2 3 4
2 3 4

2 5 5

G G−1 GS
S. Quiniou (IUT de Nantes) Graphes 34 / 62
Graphe biparti
Définition
Soit G = (S, A) un graphe.
G est un graphe biparti si S peut être divisé en deux ensembles disjoints S1
et S2 afin que chaque arête relie un sommet de S1 et un sommet de S2 :
A ⊂ {{s1 , s2 }, s1 ∈ S1 , s2 ∈ S2 }.

Exemple

1 4

2 5

3 6

S1 S2

S. Quiniou (IUT de Nantes) Graphes 35 / 62

Multigraphe
Définition
Un multigraphe orienté G = (S, A, α, ω) est composé :
d’un ensemble S dont les éléments sont les sommets du graphe ;
d’un ensemble A dont les éléments sont les arcs du graphe ;
de deux fonctions α : A → S et ω : A → S qui associent à chaque arc
a ∈ A son origine α(a) et son extrémité finale ω(a).

Exemple
4 d S = {1, 2, 3, 4, 5}
A = {a, b, c, d, e, f , g, h}
c
 
1 
 a 7→ 1 
 a 7→ 3
 
 b→ 7 1  b→ 7 3

 

a b gh
 
α= c 7→ 4 ω= c 7→ 1
3 5 e  
d 7→ 4 d 7→ 4

 


 

 
f  
... ...
2

S. Quiniou (IUT de Nantes) Graphes 36 / 62

Plan du cours
1 Introduction

2 Concepts de base

3 Concepts fondés sur les chemins, chaînes, circuits et cycles

Graphes orientés : chemins et circuits
Graphes non orientés : chaînes et cycles
Graphes valués
Fermeture transitive d’un graphe
Sommets ascendants, descendants
Connexité et forte connexité

S. Quiniou (IUT de Nantes) Graphes 37 / 62

Graphes orientés : chemins et circuits
Définitions : chemin
Soit G = (S, A) un graphe orienté. Un chemin C est une suite
[x1 , x2 , . . . , xk ] de sommets de G tel que deux sommets consécutifs
quelconques xi et xi+1 sont reliés par un arc de G :

∀i, 1 ≤ i ≤ k − 1, (xi , xi+1 ) ∈ A.

La longueur d’un chemin est égale au nombre de sommets moins un.

Un chemin est simple s’il ne passe pas deux fois par le même arc.
Un chemin est élémentaire s’il ne passe pas deux fois par le même
sommet.

Définitions : circuit
On appelle circuit un chemin [x1 , x2 , . . . , xk ], de longueur supérieure ou
égale à 1, et dont l’origine et l’extrémité sont identiques : x1 = xk .
Un circuit élémentaire est un circuit qui ne possède qu’une seule
répétition, le sommet origine et le sommet extrémité.
S. Quiniou (IUT de Nantes) Graphes 38 / 62
Exemple

4 [3, 1, 5] est un chemin de longueur 2,

simple et élémentaire

1 [1, 3, 4] n’est pas un chemin

[4, 4] est un chemin et un circuit

3 5
[1, 5, 2, 1, 3] est un chemin simple

2 [1, 5, 2, 1] est un circuit simple et

élémentaire

S. Quiniou (IUT de Nantes) Graphes 39 / 62

Graphes non orientés : chaînes et cycles
Définitions : chaîne
Soit G = (S, A) un graphe non orienté. Une chaîne C est une suite
[x1 , x2 , . . . , xk ] de sommets de G tel que deux sommets consécutifs
quelconques xi et xi+1 sont reliés par une arète de G :

∀i, 1 ≤ i ≤ k − 1, {xi , xi+1 } ∈ A.

La longueur d’une chaîne est égale au nombre de sommets moins un.

Une chaîne est simple si elle ne passe pas deux fois par la même arête.
Une chaîne est élémentaire si elle ne passe pas deux fois par le même
sommet.

Définitions : cycle
On appelle cycle une chaîne [x1 , x2 , . . . , xk ], de longueur supérieure ou
égale à 1, et dont l’origine et l’extrémité sont identiques : x1 = xk .
Un cycle élémentaire est un cycle qui ne possède qu’une seule
répétition, le sommet origine et le sommet extrémité.
S. Quiniou (IUT de Nantes) Graphes 40 / 62
Exemple

4
[3, 1, 5] est une chaîne de longueur 2,
simple et élémentaire
1
[4, 4] est une chaîne et un cycle

3 5 [1, 5, 2, 1, 3] est une chaîne simple

[1, 5, 2, 1] est un cycle simple et

2 élémentaire

S. Quiniou (IUT de Nantes) Graphes 41 / 62

Graphe valué
Définitions : graphe valué et valuation
Soit G = (S, A, v ) un graphe (orienté ou non)
G est un graphe valué s’il est muni d’une application

v: A → R
(x, y ) 7→ v (x, y )

L’application v est appelée valuation

Remarque
L’application v peut être étendue en une fonction S × S → R ∪ {+∞}, en
posant : v (x, y ) = +∞ si (x, y ) ∈
/A

S. Quiniou (IUT de Nantes) Graphes 42 / 62

Exemples de graphes valués

1 a

B 2 1,6

-9
b 1

C
-2,9 -1 2

2 5
c
D 3 2
0,24
-3 15
0 e
E

2,1
0

F d 3

Graphe non orienté Graphe orienté

S. Quiniou (IUT de Nantes) Graphes 43 / 62

Représentation matricielle
Définition : matrice de valuation
Soit G = (S, A, v ) un graphe valué dont on a numéroté les sommets de 1 à n
La matrice de valuation de G est la matrice carrée M = (mij ) de taille
n × n définie par :
(
v (i, j) si (i, j) ∈ A
mij =
+∞ sinon

Remarque
Analogie avec la matrice d’adjacence mais les coefficients correspondent
cette fois à la valuation des arcs

S. Quiniou (IUT de Nantes) Graphes 44 / 62

Exemples de graphes valués avec leur matrice
A a

1 2 1,6

B b 1

-9
-2,9 -1 2

C
c
2 5
0,24
D 3 2
0 e
-3 15

2,1
E

0
d 3

 
+∞ 1 +∞ +∞ +∞ 5  
+∞ 2 1 +∞ −1
 1 +∞ −9 +∞ +∞ 2 
1, 6 +∞ −2, 9 +∞ +∞
   
   
 +∞ −9 +∞ 2 3 15   
   +∞ +∞ +∞ +∞ 0, 24 
+∞ +∞ 2 +∞ −3 +∞
   
+∞ +∞ 0 3 +∞
   
   
 +∞ +∞ 3 −3 +∞ 0 
2 +∞ +∞ 2, 1 +∞
5 2 15 +∞ 0 +∞

S. Quiniou (IUT de Nantes) Graphes 45 / 62

Valuation d’un chemin
Définition : valuation d’un chemin
Soit G = (S, A, v ) un graphe valué
Valuation d’un chemin (ou longueur) : somme des valuations des arcs
qui composent le chemin (même chose pour les chaînes)
Valuation d’un chemin sans arc : 0

Exemple
A

1 La valuation de la chaîne
B
[A, F , C, E, D] est
5 + 15 + 3 − 3 = 20
-9

2 5

D 3 2

-3 15

S. Quiniou (IUT de Nantes) Graphes 46 / 62

Fermeture transitive d’un graphe
Définitions
Soit G = (S, A) un graphe.
La fermeture transitive de G est un graphe G+ = (S, A+ ) et elle vérifie
la propriété suivante :

(x, y ) ∈ A+ ⇔ ∃[x, y ] ∈ G.

La fermeture réflexo-transitive de G est un graphe G∗ = (S, A∗ ) et elle

vérifie la propriété suivante :

(x, y ) ∈ A∗ ⇔ x = y ou ∃[x, y ] ∈ G.

La fermeture réflexo-transitive correspond ainsi à la fermeture transitive à

laquelle on ajoute des boucles sur chacun des sommets qui n’en ont pas déjà
(pour vérifier la propriété de réflexivité).

S. Quiniou (IUT de Nantes) Graphes 47 / 62

Calcul de la fermeture transitive
Exemple de fermeture réflexo-transitive
e g

Arcs en bleu : ajoutés

b f
par transitivité

a c h Arcs en rouge : ajoutés

par réflexivité
d

Calcul de G+ à partir de G
Cela consiste à ajouter les arcs (x, y ) pour tout y tel que [x, y ] est dans G,
c’est-à-dire pour tout sommet y descendant de x. Ainsi, les successeurs de x
dans G+ sont les descendants de x dans G.
On peut alors utiliser une procédure de calcul des descendants (par un
parcours en largeur, par exemple).
S. Quiniou (IUT de Nantes) Graphes 48 / 62
Sommets ascendants, descendants
Définitions
Soit G = (S, A) un graphe orienté.
Le sommet xk est un descendant du sommet xi ssi il existe un chemin
d’origine xi et d’extrémité xk . L’ensemble des descendants de xi est noté :

descG (xi ) = {xk ∈ S | ∃ [xi , xk ] dans G}.

Le sommet xk est un ascendant du sommet xi ssi il existe un chemin

d’origine xk et d’extrémité xi . L’ensemble des ascendants de xi est noté :

ascG (xi ) = {xk ∈ S | ∃ [xk , xi ] dans G}.

Propriété
Soit G = (S, A) un graphe orienté. On a alors :

∀x ∈ S, ascG (x) = descG−1 (x).

S. Quiniou (IUT de Nantes) Graphes 49 / 62

Exemple

3
descG (5) = {1, 2, 3, 4}
ascG (5) = ∅
2
descG (1) = ∅
ascG (1) = {2, 3, 4, 5}

S. Quiniou (IUT de Nantes) Graphes 50 / 62

Connexité et forte connexité
Le problème de la recherche de composantes connexes est un problème
d’un intérêt pratique majeur dans de nombreuses applications liées à toutes
sortes de réseaux : on veut savoir quels sont les sommets reliés sans
chercher à savoir explicitement comment.

La notion de connexité est liée à l’existence de chaînes (graphes non

orientés).
La notion de forte connexité est liée à l’existence de chemins (graphes
orientés).

S. Quiniou (IUT de Nantes) Graphes 51 / 62

Graphes connexes
Définition
Un graphe non orienté est connexe si, pour tout couple de sommets x et y , il
existe une chaîne reliant x à y .

Un graphe orienté est connexe si le graphe non orienté associé est connexe.

Théorème
Il existe une chaîne simple entre chaque paire de sommets (distincts) d’un
graphe simple connexe.

S. Quiniou (IUT de Nantes) Graphes 52 / 62

Exemples de graphes connexes et non connexes

a b
a b

c d
c d

e e f

Graphe connexe Graphe non connexe

S. Quiniou (IUT de Nantes) Graphes 53 / 62

Composantes connexes
Définition
Une composante connexe d’un graphe G = (S, A) est un sous-ensemble
maximal de sommets tels que deux sommets quelconques soient reliés par
une chaîne : si x ∈ C, alors
∀y ∈ C, il existe une chaîne reliant x à y ,
∀z ∈ S \ C, il n’existe pas de chaîne reliant x à z.

Les composantes connexes d’un graphe G = (S, A) forment une

partition de S.
Un graphe est connexe ssi il a une seule composante connexe.
Le sous-graphe induit par une composante connexe C est connexe.
La composante connexe C qui contient un sommet x ∈ S est
C = {y ∈ S | il existe une chaîne reliant x à y }.

S. Quiniou (IUT de Nantes) Graphes 54 / 62

Exemples de composantes connexes

a b

c d 1 6 3 7 4

e f 2 5

Graphe avec 2 composantes Graphe avec 4 composantes connexes :

connexes : {a, c, e}, {b, d, f } {1}, {2, 6}, {3, 5, 7}, {4}

S. Quiniou (IUT de Nantes) Graphes 55 / 62

Graphes fortement connexes
Définition
Un graphe orienté est fortement connexe si, pour tout couple de sommets x
et y , il existe un chemin reliant x à y .

Théorème
Un graphe est fortement connexe ssi, pour tout couple de sommets x et y , il
existe un circuit passant par x et y .

Théorème
Un graphe orienté fortement connexe est connexe.

S. Quiniou (IUT de Nantes) Graphes 56 / 62

Exemples de graphes fortement connexes et non
fortement connexes

a
c

e
d

a
e

Graphe fortement connexe Graphe non fortement connexe

S. Quiniou (IUT de Nantes) Graphes 57 / 62
Composantes fortement connexes
Définition
Une composante fortement connexe d’un graphe G = (S, A) est un
sous-ensemble maximal de sommets tels que deux sommets quelconques
soient reliés par un chemin : si x ∈ C, alors
∀y ∈ C, il existe un circuit passant par x et y ,
∀z ∈ S \ C, il n’existe pas de circuit passant par x et z.

Les composantes fortement connexes d’un graphe G = (S, A) forment

une partition de S.
Un graphe est fortement connexe ssi il a une seule composante
fortement connexe.
Le sous-graphe induit par une composante fortement connexe C est
fortement connexe.
La composante fortement connexe C qui contient un sommet x ∈ S est
C = {y ∈ S | il existe un chemin reliant x à y et un chemin reliant y à x}.

S. Quiniou (IUT de Nantes) Graphes 58 / 62

Exemples de composantes fortement connexes
1

b 7

5
c

6
d

e
3

a
4

Graphe avec 3 composantes Graphe avec 3 composantes

fortement connexes : fortement connexes :
{a}, {b, c, d}, {e} {1, 7}, {2, 3, 5, 6}, {4}
S. Quiniou (IUT de Nantes) Graphes 59 / 62
Calcul des composantes fortement connexes
Théorème
Y = (descG (xi ) ∩ ascG (xi )) ∪ {xi } est une composante fortement connexe
maximale du graphe G.
Ce théorème nous donne un premier algorithme pour déterminer chacune
des composantes fortement connexes d’un graphe.

S. Quiniou (IUT de Nantes) Graphes 60 / 62

Exemple
Une administration veut améliorer le
a
cadre de vie de ses 9 employés
a, b, c, d, e, f , g, h et i qui travaillent
dans la même salle. Ils échangent c

entre eux des documents tel

qu’indiqué sur le graphe ci-contre. d

g e
L’objectif est de répartir les
employés dans plusieurs bureaux
b
en séparant le moins possible ceux
entre lesquels les documents
circulent. Une solution est donnée f

par le calcul des composantes

fortement connexes du graphe.
h

S. Quiniou (IUT de Nantes) Graphes 61 / 62

Exemple - suite
1 Choisissons par exemple le sommet a
▶ descG (a) = {a, b, c, d, e, f , g, h, i}
▶ ascG (a) = {a, c, d, e}
▶ Composante fortement connexe 1 :
({a, b, c, d, e, f , g, h, i} ∩ {a, c, d, e}) ∪ {a} = {a, c, d, e}

2 Choisissons le sommet b
▶ descG (b) = {b, f , g, h, i}
▶ ascG (b) = {a, b, c, d, e, g}
▶ Composante fortement connexe 2 :
({b, f , g, h, i} ∩ {a, b, c, d, e, g}) ∪ {b} = {b, g}

3 Choisissons le sommet f
▶ descG (f ) = {f , h, i}
▶ ascG (f ) = {a, b, c, d, e, f , g, h, i}
▶ Composante fortement connexe 3 :
({f , h, i} ∩ {a, b, c, d, e, f , g, h, i}) ∪ {f } = {f , h, i}

S. Quiniou (IUT de Nantes) Graphes 62 / 62