Université d’Adrar

Faculté des sciences et technologies

Département de Mathématique et Informatique

2 eme année: Informatique

Théorie des graphes

Chapitre 04:
La connexité dans un
graphe

2021-2022 1
 Plan du cours

1 Introduction

2 Cheminements dans un graphe

3 La connexité et la forte connexité

4 Parcours d’un graphe

4 Algorithmes de connexité

2
 Introduction (1)

À quel moment un réseau informatique satisfait-il à la propriété

que tous les ordinateurs du réseau, pris deux à deux, puissent
partager l'information ?
Des messages peuvent-ils lui être envoyés au moyen d'un ou de
plusieurs ordinateurs intermédiaires ?
Quand un graphe sert à représenter ce réseau informatique, où
les sommets sont des ordinateurs et les arêtes (arcs) , les liens de
communication, cette question devient:
Existe-t-il toujours une chaîne entre deux sommets de ce graphe ?

3
Introduction (2)

Représentation des liens entre quelques sites internet.

4
 Cheminements dans un graphe

Les cheminement dans la théorie des graphes sont de quatre type:

la chaîne, le cycle, le chemin et le circuit.
Remarque: La notion de chaîne et de cycle ne respecte pas
l’orientation des arcs, par contre celle de chemin et de circuit la
respecte.
On définira ces notions dans le graphe G suivant:

Graphe G

5
 Chaîne et Cycle (1)

Chaîne:
Soit G = (S, A) un graphe,
Une chaîne C joignant deux sommets s0 et sk dans un graphe G est
une suite de sommets reliés par des arêtes tels que, deux sommets
successifs ont une arête commune.
On la note: C= (s0 , s1 , s2 , … , sk).
On dit que s0 et sk sont les extrémités de la chaîne.
On appelle k la longueur de la chaîne ( nombre d’arêtes qui la
composent)
Exemple:
Dans le graphe G, C = (x1, x3, x5, x2, x4) est une chaîne. 6
 Chaîne et Cycle (2)

Une chaîne est simple si elle ne contient pas deux fois la

même arête ( tous les arcs sont différents).
Une chaîne est élémentaire si elle ne contient pas deux fois le
même sommet ( tous les sommets sont différents).
Exemple:
Dans le graphe G:
La chaîne C= (x1, x3, x5, x2, x4, x5 ) est simple.
La chaîne C= (x1, x3, x5, x2, x3, x5) n’est pas simple, l’arête (x3, x5) est
parcouru deux fois.
La chaîne C= (x5, x2, x4, x6) est élémentaire.
La chaîne C= (x5, x2, x4, x5, x6) n’est pas élémentaire. 7
 Chaîne et Cycle (3)

On appelle distance entre deux sommets, du graphe la longueur

de la plus courte ( petite) chaîne qui relie ces deux sommets.
On appelle diamètre du graphe la plus grande distance
constatée entre deux sommets quelconques du graphe.
Exemple:
Dans le graphe G:
La distance entre x1 et x4 est égale à 2.
D’après le tableau des distances,
le diamètre du graphe G est égale à 3.

Tableau des distances

8
 Chaîne et Cycle (4)

Cycle:
Soit G = (S, A) un graphe,
Un cycle est une chaîne simple dont les deux extrémités coïncident.
(s0 coïncide avec sk ), on le note: (x0, x1, x2, …, xk = x0)
Exemple:
Dans le graphe G:
La suite de sommets suivante (x1, x3, x5, x2, x1 ) est un cycle.

9
 Chemin et Circuit (1)

Chemin:
Soit G = (S, A) un graphe,
Un chemin du sommets s0 et sk dans un graphe G est une séquence
de sommets reliés successivement par des arcs orienté dans le même
sens.
On le note: C= (s0 , s1 , s2 , … , sk).
Autrement dit: Deux sommets successifs d’un chemin sont
respectivement extrémité initiale et terminale du même arc.
Exemple:
Dans le graphe G,
C = (x1, x2, x4, x6) est un chemin. 10
 Chemin et Circuit (2)

Un chemin est simple si elle ne contient pas deux fois la

