DEPARTEMENT D'INFORMATIQUE
Cours No 3 : Connexité d’un graphe
Sommaire
1- Fermeture transitive directe d’un sommet
2- Fermeture transitive inverse d’un sommet
3- Classe d’un sommet
4- Graphe fortement connexe
5- Graphe connexe
6- Graphe réduit
7- Point d’articulation
8- Propositions d’Euler
Rédigé par :
[Link]
Année Universitaire : 2020-2021
Chapitre 2 : Connexité d’un graphe
1. Fermeture transitive directe d’un sommet
Soit G= (X,U), un graphe donné, on appelle fermeture transitive directe d’un sommet x,
l’ensemble des sommets y liés à x par un chemin de longueur quelconque de x vers y. On
note :
x y X / ( x, y)
x, y est un chemin de longueur quelconque, autrement dit, c’est l’ensemble des
successeurs de degré quelconque :
x i x = {x} +1 {x} +2 {x} +3 {x} ... +i {x} ...
i 0
x .
Exemple
a
b
e
c
d
0 {a} = {a} + {a} = {b,c,d}
+2 {a} = +{b,c,d} = + {a} + {b}+{c}+{d}
= {b,c,d} {b,e ,f} {d,a} {e,f} = {b,c,d,e,f}
+3 {a} = +{b,c,d,e,f} = + {a} + {b} +{c} +{d}} +{e} +{f}
= {b,c,d,e,f}
a=
Donc, {a,b,c,d,e,f}
Ou bien directement
a= {a} {b,c,d} {f,e}
= {a,b,c,d,e,f}
Chapitre 2 : Connexité d’un graphe
2. Fermeture transitive inverse d’un sommet
On appelle fermeture transitive inverse d’un sommet x, l’ensemble des sommets y liés
à x par un chemin de longueur quelconque de y vers x. On note :
x y X / ( y, x)
y, x de longueur quelconque, autrement dit, c’est l’ensemble des successeurs de degré
quelconque :
x i x= {x} -1 {x} -2 {x} -3 {x} ... -i {x} ...
i 0
x .
Exemple
a = {a}
{a} = {a}, {a} = et donc
-0 -
e
= {e} - {e} -2 {e} -3{e}-4{e} …
= {e} {b,d} {a}
= {a,b,d,e}
3. Classe d’un sommet
Une classe de x, notée C(x), désigne l’ensemble des sommets y liés à x par des chemins
de x vers y et de y vers x, de longueur quelconque. C(x) est donc l’intersection entre la
fermeture transitive directe et inverse de x :
x x
C(x) =
Exemple
a
b
f
c d e
a a
C(a) = = {a,b,c,d,e,f} {a} = {a}
Remarque
x xest appelée une composante fortement connexe de x.
C(x) =
Chapitre 2 : Connexité d’un graphe
4. Graphe fortement connexe
Soit G= (X, U) un graphe orienté et soit R une relation définie par :
( x, y )et ( y, x)
x, y X, x R y
ou xy
R est appelée relation de forte connexité, c’est une relation d’équivalence (symétrique,
antisymétrique et transitive).
Définition
G est dit fortement connexe, si tous ses sommets ont deux à deux la relation de forte
connexité. Autrement dit, G est fortement connexe si et seulement si :
x X
x X
ou
x X
x X
Exemple
Graphe fortement connexe
B D
A
C E
Remarque
G n’est pas fortement connexe, si et seulement si :
x X
x X
ou
x X
x X
Exemple
Graphe non fortement connexe:
A A B C A, B, C X
Le graphe possède 3 classes :
A A = {A, B, C} ; D D = {D}
C1 C2
E E = {E}.
C3
Chapitre 2 : Connexité d’un graphe
5. Graphe connexe
Pour un graphe non orienté, la relation de connexité est définie par l’existence de chaînes
entre deux nœuds quelconques du graphe.
Soit G’= (X, U) un graphe non orienté et soit R’ une relation définie par :
x, y X, x R’ y
R’ est appelée relation de connexité, c’est une relation d’équivalence (symétrique,
antisymétrique et transitive).
Définition
G’ est dit connexe, si tous ses sommets ont deux à deux la relation de connexité.
Autrement dit G’ est connexe si et seulement si :
x X x X
Le graphe suivant n’est pas connexe.
A B
D E
C
Il est composé de deux composantes connexes : C1= {A, B, C} et C2 = {D, E}.
Remarque
Le nombre cyclomatique d’un graphe est le nombre de cycles linéairement
indépendant :
m-n+p
m le nombre d’arêtes, n le nombre de sommets et p le nombre de connexité.
6. Graphe réduit
On appelle graphe réduit d’un graphe G=(X, U), le graphe G' =(X’, U’) pour lequel
chaque nœud est associé à une composante fortement connexe de G. De plus, un arc relie un
nœud x' à un nœud y' dans le graphe G' si il existe un arc qui relie x à y dans G où x appartient
à la composante fortement connexe de G associée à x' et où y appartient à la composante
fortement connexe de G associée à y'.
G’= (X’, U’)/ X’= {Ci/ Ci est une composante fortement connexe de G}
U’={(x,y), x,y X’ / x Ci et y Cj /(x, y) U}
Chapitre 2 : Connexité d’un graphe
Exemple
Le graphe réduit du graphe :
C1
C2 C3
7. Point d’articulation
Un sommet x est dit point d’articulation de G si en le supprimant le nombre de connexité
de G augmente.
Exemple
A B
D E
C
‘B’ est un point d’articulation : en supprimant B,on obtient 3 composantes
fortement connexes : C 1 = {A}, C 2 = {C}, C 3 = {D, E}.
‘E’ n’est pas un point d’articulation : en supprimant ‘E’ du graphe, le nombre de
connexité ne change pas, bien que les composantes changent de sommet :
C 1 = {A, B, C} et C 2 = {D}
Remarque
Un isthme est une arête dont la suppression augmente le nombre de connexité.
8. Propositions d’Euler
- Un graphe connexe contient une chaîne eulérienne si et seulement si il possède 0 ou 2
sommets de degré impair.
- Un graphe connexe contient un cycle eulérien si et seulement si il ne possède aucun
sommet de degré impair (autrement dit tous ses sommets sont de degré pair).
Chapitre 2 : Connexité d’un graphe
Exemple
A A
G H F
C E
B D
C B D
A F L I
F
D C
B K J
B E C D
A E
G1 G2 G3 G4
Dans G1, il y a deux sommets de degré impair (A:1 et B:3). Le graphe contient une
chaîne eulérienne, par exemple (A, B, C, D, B) mais pas de cycle eulérien.
Dans G2 il y a deux sommets de degré impair (A:3 et E:3). Le graphe contient une
chaîne eulérienne, par exemple (A, F, D, B, F, E, D, C, B, A, E) mais pas de cycle
eulérien.
Dans G3, il y a 4 sommets de degré impair (A:3, B:3, D:3 et E:3). Le graphe ne
contient pas de chaîne eulérienne.
Dans G4, tous les sommets sont de degré pair. Le graphe contient un cycle eulérien,
par exemple: (G, A, H, F, I, C, J, D, K, B, L, E, G, H, I, J, K, L, G).