UNIVERSITE CHEIKH ANTA DIOP (UCAD)

ÉCOLE SUPÉRIEURE POLYTECHNIQUE (E.S.P)

DÉPARTEMENT DE GESTION

Recherche Opérationnelle

Chapitre: Théorie des Graphes

Connexité a

[Link]
1er octobre 2020
(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 1 / 11
Sommaire

1 Connexité
Composante simplement connexe
Composante fortement connexe

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 2 / 11

Connexité

Définition Un graphe G(S,A) est dit connexe si tout sommet s ∈ S est

relié à au moins un autre sommet du graphe.
Exemple
1

5 c
2
d
b

e
3
4
a
Graphe connexe Graphe non connexe

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 3 / 11

Connexité

Composante simplement connexe :

Une composante (simplement) connexe d’un graphe est un sous graphe GS
tel que pour toute paire de sommets {x, y } de GS il existe une chaı̂ne les
reliant.
Exemple : Dans le graphe G(S,A) suivant, les sous graphes E et H
engendrés respectivement par les sommets {b, a, g, d, e} et {h, f, c} sont
simplement connexes.
c
b
d
h
a

e
g f
G
(a) un graphe non connexe

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 4 / 11

Connexité

Composante simplement connexe :

Une composante (simplement) connexe d’un graphe est un sous graphe GS
tel que pour toute paire de sommets {x, y } de GS il existe une chaı̂ne les
reliant.
Exemple : Dans le graphe G(S,A) suivant, les sous graphes E et H
engendrés respectivement par les sommets {b, a, g, d, e} et {h, f, c} sont
simplement connexes.
c b
b d
d
h a
a

e e
g f g
G E
(a) un graphe non connexe (b) une composante connexe de G

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 4 / 11

Connexité

Composante simplement connexe :

Une composante (simplement) connexe d’un graphe est un sous graphe GS
tel que pour toute paire de sommets {x, y } de GS il existe une chaı̂ne les
reliant.
Exemple : Dans le graphe G(S,A) suivant, les sous graphes E et H
engendrés respectivement par les sommets {b, a, g, d, e} et {h, f, c} sont
simplement connexes.
c b c
b d
d
h a h
a

e e
g f g f
G E H

(a) un graphe non connexe (b) une composante connexe de G (c) L’autre composante connexe de G

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 4 / 11

Algorithme de recherche de composantes simplement
connexes

Étant donné un graphe G = (S, A).

Pour chercher le(s) composante(s) simplement connexe(s) du graphe G,
on cherche les composantes simplement connexes de ses sommets.
Algorithme
Pour chercher la composante simplement connexe du sommet x, on
procède comme suit :
1 Marquer * le sommet x
2 Marquer * tout sommet adjacent à un sommet déjà marqué *
3 Répéter l’étape 2) jusqu’à ce que l’on ne puisse plus marquer aucun
sommet. Alors les sommets marqués sont ceux de la composante
connexe de x
a

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 5 / 11

Algorithme de recherche de composantes simplement
connexes

Exemple Considérons le graphe suivant.

Déterminer les composantes simplement connexes du graphe
Solution
a*

d b

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 6 / 11

Algorithme de recherche de composantes simplement
connexes

Exemple Considérons le graphe suivant.

Déterminer les composantes simplement connexes du graphe
Solution
a* a*

* *
d b d b

c c

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 6 / 11

Algorithme de recherche de composantes simplement
connexes

Exemple Considérons le graphe suivant.

Déterminer les composantes simplement connexes du graphe
Solution
a* a* a*

* * * *
d b d b d b

c c c*

Ce graphe admet une seule composante simplement connexe :

Cs (a) = {a, b, c, d}. Ce graphe est alors connexe car tous ses sommets
apparaissent dans Cs (a), le sommet a est choisit au hasard.
NB : un graphe qui admet plus d’une seule composante simplement
a
connexe n’est pas connexe. [Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 6 / 11

Composante fortement connexe

Définition Une composante fortement connexe d’un graphe est un sous

graphe GF tel que pour toute paire de sommets {x, y } de GF , il existe un
chemin de x à y et un chemin de y à x.
Pour déterminer le(s) composante(s) fortement connexe(s) d’un graphe,
nous devons chercher les composantes fortement connexes de ses différents
sommets. Composante fortement connexe d’un sommet x
La composante fortement connexe d’un sommet x de G notée Cf (x) est
définie par
:
Cf (x) = y ∈ G tel qu’il existe un chemin de x à y et de y à x

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 7 / 11

Algorithme de recherche de composantes fortement
connexes

Pour chercher la composante fortement connexe du sommet x, on procède

comme suit :
1 -Marquer ± le sommet x
2 -Marquer + tout suivant (non marqué) d’un sommet marqué +
-Marquer − tout précédent (non marqué) d’un sommet marqué −
3 - Lorsque plus aucun sommet ne peut être marqué ni + ni - les
sommets marqués ∓ constituent la composante fortement connexe de
x

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 8 / 11

Algorithme de recherche de composantes fortement
connexes
Exemple considérons le graphe suivant :
1 2

3 4

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 9 / 11

Algorithme de recherche de composantes fortement
connexes
Exemple considérons le graphe suivant :
1 2

3 4

Appliquons l’algorithme en cherchant la composante fortement connexe du

sommet 3, Cf (3)
1 2

3+
− 4

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 9 / 11

Algorithme de recherche de composantes fortement
connexes
Exemple considérons le graphe suivant :
1 2

3 4

Appliquons l’algorithme en cherchant la composante fortement connexe du

sommet 3, Cf (3)
2 + 2+
1 1

+
3+
− 4 3+ 4
−

5 5+

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 9 / 11

Algorithme de recherche de composantes fortement
connexes
Exemple considérons le graphe suivant :
1 2

3 4

Appliquons l’algorithme en cherchant la composante fortement connexe du

sommet 3, Cf (3)
2 + 2+ + 2+
1 1 1

+ +
3+
− 4 3+ 4 3+ 4−
− −

+
5 5+ 5−

a
Cf (3) = {3, 4, 5} donc le graphe G n’est pas fortement connexe car il
[Link]
n’admet pas une unique composante fortement connexe.
(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 9 / 11
Algorithme de recherche de composantes fortement
connexes

NB :
Un graphe est fortement connexe s’il admet une unique composante
fortement connexe. C’est à dire si dans la composante fortement connexe
d’un sommet quelconque de G, on ne note pas tous les sommets, alors G
n’est pas fortement connexe.

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 10 / 11

Exercice

Déterminer le(s) composante(s) simplement ou fortement connexe du

graphes ci-dessous.

B E H

A C F I K

D G J

En déduire s’il est simplement ou fortement connexe.

[Link]

(ESP/UCAD Mail : esp@[Link]) 1er octobre 2020 11 / 11