même arc ( tous les arcs sont différents).
Un chemin est élémentaire si elle ne contient pas deux fois le
même sommet ( tous les sommets sont différents). .
Exemple:
Dans le graphe G:
Le chemin C= (x1, x2, x5, x6 ) est simple.
Le chemin C= (x1, x3, x2, x5, x3, x2 , x4) n’est pas simple, l’arc (x3, x2)
est parcouru deux fois.
Le chemin C= (x3, x2, x5, x6) est élémentaire.
Le chemin C= (x3, x2, x5, x6, x5) n’est pas élémentaire. 11
 Chemin et Circuit (3)

Circuit:
Soit G = (S, A) un graphe,
Un circuit est un chemin dont les deux extrémités coïncident.
(s0 coïncide avec sk ), on le note: (x0, x1, x2, …, xk = x0)
Exemple:
Dans le graphe G:
La suite de sommets suivante (x3, x2, x5) est un circuit.

12
 La connexité (1)

Définition:
On définit la connexité dans un graphe G = ( S, A) par la relation R
entre deux sommets quelconque si et sj

R est une relation d’équivalence (réflexivité, symétrie, transitivité).

Les classes d’équivalence induites sur S par cette relation forment
une partition de S en S1, S2, . . . ,Sp.
Le nombre p de classes d’équivalence distinctes est appelé
nombre de connexité du graphe. 13
 La connexité (2)

On peut alors donner une autre définition concernant la connexité

d’un graphe. Un graphe est dit connexe si et seulement si son nombre
de connexité est égal à 1.
Les sous-graphes G1, G2, . . . ,Gp engendrés par les sous-
ensembles S1, S2, . . . ,Sp sont appelés les composantes connexes
du graphe. Chaque composante connexe est un graphe connexe.
Exemple:

Ce graphe a quatre
composantes connexes :
{1}, {2, 6}, {3, 5, 7}, et {4}.

14
 La forte connexité (1)

On définit la forte connexité dans un graphe G = ( S, A) par la relation

R entre deux sommets quelconque si et sj

R est une relation d’équivalence (réflexivité, symétrie, transitivité).

Les classes d’équivalence induites sur S par cette relation forment
une partition de S en S1, S2, . . . ,Sp.
Les sous-graphes G1, G2, . . . ,Gp engendrés par les
sous-ensembles S1, S2, . . . ,Sp sont appelés les composantes
fortement connexes du graphe. 15
 La forte connexité (2)

Exemple:

Ce graphe a deux composantes Ce graphe a trois composantes

fortement connexes : fortement connexes :
{a, b} et {c}. {1, 7}, {2, 3, 5, 6} et {4}.

16
 Le parcours d’un graphe

Un parcours de graphe est un algorithme consistant à explorer les

sommets d'un graphe de proche en proche à partir d'un sommet initial.
Un parcours d'un graphe est un procédé qui permet de choisir, à
partir des sommets visités, le sommet suivant à visiter. Le problème
consiste à déterminer un ordre sur les visites des sommets.
Les algorithmes de parcours n'ont pas une finalité intrinsèque. Ils
servent comme outil pour étudier une propriété globale du graphe,
comme la connexité ou la forte connexité.
Il existe de nombreux algorithmes de parcours:
 Le parcours en profondeur
 Le parcours en largeur. 17
 Parcours en largeur

Soit G un graphe orienté d’ordre n et fortement connexe

On appelle distance de s à s’ et on note d(s, s’) le nombre minimal
d’arcs d’un chemin entre s et s’.
Un parcours en largeur de G à partir d’un sommet donné s est une
permutation de ses sommets ( p1 , p2 , p3 , p4 , ... , pn )
telle que p1 = s
d(s, pi) ≤ d(s , pj) pour tout 1< i < j ≤ n
Exemples: on a le graphe G ci-contre
Exploration en largeur:
 à partir de 4 : 4, 2, 5, 3, 6, 1
 à partir de 5 : 5, 6, 3, 1, 4, 2 18
 Algorithme
Soit G un graphe orienté fortement connexe d’ordre n, On explore à partir
du sommet s.
Algorithme
pour i de 1 à n faire
marqué[i] = faux
F ← filevide()
ajoute (s, F)
marqué[s] = vrai
i ←1
Tantque non vide (F) faire
pi← retire (F)
pour tout successeur succ de pi faire
si marqué[succ] = faux alors
ajoute(succ, F)
marqué[succ] = vrai
finsi
finpour
i ← i+1
Fin tantque
résultat ← liste des pi 19
 Exemple

Parcourir en largeur le graphe ci-dessous à partir du sommet 4:

