I.2.4. Connexité
Un graphe sera dit connexe si, pour
tout couple (x, y) de sommets, il existe une chaîne reliant deux de ses
sommets x et y.
a
d
e
f
c
b
u1
u2
u4
u5
u6
u3
Exemple 1.8 : Soit le graphe G
Figure 1.9 : Graphe non connexe
· Ce graphe n'est pas connexe car le sommet d est
isolé
Si un graphe n'est pas connexe, on
appellera composante connexe, chacun de ses
« morceaux » connexes.
Plus formellement :
On définit une relation entre les sommets de la
manière suivante :
x R y si et seulement si x=y ou x et y
sont reliés par une chaîne.
On démontre aisément que cette relation R
est réflexive, symétrique et transitive,
donc que c'est une relation d'équivalence.
Qui dit « relation d'équivalence »,
dit « classes d'équivalence ». On appellera ces
classes des composantes connexes.
Nota : Lorsqu'il s'agit d'un graphe
orienté, on parle de la forte connexité.
On notera en général : p, le nombre de
composantes connexes d'un graphe.
On peut s'intéresser au nombre de sommets à
supprimer pour « disconnecter » un graphe connexe (i.e.
faire qu'il ne soit plus connexe).
Remarque : Quand on enlève un sommet,
on supprime aussi tous les arcs dont ce sommet est extrémité.
Le nombre minimum de sommets pour ce faire sera
noté ê, on l'appellera
la connectivité du graphe.
On qualifiera d'ensemble d'articulation, un
ensemble de sommets dont la suppression disconnecte le graphe.
La connectivité est donc le cardinal minimal d'un
ensemble d'articulation.
Remarque :
Une connectivité égale à k signifie
qu'on peut trouver k sommets dont la suppression
disconnecte le graphe, cela ne veut pas dire que ce sera le cas avec k sommets
quelconques.
Exemple 1.9 :
Figure 1.11 : Graphe connexe
· Ce graphe est connexe.
· Quel que soit le sommet qu'on retire, il reste
connexe.
· Si on retire b et d, le graphe est toujours connexe.
· Si on retire c et d le graphe n'est plus connexe.
· Le Graphe est donc 2-connexe.
· {c,d} est un ensemble d'articulation du graphe.
Remarque : Si un graphe est 3-connexe,
il est 2-connexe.
Un point d'articulation est un
sommet dont la suppression disconnecte le graphe, c'est-à-dire un sommet
sont la suppression augmente la connexité du graphe.
Un isthme est une arête dont
la suppression disconnecte le graphe, c'est-à-dire une arête sont
la suppression augmente la connexité du graphe. On parle aussi de
pont en lieu et place d'isthme. Ainsi, les
extrémités d'un pont dont appelé pieds du
pont.
Exemple 1.10 :
Figure 1.11 : Graphe ayant deux points d'articulations
et un isthme
· Ce graphe est connexe ;
· Il possède deux points d'articulation ;
· L'arc central est un isthme (pont) ;
· Les deux points d'articulation sont les pieds du
pont ;
· Il n'y a aucun autre isthme.
Soit G=(X, U) un graphe. On dit que ce graphe est
k-sommet-connexe s'il reste encore connexe après avoir
en ôté (k-1) sommets.
Soit G=(X, U) un graphe. On dit que ce graphe est
k-arête-connexe s'il est possible de le
déconnecter (augmenter le nombre de connexité) en supprimant k
arêtes et tel que k est minimal.
N.B : Un graphe régulier de
degré r est au plus r-arête-connexe, r-sommet-connexe et
r-régulier. S'il est effectivement r-arête-connexe,
r-sommet-connexe, il est donc optimalement connecté.
| 
