Connexité forte et faible
Définition : Graphe symétrisé d'un graphe (rappel)
Le graphe symétrisé d'un graphe G est obtenu par l'union du graphe G et de son graphe inverse (obtenu en changeant le sens de tous ses arcs).
Définition : Chemin (rappel)
Un chemin est défini par une suite de points xo, x1, ..., xptelle que deux points qui se suivent sont toujours reliés par un arc ayant pour origine le premier point et pour extrémité le second.
Définition : Chaîne
Une chaîne est un chemin d'un graphe non orienté ou du graphe symétrisé d'un graphe orienté.
C'est une suite de points telle qu'entre deux points successifs xp et xp+1 il existe ou bien un arc de xp à xp+1 ou bien un arc de xp+1 à xP.
Définition : Graphe connexe
Un graphe G est connexe si pour tout couple de points différents x et y, il existe une chaîne entre x et y.
Remarque :
Un graphe est connexe s'il est en un seul morceau.
On ne peut pas trouver de représentation graphique de ce graphe en plusieurs parties où une partie du graphe serait par exemple à gauche et une autre partie du graphe par exemple à droite et il n'y aurait pas d'arcs ou d'arêtes entre la partie droite et la partie gauche.
C'est bien sûr le cas pour un graphe non connexe où on peut constituer des sous-représentations graphiques indépendantes les unes des autres.
Définition : Composantes connexes d'un graphe
Soit x~y la relation d'équivalence définie sur l'ensemble E des points d'un graphe par
x~y ⇔ il existe une chaîne d'extrémités x et y ou x=y.
Les classes de la relation d'équivalence ~ sont appelées les composantes connexes du graphe.
Remarque :
Une composante connexe d'un graphe est un sous-graphe connexe maximal (au sens de l'inclusion des points) contenant un point x donné.
On peut désigner une composante connexe par un de ses points (n'importe lequel).
Remarque :
Un graphe connexe ne comporte qu'une seule composante connexe alors qu'un graphe non connexe comporte au minimum deux composantes connexes.
On peut dessiner les représentations graphiques de chaque compossante connexe d'un graphe sur des pages différentes puisqu'il n'y a pas d'arêtes entre deux composantes connexes d'un graphe donné.
Définition : Graphe fortement connexe
Un graphe G est fortement connexe si pour tout couple de points x et y, il existe un chemin de x à y ou x=y.
Remarque :
Un graphe fortement connexe est connexe.
Un graphe connexe et symétrique est fortement connexe.
Dans un graphe fortement connexe de plus d'un point, il existe un circuit non réduit à une boucle passant par tout point x (puisque quelque soit x et y il existe un chemin de x à y et un chemin de y à x).
Définition : Composantes fortement connexes d'un graphe
Soit x≈y la relation d'équivalence définie sur l'ensemble E des points d'un graphe par
x≈y ⇔ il existe un chemin de x à y et un chemin de y à x ou x=y.
Les classes de la relation d'équivalence ≈ sont appelées les composantes fortement connexes du graphe.
On peut désigner une composante fortement connexe par un de ses points (n'importe lequel).
Cliquez sur les flèches précédent et suivant pour choisir des graphes (petits ou gros).
Les composantes connexes d'un même graphe sont données pour trois points choisis arbitrairement (parfois on obtient deux fois la même composante connexe et parfois des composantes connexes différentes).
Recherche des composantes fortement connexes
Il existe plusieurs algorithmes de recherche des composantes fortement connexe d'un garphe
Nous en présentons ici deux :
- l'un utilise la recherche des ascendants et des descendants d'un graphe (ces algorithmes sont présentés dans le chapitre "chemins et cheminement") ;
- l'autre utilise la fermeture transitive du graphe (un algorithme de construction de la fermeture transitive est présentée dans le chapitre "propriétés liées aux relations binaires").
Algorithme de recherche d'une composante fortement connexe d'un graphe en utilisant les ascendants et les descendants
Soit xo le point dont on cherche la composante fortement connexe.
On utilise un algorithme de recherche des descendants de xoet on marque par le signe "+" les descendants trouvés (on les met en couleur jaune dans l'animation qui suit).
On utilise un algorithme de recherche d'ascendants de xo (ou de descendants dans le graphe inverse) et on marque par le signe "- " les ascendants trouvés (on entoure en rouge les points dans l'animation qui suit).
Le point xo ainsi que tous les points marqués simultanément "+" et "-" font partie de la composante fortement connexe de xo (on a ajouté un fond vert de forme carré sous les points pour les mettre en valeur dans l'animation qui suit).
Cliquez sur Anim pour démarrer l'animation. Utilisez les flèches précédent et suivant pour sélectionner un graphe. Changer éventuellement le numéro du point dont on cherche la composante connexe et appuyer sur valider pour partir effectivement de ce point (en cas d'erreur le point 1 est pris par défaut). Les trois boutons de gauche permettent d'obtenir successivement les trois phases de l'algorithme :
- recherche des descendants
- recherche des ascendants
- mise en évidence de la composante fortement connexe du point choisi.
Algorithme de recherche de la composante fortement connexe d'un point en utilisant la fermeture transitive
Initialisation
On utilise un algorithme qui fournit la matrice en variables 0-1 du graphe, soit FT cette matrice.
On considère un point quelconque x.
Les points de la composante fortement connexe de x sont donnés par tous les points j tels que FT(i,x)=1 et FT(x,j)=1.
Cliquez sur Anim pour démarrer l'animation.
Utilisez les flèches précédent et suivant pour sélectionner un graphe.
Utilisez la case numérique et le bouton Valider pour changer le point x ou pour réinitialiser l'algorithme.
Utilisez le bouton FT pour afficher la matrice de la fermeture transitive (qui n'a besoin d'être calculée qu'une seule fois).
Puis utilisez le bouton CFC-m pour mettre en violet sur la matrice les cases intéressantes de la matrice correspondant à la composante fortement connexe (s'il n'y a aucune case violette sauf le numéro de ligne et de colonne, c'est que le point est seul dans sa composante fortement connexe).
Enfin utilisez le bouton CFC-g pour faire apparaître la composante fortement connexe sur la représentation graphique.
Définition : Graphe réduit
On note Xr l'ensemble quotient X/≈ où chaque composante fortement connexe différente est représenté par un élément dans cet ensemble.
On définit l'ensemble Er d'arcs entre les points de Xr de la façon suivante :
∀(c,c')∈ Xrx Xr : (c,c')∈Er⇔ c=c' ou ∃x∈c et ∃x'∈c' tel que (x,x')∈E.
Le graphe (Xr,Er) est appelé le graphe réduit du graphe (X,E).
Le graphe réduit d'un graphe G a donc autant de points que de composantes fortement connexe dans le graphe G.
Il y a un arc entre un point représentant une composante fortement connexe et un autre point représentant une autre composante si et seulement si il existe au moins un arc entre un point de la première composante fortement connexe et un point de la deuxième composante fortement connexe.
Remarque :
Le graphe réduit ne contient pas de circuits, mais peut contenir des cycles
Le graphe réduit d'un graphe fortement connexe ne contient qu'un seul point.
Cliquez sur les flèches précédent et suivant pour choisir des graphes (petits ou gros).
A gauche, le graphe initial.
Au milieu les composantes fortement connexes sont coloriées avec une couleur différente pour chaque composante fortement connexe.
En outre les arcs qui vont d'une composante fortement connexe à une autre composante fortement connexe sont coloriés en rouge.
A droite, le graphe réduit avec un seul point par composante fortement connexe (en conservant les mêmes couleurs que pour la figure du milieu) et un seul arc pour les liens éventuels entre les composantes fortement connexes.