20
 Parcours en profondeur

Soit G un graphe orienté fortement connexe d’ordre n.

On obtient un parcours en profondeur de G si, à partir d’un
sommet donné s, en explorant récursivement en profondeur ses
successeurs non encore visités.
L’usage d’une pile permet d’écrire un algorithme itératif.

Exemples : on a le graphe G ci-contre

Exploration en profondeur:
 à partir de 4 : 4, 2, 3, 1, 5, 6.
 à partir de 3 : 3, 1, 2, 4, 5, 6.
21
 Algorithme
Soit G un graphe orienté fortement connexe d’ordre n, On explore à partir
du sommet s.
Algorithme
pour i de 1 à n faire
marqué[i] = faux
P ← pilevide ( )
empile (s, P)
marqué[s] ← vrai
i←1
Tantque non vide (P) faire
pi ← sommet (P)
pour tout successeur succ de pi faire
si marqué[succ] = faux alors
empile (succ, P)
marqué[succ] ← vrai
finsi
finpour
i ← i+1
fintantque
résultat ← la liste des pi 22
Exemple

23
 Algorithmes de connexité

Lors de la conception d’un réseau de communication notamment,

il peut être intéressant de savoir si la configuration choisie permet
une communication de n’importe quel point à n’importe quel autre.
Un moyen de le vérifier est de représenter le réseau sous la
forme d’un graphe et de vérifier qu’il est fortement connexe.
Pour cela, un algorithme qui détermine la composante fortement
connexe d’un graphe contenant un point donné est proposé.
Un algorithme permettant de trouver toutes les composantes
fortement connexes est également proposé.

24
 Recherche d’une composante
fortement connexe ( CFC)
L’idée de cet algorithme est de parcourir le graphe à partir du
point a dans le sens direct (en suivant les flèches des arcs) et de
créer un ensemble des nœuds parcourus. La même chose est
effectuée dans le sens indirect (en suivant les flèches des arcs en
sens inverse) et de créer un deuxième ensemble des sommets
parcourus.
Le premier ensemble S1 regroupe les nœuds accessibles à partir de
a et le deuxième ensemble S2 regroupe les nœuds qui peuvent
atteindre a.
L’intersection S` = S1 ∩ S2 est la CFC qui contient a.

25
 Algorithme de recherche d’une CFC
Entrées: G = (S, A) un graphe, a un sommet.
Sortie: S` un sous-ensemble de sommets.
Début
S1 ← {a} ;
pour tout s S faire visité(s) ← faux;
tant que Ǝ s S1 | non visité(s) faire
visité(s) ← vrai;
pour tout ar = (x, y) A | y S1 faire
S1 ← S1 U {y};
fin tant que;
S2 ← {a} ;
pour tout s S1 faire visité(s) ← faux;
tant que Ǝ s S2 | non visité(s) faire
visité(s) ←vrai;
pour tout ar = (y, x) A | y  S2 faire
S2 ← S2 U {y};
fin tant que;
S` ← S1 ∩ S2 ;
26
Fin
 Algorithme de recherche d’une CFC

Exemple:
Qans le graphe suivant, déterminer la composante fortement
Connexe contenant le sommet A.

27
 Recherche de toutes les
composante fortement connexe
Pour trouver toutes les composantes fortement connexes d’un
graphe, il suffit de choisir au hasard un nœud et de déterminer, grâce
à l’algorithme précédent, la composante fortement connexe qui le
contient.
On obtient alors une première composante fortement connexe S1.
Ensuite, parmi les nœuds qui ne font pas partie de S1, on en prend
un au hasard pour déterminer la composante fortement connexe qui le
contient.
On obtient alors une deuxième composante fortement connexe S2.
On recommence ainsi jusqu’à ce que tous les nœuds appartiennent
à une composante fortement connexe. 28
 Algorithme

Entrées: G = (S, A) un graphe.

Sortie: C = {C1,...,Cn} un ensemble de composantes connexes.
Début
S’ ← S;
i ← 1;
tant que S’ ≠ Ø faire
choisir s dans S’;
Ci ← ComposanteFortementConnexe(G, s);
S’ ← S’ - Ci;
i ← i + 1;
fin tant que;
Fin 29
 Algorithme de recherche d’une CFC

Exemple:
Qans le graphe suivant, déterminer toutes les composantes fortement
Connexes.

30