CONNEXITE

 

CHAINE-CHAINE ELEMENTAIRE, CHEMIN-CHEMIN ELEMENTAIRE

- Chaîne

Soit G =(X,U), x Î X et y Î X
Une chaîne joignant x et y est une séquence d'arêtes telle que :

-la première arête de la séquence est adjacente à x par une de ses extrémités et, à la deuxième arête de la séquence par son autre extrémité,
-la dernière arête de la séquence est adjacente à
y par une de ses extrémités et, à l'avant dernière arête par son autre extrémité.
- Chemin

Soit G = (X,U), x Î X et y Î X
Un chemin de
x à y dans G est une séquence d'arcs telle que : 

-l'extrémité initiale du premier arc de la séquence est x,
-l'extrémité initiale de chacun des autres arcs de la séquence coïncide avec l'extrémité terminale de l'arc précédent,
-l'extrémité terminale du dernier arc de la séquence est
y.
- Chemin élémentaire C'est un chemin tel qu'en le parcourant, on ne rencontre pas 2 fois le même sommet (dans le chemin tous les sommets sont au plus de degré 2).

- Circuit

C'est un chemin dont les extrémités coïncident.


CONNEXITE

Un graphe est dit connexe si pour tout couple de sommets i et j, il existe une chaîne joignant i et j.
i R j Û
   Soit i=j
    Soit il existe une chaîne joignant
i et j

Cette relation est une relation d'équivalence (R,S,T)
Les classes d'équivalence induites sur X par cette relation forment une partition de
X en X1, X2 , X3, ....,Xp.
Le nombre
p de classes d'équivalence distinctes est appelé le nombre de connexité du graphe.

Un graphe est dit connexe si et seulement si son nombre de connexité p vaut 1

Les sous graphes G1, G2, . Gp engendrés par les sous-ensembles X1, X2, ... Xp sont appelés les composantes connexes du graphe. La vérification de la connexité d'un graphe est un des premiers problèmes de la théorie des graphes.

 
 


 
 

(3 composantes connexes)
 

FORTE CONNEXITE Dans le cas d'un graphe orienté on ne parle plus de connexité mais de forte connexité  
 

(3 composantes fortement connexes)
 


RECHERCHE DES COMPOSANTES CONNEXES (fortement)

Pour qu'un graphe soit fortement connexe, il faut et il suffit qu'il existe un chemin entre x et y, pour tout x et tout y du graphe. Les composantes connexes forment des sous graphes remplissant cette condition. Il faut donc une méthode qui permette de voir si ces chemins existent. On utilise la FERMETURE TRANSITIVE. La fermeture transitive d'un sommet x, d'un graphe G = (X,T) est l'expression   G ' (x)={x} U G (x) U G ²(x) U G (n-1)(x) .

ou G '(k)(x)=G '[r(k-1)(x)]

G '(x) représente l'ensemble des sommets que l'on peut atteindre à partir du sommet x par des chemins ayant au plus k arcs.

On obtient la fermeture transitive de l'ensemble X des sommets du graphe en calculant la matrice Mn-1

G '(X) = I+A+ A² + +An - 1 = (I+A)(n-1)

G '(X)=Mn-1

où I est la matrice identité et A la matrice booléenne associée au graphe considéré

M=A+I

Dans l'expression de G '(X)  le + représente la somme booléenne, représente la puissance booléenne d'ordre 2 de A

Si G '(X) = l le graphe est fortement connexe ; en effet il existe entre chaque paire de sommets au moins un chemin.

Remarque:
(I + A) k est la matrice des chemins en au plus k arcs en considérant que, de x à x il existe un chemin de 0 arc.

Dans un graphe de n sommets il ne peut y avoir de chemin ayant plus de n-1 arcs sans répétition d'arcs, si bien que lorsque l'on recherche la fermeture transitive, (ou ensemble des successeurs de tous les sommets) il n'y a pas intérêt à dépasser la puissance (n-1) de (I + A). En pratique, on peut s'arrêter dès que

(I+A)k = (I+A)k-1


EXEMPLE: Rechercher les composantes connexes du graphe suivant
 
 


 
 

Matrice booléenne A associée au graphe


 

  A C D E F G
A 0 1 0 0 0 0 0
B 0 0 0 0 0 1 1
C 0 0 0 1 0 0 0
D 0 0 0 0 1 0 0
E 0 0 0 0 0 0 1
F 1 0 0 0 1 0 0
G 0 0 1 0 0 0 0

 

Le graphe comprend 7 sommets on calculera donc au plus M6

 

 

  A C D E F G
A 1 1 1 1 1 1 1
B 1 1 1 1 1 1 1
C 0 0 1 1 1 0 1
D 0 0 1 1 1 0 1
E 0 0 1 1 1 0 1
F 1 1 1 1 1 1 1
G 0 0 1 1 1 0 1

On constate qu'un nouvel arrangement des lignes et des colonnes permet de faire apparaître des matrices carrées, uniquement formées de 1 s'appuyant sur la diagonale principale.

A chacune de ces matrices correspond une composante fortement connexe du graphe : {A,B,F} et {C,D,E,G} sont les ensembles de sommets des 2 composantes connexes du graphe étudié.


  A F C D E G
A 1 1 1 1 1 1 1
B 1 1 1 1 1 1 1
F 1 1 1 1 1 1 1
C 0 0 0 1 1 1 1
D 0 0 0 1 1 1 1
E 0 0 0 1 1 1 1
G 0 0 0 1 1 1 1


  Si la matrice était uniquement composée de 1, le graphe serait fortement connexe.

Retour en haut de page