Définitions et algorithme simple

Celle-ci est une relation d'équivalence. Sa définition même entraîne la symétrie et la réflexivité. La transitivité résulte de ce que l'on peut concaténer un chemin entre et et un chemin entre et pour obtenir un chemin entre et . Les classes de cette relation d'équivalence sont appelées les composantes fortement connexes de . La composante fortement connexe contenant le sommet sera notée dans la suite.

  
Figure: Composantes fortement connexes du graphe de la figure 5.11

Le graphe de la figure comporte composantes fortement connexes, trois ne contiennent qu'un seul sommet, une est constituée d'un triangle et la dernière comporte sommets.

  Lorsque la relation n'a qu'une seule classe, le graphe est dit fortement connexe. Savoir si un graphe est fortement connexe est particulièrement important par exemple dans le choix de sens uniques pour les voies de circulation d'un quartier.

Un algorithme de recherche des composantes fortement connexes débute nécessairement par un parcours à partir d'un sommet , les sommets qui n'appartiennent pas à l'arborescence ainsi construite ne sont certainement pas dans la composante fortement connexe de mais la réciproque n'est pas vraie: un sommet qui est dans l'arborescence issue de n'est pas nécessairement dans sa composante fortement connexe car il se peut qu'il n'y ait pas de chemin allant de à .

Une manière simple de procéder pour le calcul de ces composantes consiste à itérer l'algorithme suivant pour chaque sommet dont la composante n'a pas encore été construite:

• Déterminer les sommets extrémités de chemins d'origine , par exemple en utilisant l'algorithme de Trémaux à partir de .

• Retenir parmi ceux ci les sommets qui sont l'origine d'un chemin d'extrémité . On peut, pour ce faire, construire le graphe opposé de obtenu en renversant le sens de tous les arcs de et appliquer l'algorithme de Trémaux sur ce graphe à partir de .

Cette manière de procéder est peu efficace lorsque le graphe possède de nombreuses composantes fortement connexes, car on peut être amené à parcourir tout le graphe autant de fois qu'il y a de composantes. Nous allons voir dans les sections suivantes, que la construction de l'arborescence de Trémaux issue de va permettre de calculer toutes les composantes connexes des sommets descendants de en un nombre d'opérations proportionnel au nombre d'arcs du graphe.