Découverte et exploration des graphes : partie 2¶

Rappel du problème fil rouge et règles du jeu¶

Fil rouge¶

Dans la première partie de ce cours nous avons vu comment l’on peut modéliser les pistes cyclables parisiennes avec un graphe. Dans cette deuxième partie, nous verrons comment explorer efficacement ces pistes cyclables pour découvrir la partie du plan parisien qui est atteignable depuis un point de départ donné. En d’autres termes, nous allons répondre à la question initiale :

Où puis-je aller à vélo depuis chez moi en empruntant des pistes cyclables ?

A cause des pistes cyclables en sens unique, il est fort possible qu’il existe des endroits de Paris que l’on peut attendre sans pouvoir ensuite rentrer chez soi. Il nous intéressera alors d’étudier un second problème :

Où puis-je aller et rentrer à vélo depuis chez moi ?

En termes de graphes, cela nous conduira à nous intéresser aux 3 notions fondamentales suivantes :

parcours de graphes et chemins ;

composante connexe ; et

composante fortement connexe.

Nous étudierons également des algorithmes efficaces pour extraire ces objets à partir d’un graphe donné et d’un sommet de départ. Bien que nous nous appuyons dans ce cours sur l’exemple particulier des pistes cyclables, la portée applicative de ces notions est bien plus vaste puisqu’elles sont nécessaires dans une grande partie des problèmes que l’on peut résoudre avec des graphes (comme par exemple ceux que nous verrons dans la suite de ce cours : partitionnement de données, plus courts chemins, réseaux de poids optimaux).

Organisation du cours¶

Toutes les sections dont le titre est étiqueté “Exo” font référence à des exercices relevant du problème fil rouge. Vous devez répondre à ces questions par groupe de 4 étudiants et consigner vos réponses dans un rapport. Vous devez conserver le même groupe que pour la première partie du cours. Vous devez

reprendre le document google créé précédemment ;

le partager avec les autres membres du groupe ; et

le partager dès le début de la séance avec l’enseignant.

Pour les questions qui demandent du code, il vous sera demandé de copier le code que vous avez produit dans votre rapport. Pour ce type de question, on ne vous demandera pas d’écrire l’intégralité d’un programme par vous même mais de compléter une bibliothèque de graphes écrite en C. Ainsi, vous ne devriez jamais avoir à produire plus d’une vingtaine de lignes de code par question.

Le rapport produit sera utilisé pour votre évaluation dans le cours “Graphes et algorithmes”.

En général, chaque section étiquetée “Exo” est suivie d’une section étiquetée “Cours” qui présente les notions nécessaires pour répondre aux questions posées en fil rouge.

A l’intérieur des sections de cours, vous trouverez également des petits quiz qui ont pour objectif de tester votre compréhension du cours. Pour vérifier ses réponses, il suffit de cliquer sur le bouton corriger situé à la fin de l’exercice.

Ce cours n’est pas un mooc ! Un enseignant est à présent pour vous aider : solliciter le au moindre doute ou pour vérifier vos réponses. L’enseignant pourra également inscrire des remarques directement dans votre rapport. Prenez ces remarques en compte pour améliorer vos réponses.

Un exemple “jouet” : rappel¶

Soient les pistes cyclables suivantes repérées grâce à leurs extrémités dans un système de coordonnées cartésiennes:

sens unique de (3;6) vers (6;3)

sens unique de (6;3) vers (9;7)

double sens entre (6;3) et (10;1)

sens unique de (6;9) vers (3;6)

sens unique de (9;7) vers (6;9)

sens unique de (10;1) vers (13;6)

double sens de (12;9) et (16;9)

sens unique de (12;13) vers (12;9)

sens unique de (13;6) vers (16;4)

sens unique de (16:9) vers (16;13)

Exo - Exploration des successeurs : algorithme de dilatation¶

Dans le graphe \(G = (S,A)\) qui modélise les pistes cyclables de l’exemple jouet, considérez comme point de départ le sommet \(x\) associé à la position \((3;6)\) et donnez

la dilatation \(E_1 = \delta(G,\{x\})\) de l’ensemble \(\{x\}\)
la dilatation \(E_2 = \delta(G,E_1)\) de \(E_1\)
la dilatation \(E_3 = \delta(G,E_2)\) de \(E_2\)

Dans l’exemple précédent, si l’on poursuit les étapes de dilatation (c’est-à-dire si l’on considère la suite \(E_0, E_1, \ldots\) où \(E_i = \delta(G,E_{i-1})\) et \(E_0 = \{x\}\)), à partir de quelle étape ne découvre-t-on plus de sommet inexploré ?

Complétez l’algorithme en pseudo-code ci-dessous pour calculer la dilatation d’un sous-ensemble de sommets d’un graphe.

Algorithme Dilatation

Données : le nombre \(n\) de sommets du graphe \(G\), l’application successeur \(\Gamma\) du graphe \(G\) et un sous-ensemble \(E\) de sommets du graphe

Résultat : la dilatation \(D\) de \(E\) dans \(G\)

\(D := \emptyset\)

Pour chaque \(x\) de \(0\) à \(n-1\) Faire

Si \(x\) appartient à \(E\) Alors

Compléter ici !!

En supposant que le graphe \(G\) est représenté en mémoire par un tableau de listes chaînées, évaluez la complexité de l’algorithme dans les deux cas suivants :

chacun des ensembles \(D\) et \(E\) est représenté en mémoire par une liste chaînée ; et

chacun des ensembles \(D\) et \(E\) est représentés en mémoire par un tableau booléens.

Dans chaque cas de figure, vous évaluerez la complexité de chaque ligne de l’algorithme avant d’évaluer la complexité globale.

Complétez maintenant l’implémentation suivante de l’algorithme Dilatation.

#include "graphes.h"

/* ci-dessous trois macros pour pouvoir utiliser les termes, booleens, VRAI et FAUX dans les programmes */
#define booleen unsigned char
#define VRAI 1
#define FAUX 0

/***************************************************************************/
/* retourne le dilate D de l'ensemble E dans le graphe G                   */
/* les ensembles E et D sont représentés par des tableaux booleens         */
/* - la mémoire pour E est supposée allouée avec autant de case            */
/*   que de sommets dans G                                                 */
/* - la mémoire pour D est allouée a l'intérieur de la fonction            */
/***************************************************************************/
booleen * dilatation(graphe* G, booleen *E){
    booleen *D; /* tableau boolen pour stocker le résultat de la dilatation */
    int x; /* pour parcourir les sommets de G */
    pcell p; /* pointeur vers maillon pour parcourir des listes de successeurs */

    /* comme D est un sous ensemble des sommets de G on a besoin
    d'autant de cases que de sommets de G */
    D = (booleen *) calloc(G->nsom, sizeof(booleen));

    /* A completer ici, peut se faire en 4 lignes, en tout cas en au plus 7 :-) */

    return D;
}

Afin de tester votre implémentation de l’algorithme de dilatation :

téléchargez le fichier exploration_dilatation.c et sauvegarder le dans votre répertoire de travail

insérez votre code de dilatation dans ce fichier à l’endroit prévu pour cela

compilez le programme (gcc exploration_dilatation.c graphes.c -o exploration_dilatation ou mieux en utilisant l’utilitaire make)

testez avec plusieurs graphes (par exemple amitie.graphe, votre graphe exemple jouet et pistes.petit.graphe 1 ) ;

vérifiez que les résultats sont conformes à ce qui est attendu ; et

copiez les traces d’exécution de vos programmes dans votre rapport.

Notes

1(1,2,3)

Bonus : Obtenir une visualisation des graphes ! Pour cela

télécharger le fichier source de graphe2ps et le sauver dans votre répertoire
le compiler, par exemple, avec la commande gcc graphe2ps.c graphes.c -o graphe2ps
Ce programme permet de convertir un graphe sous forme d’un fichier .graphe en une illustration graphique au format .eps que l’on peut visualiser par exemple avec un visualiseur de pdf comme evince.

En exécutant le programme d’exploration de graphes par dilatation (à la main ou sur une machine), on peut se convaincre qu’à l’étape \(k\) de l’algorithme, les sommets explorés sont ceux qui peuvent être atteints en “empruntant” \(k\) sections de piste cyclable (c’est-à-dire, \(k\) arcs) depuis le point de départ.

Indiquez (en langage naturel) une méthode pour obtenir l’ensemble des sommets du graphe depuis lesquels on peut atteindre un sommet de départ en empruntant \(k\) arcs (aide : vous pouvez combiner plusieurs algorithmes vus jusqu’à présent).

Cours - Exploration des successeurs : dilatation¶

Intuitivement, dans un graphe, pour explorer tous les sommets atteignables depuis un sommet initial donné, on peut procéder de proche en proche en considérant les successeurs du sommet initial, puis les successeurs des successeurs, les successeurs de ces successeurs, etc. Dans une telle procédure, l’opération élémentaire consiste à explorer les successeurs d’un sous-ensemble de sommets. Cette opération s’appelle la dilatation.

Définition: Graphe

Soit un graphe \(G = (S,A)\) et soit un sous ensemble \(E\) de sommets de \(G\). La dilation de \(E\) dans \(G = (S,A)\), désignée par \(\delta(G,E)\), est l’union des ensembles de successeurs des éléments de \(E\) :

\(\delta(G,E) = \cup \{ \Gamma_G(x), x \in E \}\).

Exemple

Soit le graphe \(G\) dessiné ci-dessous.

La dilatation de l’ensemble \(E = \{0, 3, 7\}\) dans \(G\) est l’ensemble \(\delta(G,E) = \{1, 5, 4, 8\}\) car \(\Gamma_G(0) = \{1\}\), \(\Gamma_G(3) = \{5,4\}\), \(\Gamma_G(7) = \{8\}\) et \(\{1\} \cup \{5,4\} \cup \{8\} = \{1, 5, 4, 8\}\).

Nous pouvons observer qu’un sommet \(x\) de \(G\) appartient à la dilatation de \(E\) si et seulement si l’un des prédécesseurs de \(x\) appartient à \(E\). Autrement dit, on peut facilement prouver que l’affirmation suivante est vraie :

\(\delta(G,E) = \{ x \in S \text{ tel que } \exists (y,x) \in A \text{ où } y \in E \}\).

Exo - Chemin¶

Dans le graphe \(G\) qui modélise les données du problème “exemple jouet”, donnez

un chemin élémentaire de longueur 4 ;
un circuit non trivial qui est un chemin élémentaire ;
une chaine non-triviale qui n’est pas un chemin ;
la longueur d’un plus long chemin élémentaire ;
un cycle qui n’est pas un circuit ;
un circuit qui n’est pas un chemin élémentaire ;
l’ensemble des sommets du graphe que l’on peut atteindre par un chemin depuis le sommet à la position \((12; 9)\) ;
l’ensemble des sommets depuis lesquels il existe un chemin vers le sommet de position \((12; 9)\)
l’ensemble composé de chaque sommet qui peut à la fois
- être atteint par un chemin depuis la position \((12; 9)\) et
- depuis lequel on peut revenir à la position \((12 ; 9)\) par un chemin ;
même travail qu’à l’item précédent pour la position \((6;9)\) puis pour la position \((13;6)\).

Cours - Chemin¶

Afin d’étudier précisément l’exploration de graphes, nous consacrons cette section à la notion de chemin. Cette notion joue un rôle important dans l’exploration de graphe. En effet, dans un graphe, un sommet peut être “exploré” depuis un autre s’il existe un chemin allant du second vers le premier.

Intuitivement, dans un graphe, un chemin est une suite ordonnée de sommets dans laquelle chaque élément est relié par un arc à celui qui le précède et à celui qui le suit

Définition: Chemin

Soit \(G = (S, A)\) un graphe, et soient \(x\) et \(y\) deux sommets dans \(S\).

Un chemin de \(x\) à \(y\) (dans \(G\)) est une séquence ordonnée \(\pi = (x_0, \ldots, x_\ell)\) de sommets de E telle que

pour tout \(i\) dans \(\{1, \ldots, \ell \}\), \(x_i\) est un successeur de \(x_{i-1}\) dans \(G\) ; et

\(x_0 = x\) et \(x_\ell = y\)

Si \(\pi = (x_0, \ldots, x_\ell)\) est un chemin, on dit que \(\ell\) est sa longueur.

Exemple

Dans le graphe \(G\) dessiné ci-dessous, \(\pi = (0,2,1)\) est un chemin de longueur 2.

Certains chemins possèdent des caractéristiques remarquables et on leur donne alors un nom particulier.

Définition: Chemins remarquables

Soit \(G\) un graphe.

Un chemin de longueur nulle est appelé un chemin trivial.
Un chemin \(\pi = (x_0, \ldots, x_\ell)\) non-trivial est un circuit si son premier et son dernier sommet sont égaux, c’est-à-dire, si l’on a \(x_0 = x_\ell\).
Un chemin \(\pi = (x_0, \ldots, x_\ell)\) est élémentaire si tous ses sommets sont deux-à-deux distincts sauf éventuellement \(x_0\) et \(x_\ell\), c’est à dire, si pour tous \(i\) et \(j\) dans \(\{0, \ldots, \ell\}\) avec \(i \neq j\), on a \(x_i \neq x_j\) ou \(\{i,j\} = \{0,\ell\}\).

Exemple

Dans le graphe \(G\) dessiné ci-dessous,

\((3)\) est un chemin trivial ;

\((0,2,1,0)\) est un circuit ;

le circuit \((0,2,1,0)\) est élémentaire ; et

\((0,1,0,2,1,0)\) est un circuit non-élémentaire.

D’après la définition d’un chemin élémentaire, nous déduisons la propriété suivante. Intuitivement, cette propriété nous permet d’affirmer que tout sommet atteignable depuis un sommet initial donné peut également l’être grâce à un chemin élémentaire de longueur inférieure au nombre total de sommets dans le graphe. Nous utiliserons cette propriété dans une section ultérieure afin de montrer qu’un algorithme d’exploration de graphe est correcte et efficace :

il produit bien l’ensemble de tous les sommets qui peuvent être atteint depuis le sommet initial sans en manquer un seul ; et

il produit ce résultat en un nombre borné d’étapes.

Propriété

Tout chemin \(\pi\) de \(x\) à \(y\) contient un chemin élémentaire de \(x\) à \(y\).

La longueur d’un circuit élémentaire dans \(G\) est au plus \(n\), \(n\) étant le nombre de sommets de \(G\).

La longueur d’un chemin élémentaire qui n’est pas un circuit est au plus \(n-1\).

Comme nous l’avons vu avec l’exemple des cyclistes rebelles (ceux qui s’autorisent à emprunter les sens uniques), il est parfois intéressant de ne pas considérer l’orientation des arcs d’un graphes. Dans, ce cas, il est pertinent de considérer les notions de chaine et de cycle au lieu de celle de chemin et circuit.

Définition: Chaine et circuit

Soient \(G\) un graphe et \(G_s\) la fermeture symétrique de \(G\) 2

Tout chemin dans \(G_s\) est appelé une chaine dans \(G\).

Tout circuit élémentaire dans \(G_s\) comportant au moins 3 sommets est appelé un cycle dans \(G\).

Notes

2: Voir section Cours - Symétrique et graphes pour un rappel la définition de fermeture symétrique

Considérez le graphe \(G\) dessiné ci-dessous et remplissez le tableau suivant. Dans chaque case, indiquez vrai si vous pensez que la séquence donnée en début de ligne satisfait la définition donnée en haut de la colonne.

	est un chemin	est une chaîne	est un circuit	est un cycle
\((0,2,0)\)
\((0,2,1,0,2,3)\)
\((3,2,0)\)
\((0,2,1,2,0)\)
\((2,0,1,2)\)
\((0,2,1,0)\)

Exo - Exploration partielle¶

Dans le graphe de l’exemple jouet, pour chaque valeur de \(k\) entre 0 et 6, donnez l’exploration partielle de rang \(k\) depuis le sommet à la position \((6;9)\)
Dans un fichier ‘’explorationPartielle.c’’, implémentez une fonction pour réaliser l’exploration partielle d’un graphe (indication : vous pouvez copier une partie du programme main d exploration_dilatation.c donné à l’exercice précédent).
Compilez et testez votre programme sur de petits graphes.
En utilisant votre programme, donnez la liste de tous les sommets qui peuvent être atteints par un chemin de longueur 5 (c’est à dire en empruntant 5 sections de pistes cyclables)
- dans le graphe partiel des pistes cyclables, depuis le sommet 135 (Rue Martel) ; et
- dans le graphe complet des pistes depuis le sommet 1072 (AVENUE DES CHAMPS ELYSEES).

Cours - Exploration partielle d’un graphe¶

Dans cette section nous allons voir qu’étant donné un sommet initial dans un graphe et une longueur \(\ell\) donnée, il est possible d’obtenir l’ensemble des sommets atteignables depuis ce sommet par un chemin de longueur \(\ell\) en itérant \(\ell\) fois l’algorithme de dilatation étudié à la section précédente. Nous verrons ensuite qu’il est possible d’obtenir tous les sommets atteignables depuis le sommet initial en itérant un nombre suffisant (mais borné) de fois l’algorithme de dilatation. Cet algorithme est en temps quadratique. Nous verrons dans une section suivante comment l’améliorer pour obtenir un algorithme en temps linéaire en fonction de la taille du graphe pour explorer tous les sommets atteignables depuis un sommet de départ.

Intuitivement, l’exploration d’ordre \(k\) depuis un sommet de départ donné est l’ensemble des sommets que l’on peut atteindre depuis ce sommet en itérant \(k\) dilatations à partir de l’ensemble comprenant uniquement le sommet de départ.

Définition: Exploration partielle :class: definition

Soient \(G\) un graphe, \(x\) un sommet de \(G\) et \(k\) un entier positif. L’exploration (partielle) d’ordre \(k\) (de \(G\) ) depuis \(x\) est le sous-ensemble des sommets de \(G\) désigné par \(\Gamma_G^k(x)\) et défini par :

\(\Gamma_G^k(x) = \{x\}\), si \(k = 0\) ; et

\(\Gamma_G^k(x) = \delta(G,\Gamma_G^{k-1}(x))\), si \(k > 0\).

Nous pouvons ainsi observer que:

\(\Gamma_G^0(x) = \{x\}\) ;

\(\Gamma_G^1(x) = \delta(G,\Gamma_G^0(x)) = \delta(G,\{x\}) = \Gamma_G(x)\) ;

\(\Gamma_G^2(x) = \delta(G,\Gamma^1(x)) = \delta(G,\delta(G,\{x\}))\) ;

\(\Gamma_G^3(x) = \delta(G,\Gamma^2(x)) = \delta(G,\delta(G,\delta(G,{x})))\) ;

…

Plus généralement, \(\Gamma_G^k(x) = \delta(G,\Gamma^{k-1}(x)) = \delta(G,\delta(G,...(\delta(G,\{x\})...))\), où la dilatation est appliquée \(k\) fois.

Exemple [mettre a jour avec quiz]

Soit le graphe \(G\) dessiné ci-dessous.

Nous observons que:

\(\Gamma_G^0(0) = \{0\}\) ;

\(\Gamma_G^1(0) = \{1\}\) ;

\(\Gamma_G^2(0) = \{2,6\}\) ;

\(\Gamma_G^3(0) = \{0,5\}\) ;

\(\Gamma_G^4(0) = \{1,4\}\) ;

\(\Gamma_G^5(0) = \{3, 6, 2\}\) ;

\(\Gamma_G^6(0) = \{4, 5, 0\}\).

Nous pouvons maintenant énoncer la propriété suivante qui établit le lien formel entre exploration d’ordre \(k\) et chemin de longueur \(\ell = k\).

Propriété

Il existe un chemin de longueur \(\ell\) de \(x\) à \(y\) si et seulement si \(y\) appartient à l’exploration d’ordre \(k = \ell\) depuis \(x\)

Preuve (pour les curieux).

Procédons par induction pour démontrer cette propriété.
1. [Initialisation de la récurrence] Démontrons la propriété pour \(\ell = 0\). Il existe un chemin de longueur \(\ell = 0\) de \(x\) à \(y\) si et seulement si \(y = x\) car le seul chemin depuis \(x\) de longueur \(0\) est le chemin trivial \((x)\). Comme l’exploration \(\Gamma_G^0(x)\) d’ordre 0 depuis \(x\) est l’ensemble \(\{x\}\) (cf premier item de la définition ci-dessus), nous déduisons que la propriété est vraie lorsque \(\ell = 0\).
2. [Hypothèse de récurrence] Supposons désormais que \(\ell\) est strictement positif et que la propriété est vraie au rang \(\ell -1\), c’est-à dire que l’affirmation suivante est vraie :
  il existe un chemin de longueur \(\ell-1\) de \(x\) à \(y\) si et seulement si \(y\) appartient à l’exploration d’ ordre \(\ell - 1\) depuis \(x\)
3. [Hérédité] Nous allons maintenant montrer que, sous cette hypothèse, la propriété est également vraie au rang \(\ell\), ce qui complétera la preuve par récurrence. Nous allons commencer par montrer l’implication directe avant de montrer l’implication réciproque :
  Si \((x = x_0, \ldots, x_\ell=y)\) est un chemin de longueur \(\ell\) de \(x\) à \(y\), alors, d’après la définition d’un chemin, nous pouvons affirmer que
  
  \(\pi' = (x_0, \ldots, x_{\ell - 1})\) est un chemin de longueur \(\ell -1\) de \(x\) à \(x_{\ell-1}\) et que
  
  \(y\) est un successeur de \(x_{\ell-1}\).
  
  Par hypothèse de récurrence, nous déduisons de (a) que \(x_{\ell-1}\) appartient à l’exploration \(\Gamma_G^{\ell-1}(x)\) d’ordre \(\ell-1\) depuis \(x\). Donc, d’après (b), par définition de \(\Gamma_G^{\ell}(x)\) (cf second point de la définition ci-dessus), nous déduisons que le sommet \(y\) appartient à l’exploration \(\Gamma_G^{\ell}(x)\) d’ordre \(\ell\) depuis \(x\), ce qui complète la preuve de l’implication directe.
  
  Si \(y\) appartient à l’exploration \(\Gamma_G^{\ell}(x)\) d’ordre \(k = \ell\) depuis \(x\), alors, d’après la définition de \(\Gamma_G^{\ell}(x)\) (cf second point de la définition ci-dessus), nous affirmons qu’il existe un élément \(z\) dans \(\Gamma_G^{\ell-1}(x)\) tel que \(y\) est un successeur de \(z\). Ainsi, d’après l’hypothèse de récurrence, il existe un chemin \((x_0, \ldots, x_{\ell -1} = z)\) de longueur \(\ell-1\) de \(x\) à \(z\). Donc, comme \(y\) est un successeur de \(z\), \((x_0, \ldots, x_{\ell -1}=z, x_{\ell} = y)\) est un chemin de longueur \(\ell\) de \(x\) à \(y\), ce qui complète la preuve de l’implication réciproque.
CQFD.

Exo - Exploration de graphe¶

Dans le graphe \(G\) de l’exemple jouet, donnez l’exploration du graphe
- depuis le sommet \(x_1\) à la position \((6; 3)\) ;
- depuis le sommet \(x_2\) à la position \((13; 6)\) ; et
- depuis le sommet \(x_3\) à la position \((12,13)\).
En d’autre terme, donnez \(\mbox{Expl}(G,x_1), \mbox{Expl}(G,x_1)\), et \(\mbox{Expl}(G,x_3)\).

Cours - Exploration d’un graphe¶

Dans cette section, nous définissons formellement ce qu’est l’exploration (complète) d’un graphe à partir de l’un de ses sommets et nous présentons une propriété essentielle pour concevoir un algorithme de calcul de l’exploration d’un graphe. Grâce à cette propriété, dans la section suivante, nous concevrons un algorithme d’exploration, nous démontrerons que cet algorithme est correct (c’est-à-dire qu’il produit toujours le bon résultat) et nous justifierons sa complexité de calcul. Nous verrons ensuite comment améliorer cet algorithme pour atteindre une complexité optimale (linéaire en fonction de la taille du graphe d’entrée).

Définition: Exploration

Soient \(G = (S,A)\) un graphe et \(x\) un sommet de \(G\). L’exploration (de \(G\)) depuis \(x\), désignée par \(\mbox{Expl}(G,x)\), est le sous-ensemble des sommets de \(G\) qui peuvent être atteints par un chemin depuis \(x\) :

\begin{eqnarray} \mbox{Expl}(G,x) = \{ y \in S \text{ tel qu'il existe un chemin de } x \text{ à } y \} . \end{eqnarray}

Exemple [mettre a jour avec quiz]

Soit le graphe \(G\) dessiné ci-dessous.

Nous observons que:

\(\mbox{Expl}(G,0) = \{0,1,2,6,5,4,3\}\) ;

\(\mbox{Expl}(G,6) = \{6,5,4,3\}\) ;

\(\mbox{Expl}(G,10) = \{10\}\) ;

\(\mbox{Expl}(G,7) = \{7,8,9\}\).

La propriété suivante caractérise l’exploration d’un graphe en fonction de ses explorations partielles. Elle conduit ainsi naturellement à un premier algorithme pour calculer l’exploration d’un graphe. Cet algorithme est présenté dans la section de cours suivante.

Propriété

Soient \(G\) un graphe à \(n\) sommets et \(x\) un sommet de \(G\). L’exploration de \(G\) depuis \(x\) est l’union des explorations partielles depuis \(x\) pour tous les rangs de \(0\) à \(n-1\) :

\begin{eqnarray} \mbox{Expl}(G,x) = \bigcup_{k \in \{0, \ldots, n-1\}} \Gamma^k_G(x). \end{eqnarray}

Preuve (pour les curieux).

Soit \(y\) un sommet de \(G\). Pour établir la propriété, nous allons montrer que \(y\) appartient à \(\mbox{Expl}(G,x)\) si et seulement si \(y\) appartient à \(\bigcup_{k \in \{0, \ldots, n-1\}} \Gamma^k_G(x)\). D’après la propriété de la section sur les chemins , il existe un chemin de \(x\) à \(y\) si et seulement si il existe un chemin élémentaire de \(x\) à \(y\). Or, d’ après cette propriété, nous savons également que la longueur d’un chemin élémentaire est strictement inférieure à \(n\). Nous pouvons donc affirmer qu’il existe un chemin de \(x\) à \(y\) si et seulement il existe, de \(x\) à \(y\), un chemin de longueur strictement inférieur à \(n\). Ainsi, d’après la propriété énoncée dans la section sur l’exploration partielle de graphe, nous déduisons qu’il existe un chemin de \(x\) à \(y\) si et seulement si \(y\) appartient à une exploration partielle depuis \(x\) d’ordre strictement inférieur à \(k\), c’est-à-dire, si et seulement si \(y\) appartient à \(\bigcup_{k \in \{0, \ldots, n-1\}} \Gamma^k_G(x)\). CQFD

Exo - Programmer des algorithmes d’exploration de graphes¶

Algorithme Exploration Naïf.
1. Implémentez cet algorithme en complétant le code de la fonction ‘’explorationNaif’’ dans le fichier source explorationNaif.c
2. Compilez votre programme (gcc explorationNaif.c graphes.c -o exploration ou mieux en utilisant l’utilitaire make)
3. Testez votre programme avec plusieurs graphes amitie.graphe, votre graphe exemple jouet et pistes.petit.graphe 1 )
4. Vérifiez que les résultats sont corrects
5. Reportez les temps de calcul pour l’exploration du graphe complet des pistes depuis le sommet 1072 (AVENUE DES CHAMPS ELYSEES).
Algorithmes Exploration Largeur
1. Implémentez cet algorithme en complétant le code de la fonction ‘’explorationLargeur’’ dans le fichier source explorationLargeur.c
  Conseil : utiliser la structure de liste qui a été implémentée pour vous. Cette structure doit être manipulée exclusivement via les 5 fonctions fournies : ‘’initListFIFO’’, ‘’termineListFIFO’’, ‘’selectionSuppressionListeFIFO’’, ‘’insertionListeFIFO’’ et ‘’estNonVideListeFIFO’’.
2. Compilez votre programme (gcc exploration.c graphes.c -o exploration ou mieux en utilisant l’utilitaire make)
3. Testez votre programme avec plusieurs graphes amitie.graphe, votre graphe exemple jouet et pistes.petit.graphe 1 )
4. Vérifiez que les résultats sont corrects
5. Reportez les temps de calcul pour l’exploration du graphe complet des pistes depuis le sommet 1072 (AVENUE DES CHAMPS ELYSEES).
Indiquez dans chacun des deux cas de figure (graphes partiel et complet des pistes cyclables) s’il est possible d’aller n’importe où à vélo dans le graphe (partiel) de pistes cyclable de Paris depuis les points de départ indiqués.

Cours - Algorithmes d’exploration de graphes¶

Cours - Algorithme Exploration Naïf¶

Nous pouvons maintenant présenter un premier algorithme pour calculer l’exploration d’un graphe. Cet algorithme consiste à

obtenir successivement chaque exploration partielle du graphe d’ordre \(k\), pour \(k\) compris entre 0 et \(n\) (ensemble \(D\), ci-dessous); et à

sauvegarder, à chaque étape, l’union des explorations partielles précédentes (ensemble \(Z\), ci-dessous).

Ainsi, d’après la propriété précédente, à l’issue de l’algorithme le résultat obtenu est bien l’exploration du graphe depuis le sommet initial donné.

Algorithme Exploration Naïf

Données : le nombre \(n\) de sommets du graphe \(G\), l’application successeur \(\Gamma\) du graphe \(G\) et un sommet \(x\) du graphe \(G\)

Résultat : l’exploration \(Z = \mbox{Expl}(G,x)\) depuis \(x\)

\(E := \{x\}\); \(D := \emptyset\); \(Z := \{x\}\)

Pour chaque \(k\) de \(1\) à \(n-1\) Faire

\(D := \delta(G,E)\) // utiliser l’algorithme vu à l’exercice de la section Exo - exploration … dilatation

\(Z := Z \cup D\)

\(E := D\)

[TOCOMPLETER] Exemple d’exécution de l’algo sur un petit graphe (reprendre les exemples précédents pour la dilatation et l’exploration partielle).

Nous allons analyser la complexité de calcul de cet algorithme en supposant que les différents sous-ensembles de sommets (\(E,D\) et, \(Z\)) sont représentés par des tableaux de booléens et que le graphe est représenté par un tableau de listes de successeurs. Pour cela, nous analysons la complexité de chacune des lignes de l’algorithmes.

La ligne 1 consiste à initialiser les ensembles \(E, D\) et \(Z\) représentés par trois tableaux booléens. Sa complexité est donc \(\mathcal{O}(n)\).

La complexité de la ligne 2 est trivialement \(\mathcal{O}(n)\) .

La ligne 3 consiste à exécuter l’algorithme de dilatation à chaque itération de la boucle pour chaque (\(n-1\) itérations). La complexité de l’algorithme de dilatation étant \(\mathcal{O}(n+m)\), la complexité de la ligne 3 est donc \(\mathcal{O}(n(n+m))\).

La ligne 4 consiste à effectuer l’union de deux sous-ensembles de sommets à chaque itération de la boucle pour chaque (\(n-1\) itérations). Les deux ensembes étant représentés par des tableaux de booléens, chaque étape d’union peut être effectuée en \(\mathcal{O}(n)\). Comme il faut effectuer au total \(n-1\) unions, la complexité de la ligne 4 est \(\mathcal{O}(n^2)\).

La ligne 5 consiste à affecter, à chaque itération de la boucle pour chaque (\(n-1\) itérations), l’ensemble \(D\), résultant de la dilataion, à la variable \(E\). Une telle affectation peut être effectuée en temps constant (manipulation d’une adresse) et donc la compléxité gloabale de la ligne 5 est \(\mathcal{O}(n)\).

Ainsi, nous déduisons la propriété suivante qui établit la complexité de l’algorithme Exploration Naïf.

Complexité de l’algorithme Exploration Naïf

Lorsque le graphe est représenté par un tableau de listes chaînées, et que les sous-ensembles de sommets sont représentés par des tableaux booléens, la complexité de l’algorithme Exploration Naïf est

\(\mathcal{O}(n(n+m))\),

où \(n\) et \(m\) sont respectivement les nombres de sommets et d’arcs du graphe donné \(G\).

Cours - Algorithme Exploration Largeur¶

Dans cette section, nous présentons et étudions l’un des algorithmes d’exploration de graphes les plus célèbres: l’algorithme d’exploration en largeur, appelé également algorithme de parcours en largeur d’abord dans certains ouvrages.

Cet algorithme peut être obtenu en améliorant l’algorithme naïf. Pour cela, deux améliorations doivent être apportées à l’algorithme naïf afin de réduire la complexité des lignes 3 et 4.

La première amélioration consiste, dans le déroulement de l’algorithme de dilatation, à “bloquer” l’exploration d’un sommet déjà exploré au cours d’une itértion précédente, c’est à dire, si le sommet appartient déjà à l’ensemble \(Z\) (et ainsi s’il appartient à une exploration partielle d’ordre strictement inférieur à la valeur courante de la variable \(k\)). En effet, l’exploration à partir de ce sommet bloqué n’est pas nécessaire puisque celle-ci a déjà été effectuée à une itération précédente. Ainsi, nous réduisons le nombre d’opérations sans changer le contenu de l’ensemble \(Z\) des sommets explorés.

La seconde amélioration consiste à insérer dans \(Z\) les éléments explorés au cours de l’algorithme de dilatation de manière à supprimer l’opération d’union effectuée à posteriori à la ligne 4.

L’algorithme d’exploration en largeur est présenté ci-dessous. On constate en particulier que les deux lignes 3 et 4 de l’algorithme naïf ont été remplacées ici par les lignes 3 à 8 qui permettent d’intégrer les améliorations ci-dessus.

Algorithme Exploration Largeur (version 1)

Données : le nombre \(n\) de sommets du graphe \(G\), l’application successeur \(\Gamma\) du graphe \(G\) et un sommet \(x\) du graphe \(G\)

Résultat : l’exploration \(Z = \mbox{Expl}(G,x)\) depuis \(x\)

\(E := \{x\}\); \(D := \emptyset\); \(Z := \{x\}\)

Pour chaque \(k\) de \(1\) à \(n-1\) Faire

Tant que \(E \neq \emptyset\) Faire

\(y :=\) un élément quelconque de \(E\) ; \(E := E \setminus \{y\}\) // sélection-suppression

Pour chaque \(z\) dans \(\Gamma(y)\) Faire

Si \(z\) n’appartient pas à \(Z\) Alors

\(D := D \cup \{z\}\)

\(Z := Z \cup \{z\}\)

\(E := D\) ; \(D := \emptyset\)

Analysons maintenant la complexité de l’algorithme d’exploration en largeur. Nous supposerons dans cette analyse que

l’application successeur du graphe \(G\) est représentée par un tableau de listes chaînées ;

les ensembles \(E\) et \(D\) sont représentés par des listes ; et

l’ensemble \(Z\) est représenté en mémoire par un tableau de booléens.

A la ligne 1, l’initialisation de \(E\) et de \(D\) peut être effectuée en \(\mathcal{O}(1)\) (car ces ensembles sont représentés par des listes) alors que l’initialisation de \(Z\) (représenté par un tableau de booléens) est en complexité \(\mathcal{O}(n)\). La complexité de la ligne 2 est trivialement \(\mathcal{O}(n)\).

Afin d’analyser la complexité des lignes suivantes de l’algorithme, il convient d’énoncer les observations suivantes :

chaque sommet de \(G\) est inséré au plus une fois dans \(D\). En effet, chaque fois qu’un élément est inséré dans \(D\) (ligne 7), il l’est également dans \(Z\) (ligne 8) et avant chaque insertion d’un élément \(z\) dans \(D\), on s’assure au préalable que cet élément \(z\) n’est pas dans encore \(Z\) (ligne 6). Comme aucun élément n’est jamais supprimé de \(Z\), on déduit que chaque sommet du graphe est inséré au plus une fois dans \(D\) ;

chaque sommet de \(G\) est inséré au plus une fois dans \(E\). En effet, la seul instruction qui permet d’ajouter des éléments à \(E\) est celle de la ligne 9 qui consiste à transférer dans \(E\) tous les éléments qui appartient à \(D\). Ainsi, comme chaque sommet est inséré au plus une fois dans \(D\) (observation précédente), on déduit que chaque sommet de \(G\) est inséré au plus une fois dans \(E\).

A chaque itération de la boucle tant que un élément est supprimé de \(E\). Comme chaque sommet de \(G\) est inséré au plus une fois dans \(E\), le test de la boucle tant que est au plus \(n\) fois positif. On observe également que ce test est \(n-1\) fois négatif (1 test négatif par itération de la boucle pour chaque). Ainsi la complexité de la ligne 3 est \(\mathcal{O}(n)\).

L’instruction de la ligne 4 est exécutée au plus \(n\) fois (une fois par test positif de la boucle tant que) et chaque exécution de cette instruction (sélection-suppression) est en temps \(\mathcal{O}(1)\) car \(E\) est représenté par un tableau de booléens.

La complexité de la ligne 5 est \(O(n+m)\), \(m\) étant le nombre d’arcs de \(G\). En effet dans le pire cas, chaque sommet du graphe est sélectionné et supprimé une fois depuis \(E\). Ainsi, la liste des successeurs de chaque sommet est parcourue au plus une fois à la ligne 5, conduisant à une complexité en \(O(n+m)\) (revoir si nécessaire l’analyse de complexité de l’algorithme SYM ).

La recherche d’un élément dans un ensemble représenté par un tableau de booléens pouvant être effectuée en tant constant et la ligne 6 étant exécutée au plus \(m\) fois, nous déduisons que la complexité de la ligne 6 est \(\mathcal{O}(m)\). L’insertion d’un élément (externe) dans un ensemble pouvant être effectué en temps constant, la complexité des lignes 7 et 8 est également \(\mathcal{O}(m)\).

Finalement, les instructions de la ligne 9 peuvent être réalisées en échangeant les adresses de \(E\) et de \(D\). Donc, la complexité de cette ligne est \(\mathcal{0}(n)\).

Nous déduisons ainsi la propriété suivante qui établit la complexité de calcul linéaire de l’algorithme Exploration Largeur.

Complexité de l’algorithme Exploration Largeur

Lorsque le graphe est représenté par un tableau de listes chaînées, que les sous-ensembles \(E\) et \(D\) sont représentés par des listes et que l’ensemble \(Z\) est représenté par un tableau de booléens, la complexité de l’algorithme Exploration Largeur est

\(\mathcal{O}(n+m)\),

où \(n\) et \(m\) sont respectivement les nombres de sommets et d’arcs du graphe donné \(G\).

L’algorithme Exploration Largeur peut être re-écrit avec moins de lignes d’instruction. Pour cela, on insère les éléments dans \(E\) directement au lieu de les faire transiter par l’ensemble \(D\). Cette ré-écriture, présentée ci-après, ne change pas l’exécution de l’algorithme ni sa complexité lorsque la collection \(E\) est implémentée avec une liste FIFO (First In - First-Out, premier inséré - premier supprimé).

Algorithme Exploration Largeur (version 2)

Données : le nombre \(n\) de sommets du graphe \(G\), l’application successeur \(\Gamma\) du graphe \(G\) et un sommet \(x\) du graphe \(G\)

Résultat : l’exploration \(Z = \mbox{Expl}(G,x)\) depuis \(x\)

\(E := \{x\}\); \(Z := \{x\}\)

Tant que \(E \neq \emptyset\) Faire

\(y :=\) le premier élément de \(E\) ; \(E := E \setminus \{y\}\) // sélection-suppression

Pour chaque \(z\) dans \(\Gamma(y)\) Faire

Si \(z\) n’appartient pas à \(Z\) Alors

\(E := E \cup \{z\}\)

\(Z := Z \cup \{z\}\)

Exo - Connexité¶

Donnez pour chaque sommet \(x\) du graphe de l’exemple jouet :

la composante connexe contenant \(x\) ; et

la composante fortement connexe contenant \(x\).

En utilisant le vocabulaire de la théorie des graphes, expliquez à quoi correspond l’ensemble des localisations où l’on peut aller et rentrer depuis chez soi à vélo.

Même question mais en s’autorisant d’emprunter les sens unique à contre-sens.

Cours - Connexité¶

Dans cette section nous allons nous intéresser à la notion de connexité dans les graphes. Cette notion topologique joue un rôle important dans de nombreux domaines applicatifs ou fondamentaux allant de la perception visuelle (théorie de la Gestalt) à l’analyse de données ou à la géographie et la topographie. Par exemple, si l’on se pose la question de décrire la différence entre les deux images ci-dessous, on répondra volontiers que :

l’image 1 est d’un seul tenant, qu’elle contient un seul morceau/objet (l’éléphant) et que

l’image 2 comprend deux morceaux, qu’elle contient deux objets (deux éléphants).

La connexité dans les graphes permet de formaliser cette notion de “morceau d’un seul tenant” et d’identifier les différents “morceaux” d’un graphe. Dans cette section, nous étudierons, à l’aide des chemins, les notions de composantes connexes et fortement connexes d’un graphe. Nous présenterons ensuite, à l’aide de l’algorithme d’exploration en largeur, un algorithme efficace pour extraire les composantes connexes et fortement connexes contenant un somment donné d’un graphe.

Connexité (et connexité forte)¶

Intuitivement, un graphe est connexe s’il existe un chemin permettant d’aller de tout sommet à tout autre. Par exemple, cette caractéristique peut être vérifiée dans le graphe \(G_1\) ci dessous mais pas dans \(G_2\) : on dit que \(G_1\) est connexe mais que \(G_2\) ne l’est pas. Lorsque les graphes sont orientés, nous pouvons considérer deux notions différentes selon que nous souhaitons prendre en compte ou non l’orientation des arcs.

Des éléphants représentés par des graphes

Définition

Soit \(G\) un graphe.

Le graphe \(G = (S,A)\) est connexe si pour tout couple de sommets \(x\) et \(y\) il existe une chaîne 3 de \(x\) à \(y\).

Le graphe \(G = (S,A)\) est fortement connexe si pour tout couple de sommets \(x\) et \(y\) il existe une chemin 3 de \(x\) à \(y\)

Notes

3(1,2): On observe que la seule différence entre les notions de graphe connexe et de graphe fortement connexe réside dans la différence entre chemin et chaîne, c’est-à-dire dans la prise en compte ou non des orientations des arcs. Comme toute chaine est un chemin, nous pouvons aussi observer que tout graphe fortement connexe est aussi nécessairement connexe.

Soient les graphes \(G_1\), \(G_2\) et \(G_3\). Pour chacun d’eux, indiquez dans le tableau ci-après s’il est connexe ou non.

est connexe

est fortement connexe

\(G_1\)

\(G_2\)

\(G_3\)

Composante connexe (et fortement connexe)¶

Nous avons vu dans la section précédente comment définir si un graphe est connexe ou pas. Dans cette section, nous étudions les sous-parties d’un graphe qui sont connexes (ou fortement connexe) et qui sont les plus grandes possibles à satisfaire cette propriété de connexité (c’est-à-dire maximales vis-à-vis de l’inclusion).

Définition : composante connexe

Soient \(G =(S,A)\) un graphe et \(x\) un sommet de \(G\)

La composante connexe de \(G\) contenant \(x\), désignée par \(\mbox{CC}(G,x)\) est le sous-ensemble de \(S\) contenant tous les éléments pouvant être atteints depuis \(x\) par une chaine :

\[\begin{eqnarray} \mbox{CC}(G,x) = \{ y \in S \text{ tel qu'il existe une chaîne de } x \text{ à } y \} . \end{eqnarray}\]

Exemple

Soit le graphe \(G\) dessiné ci-dessous.

Nous observons qu’il existe une chaîne du sommet 0 aux sommets 0, 1, 2, 6, 5, 4, et 3 mais pas de 0 à 7, 8, 9, ni 10. Nous pouvons donc affirmer que la composante connexe qui contient le sommet 0 est l’ensemble \(\{0, 1, 2, 6, 5, 4,3\}\) :

\(\mbox{C}(G,0) = \{0, 1, 2, 6, 5, 4,3\}\).

Nous observons aussi que :

\(\mbox{CC}(G,0) = \mbox{CC}(G,1) = \mbox{CC}(G,2)= \mbox{CC}(G,3)= \mbox{CC}(G,4)= \mbox{CC}(G,5)= \mbox{CC}(G,6)= \mbox{CC}(G,1) = \{0, 1, 2, 6, 5, 4,3\}\) ;

\(\mbox{CC}(G,10) = \{10\}\) ; et

\(\mbox{CC}(G,7) = \mbox{CC}(G,8) = \mbox{CC}(G,9) = \{7,8,9\}\).

Soit le graphe \(G_3\) dessiné ci-dessous.

Compléter le tableau suivant en indiquant pour chaque couple de sommets \(x\) et \(y\) si le second (\(y\)) appartient à la composante connexe qui contient le premier (\(x\)).

\(\mbox{CC}(G,0)\)

\(\mbox{CC}(G,1)\)

\(\mbox{CC}(G,2)\)

\(\mbox{CC}(G,3)\)

\(\mbox{CC}(G,4)\)

\(\mbox{CC}(G,5)\)

\(\mbox{CC}(G,6)\)

\(0 \in\)

\(1 \in\)

\(2 \in\)

\(3 \in\)

\(4 \in\)

\(5 \in\)

\(6 \in\)

Définition : composante fortement connexe

Soient \(G =(S,A)\) un graphe et \(x\) un sommet de \(G\)

La composante fortement connexe de \(G\) contenant \(x\), désignée par \(\mbox{CFC}(G,x)\), est le sous-ensemble de \(S\) contenant chaque sommet qui peut être atteint par un chemin depuis \(x\) et depuis lequel \(x\) peut être atteint par un chemin :

\[\begin{eqnarray} \mbox{CFC}(G,x) = \{ y \in S \text{ tel qu'il existe un chemin de } x \text{ à } y \text{ et qu'il existe un chemin de } y \text{ à } x \} . \end{eqnarray}\]

Exemple

Soit le graphe \(G\) dessiné ci-dessous.

A partir de la figure nous pouvons faire les observations suivantes :

il existe une chemin du sommet du sommet 0 au sommet 1 et il existe un chemin du sommet 1 au sommet 0 : le sommet 1 appartient donc à la composante fortement connexe contenant le sommet 0 ;

il n’existe pas de chemin du sommet 0 au sommet 10 : le sommet 10 n’appartient pas à la composante connexe du sommet 0 ; et

il existe un chemin du sommet 0 au sommet 6 mais il n’existe pas de chemin du sommet 6 au sommet 0 : le sommet 10 n’appartient pas à la composante connexe du sommet 0.

Nous observons aussi que :

\(\mbox{CFC}(G,0) = \mbox{CFC}(G,1) = \mbox{CFC}(G,2)= \{0, 1, 2\}\) ;

\(\mbox{CFC}(G,6) = \{6\}\) ;

\(\mbox{CFC}(G,3) = \mbox{CFC}(G,4) = \mbox{CFC}(G,5) = \{3, 4, 5\}\) ;

\(\mbox{CFC}(G,7) = \mbox{CFC}(G,8) = \mbox{CFC}(G,9) = \{7, 8, 9\}\) ;

\(\mbox{CFC}(G,6) = \{10\}\) ;

Soit le graphe \(G_3\) dessiné ci-dessous.

Compléter le tableau suivant en indiquant pour chaque couple de sommets \(x\) et \(y\) si le second (\(y\)) appartient à la composante fortement connexe qui contient le premier (\(x\)).

\(\mbox{CFC}(G,0)\)

\(\mbox{CFC}(G,1)\)

\(\mbox{CFC}(G,2)\)

\(\mbox{CFC}(G,3)\)

\(\mbox{CFC}(G,4)\)

\(\mbox{CFC}(G,5)\)

\(\mbox{CFC}(G,6)\)

\(0 \in\)

\(1 \in\)

\(2 \in\)

\(3 \in\)

\(4 \in\)

\(5 \in\)

\(6 \in\)

Une propriété remarquable des composantes connexes et fortement connexes¶

Pour les curieux

Nous établissons dans cette section une propriété structurelle importante des composantes connexes et fortement connexes. Une conséquence majeure de cette propriété est qu’un graphe peut être “découpé” en composantes connexes (et fortement connexes).

Propriété

Soit \(G = (S,A)\) un graphe. La relation “est dans la composante connexe contenant” est une relation d’équivalence, c’est à dire que les trois affirmations suivantes sont vraies :

[refléxivité] pour tout sommet \(x\) de \(G\), \(x\) appartient à \(CC(G,x)\)

[symétrie] pour tous sommets \(x, y\) de \(G\), si \(y\) appartient à \(CC(G,x)\) alors \(x\) appartient à \(CC(G,y)\) ; et

[transitivité] pour tous sommets \(x, y, z\) de \(G\), si \(y\) appartient à \(CC(G,x)\) et \(z\) appartient à \(CC(G,y)\), alors \(z\) appartient à \(CC(G,x)\).

Preuve

Comme \((x)\) est une chaine, d’après la définition d’une composante connexe, \(x\) appartient à \(CC(G,x)\).

Supposons que \(y\) appartient à \(CC(G,x)\). Alors, il existe une chaîne \(\pi = (x_0 = x, \ldots, x_\ell=y)\) de \(x\) à \(y\) (définition de \(CC(G,x)\)), c’est à dire que \(\pi\) est un chemin de \(x\) à \(y\) dans la fermeture symétrique \(G_s\) de \(G\) (définition d’une chaîne). Comme \(G_s\) est un graphe symétrique, \(\pi' = (x_\ell = y, \ldots, x_0=x)\) est aussi un chemin dans \(G_s\) et donc \(\pi'\) est une chaîne de \(y\) à \(x\), ce qui signifie que \(x\) appartient à \(CC(G,y)\).

Supposons que \(y\) appartient à \(CC(G,x)\) et que \(z\) appartient à \(CC(G,y)\). Alors il existe une chaine \(\pi =(x=x_0, \ldots, x_\ell=y)\) de \(x\) à \(y\) et une chaine \(\pi' =(y=y_0, \ldots, y_k=z)\) de \(y\) à \(z\). Alosr, on peut obeserver que la séquence \(\pi'' =(x=x_0, \ldots, x_\ell=y=y_0, \ldots, y_k=z)\) est une chaîne, ce qui implique que \(z\) appartient à \(CC(G,x)\). CQFD

Corollaire

Soit \(G = (S,A)\) un graphe. L’ensemble des composantes connexes de \(G\) est une partition de \(S\) :

pour tout couple \((x,y)\) de sommets de \(G\), soit \(CC(G,x) = CC(G,y)\) soit \(CC(G,x) \cap CC(G,y) = \emptyset\).

Preuve (par l’absurde) A faire en exercice ;-)

Propriété

Soit \(G = (S,A)\) un graphe. La relation “est dans la composante fortement connexe contenant” est une relation d’équivalence, c’est à dire que les trois affirmations suivantes sont vraies :

[refléxivité] pour tout sommet \(x\) de \(G\), \(x\) appartient à \(CFC(G,x)\)

[symétrie] pour tous sommets \(x, y\) de \(G\), si \(y\) appartient à \(CFC(G,x)\) alors \(x\) appartient à \(CFC(G,y)\) ; et

[transitivité] pour tous sommets \(x, y, z\) de \(G\), si \(y\) appartient à \(CFC(G,x)\) et \(z\) appartient à \(CFC(G,y)\), alors \(z\) appartient à \(CFC(G,x)\).

Preuve

Comme \((x)\) est un chemin, d’après la définition d’une composante fortement connexe \(x\) appartient à \(CC(G,x)\).

Supposons que \(y\) appartient à \(CFC(G,x)\). Par définition d’une composante fortement connexe, il existe une chemin \(\pi = (x_0 = x, \ldots, x_\ell=y)\) de \(x\) à \(y\) et un chemin \(\pi' = (y_0 = y, \ldots, y_k=x)\) de \(y\) à \(x\) (définition de \(CFC(G,x)\)). Donc, d’après la définition d’une composante fortement connexe \(x\) appartient à \(CFC(G,y)\).

Supposons que \(y\) appartient à \(CFC(G,x)\) et que \(z\) appartient à \(CFC(G,y)\). Alors il existe

un chemin \(\pi_1 =(x=x_0, \ldots, x_\ell=y)\) de \(x\) à \(y\);

un chemin \(\pi'_1 =(y=y_0, \ldots, y_k=x)\) de \(y\) à \(x\);

un chemin \(\pi_2 =(y=w_0, \ldots, w_i=z)\) de \(y\) à \(z\); et

un chemin \(\pi'_2 =(z=z_0, \ldots, z_j=y)\) de \(z\) à \(y\).

On remarque que la séquence \(\pi =(x=x_0, \ldots, x_\ell=y=w_0, \ldots, w_i=z)\) est un chemin de \(x\) à \(z\) et que la séquence \(\pi =(z=z_0, \ldots, z_j=y=y_0, \ldots, y_k=x)\) est un chemin de \(z\) à \(x\) ce qui implique que \(z\) appartient à \(CFC(G,x)\). CQFD

Corollaire

Soit \(G = (S,A)\) un graphe. L’ensemble des composantes fortement connexes de \(G\) est une partition de \(S\) :

pour tout couple \((x,y)\) de sommets de \(G\), soit \(CFC(G,x) = CFC(G,y)\) soit \(CFC(G,x) \cap CFC(G,y) = \emptyset\).

Preuve (par l’absurde) A faire en exercice ;-)

Exo - Programmer des algorithmes de composantes connexes¶

Implémentez l’akgorithme CFC.

Conseil #1 : démarrer en recopiant le fichier source du programme explorationLargeur

Conseil #2 : recopier le code de la fonction symEfficace qui se trouve dans votre fichier source symetrique.c

En utilisant votre programme, listez tous les “endroits” où l’on peut aller et revenir en vélo depuis

dans le graphe partiel des pistes cyclables, depuis le sommet 135 (Rue Martel) ; et

dans le graphe complet des pistes depuis le sommet 1072 (AVENUE DES CHAMPS ELYSEES).

[Optionnelle] Même travail que ci-dessus si l’on s’autorise à emprunter les sens unique à contre-sens.

Cours - Algorithme Composante Connexe et Composante Fortement Connexe¶

Dans cette section, nous présentons deux algorithmes. Etant donné un graphe et un sommet de ce graphe,

l’algorithme CC extrait en temps linéaire la composante connexe contenant ce sommet et

l’algorithme CFC produit la composante fortement connexe contenant ce sommet.

Ces deux algorithmes font appel, à la manière d’un appel de fonction, à deux algorithmes étudiés dans des sections précédentes pour calculer le symétrique d’un graphe et l’ exploration d’un graphe. Pour justifier ces appels, nous commençons par établir une propriété qui caractérise les composantes connexes et fortement connexes en utilisant uniquement les notions d’exploration et de symétrique d’un graphe. Nous dérivons ensuite directement les deux algorithmes CC et CFC de cette propriété et étudions leur complexité de calcul.

Propriété

Soient \(G\) un graphe, \(G^{-1}\) le symétrique de \(G\) et \(G_{s}\) la fermeture symétrique de \(G\). Soit \(x\) un sommet de \(G\). Alors, les deux égalités suivantes sont vraies :

\(\mbox{CC}(G,x) = \mbox{Expl}(G_s,x)\)

\(\mbox{CFC}(G,x) = \mbox{Expl}(G,x) \cap \mbox{Expl}(G^{-1},x)\)

Preuve

Comme une chaine est un chemin dans \(G_s\) et que \(\mbox{Expl}(G_s,x)\) est l’ensemble des sommets qui peuvent être atteins depuis \(x\) par un chemin dans \(G_s\), on déduit :\(\mbox{Expl}(G_s,x)\) contient chaque sommet qui peut être atteint depuis \(x\) par un chaine, c’est à dire d’après la définition d’une composante connexe que :\(\mbox{Expl}(G_s,x)\) est exactement la composant connexe contenant \(x\).
Afin de justifier la seconde égalité, nous remarquons, d’après la définition du symétrique d’un graphe, que l’affirmation suivante est vraie :
- il existe un chemin de \(y\) à \(x\) dans \(G\) si et seulement si il existe un chemin de \(x\) à \(y\) dans le symétrique \(G^{-1}\) de \(G\).

Ainsi, un sommet \(y\) qui est à la fois dans l’exploration de \(G\) depuis \(x\) et dans l’exploration de \(G^{-1}\) depuis \(x\) est un sommet qui peut être atteint depuis \(x\) par un chemin dans \(G\) et depuis lequel \(x\) peut être atteint par un chemin dans \(G\), ce qui complète la preuve de la seconde égalité. CQFD

Nous présentons maintenant, les deux algorithmes CC et CFC qui sont directement dérivés de la propriétés précédente. La propriété précédente nous permet donc de garantir qu’à l’issue de l’exécution de ces algorithmes les résultats produits sont bien la composante connexe et la composante fortement connexe contenant le sommet initial donné.

Algorithme CC

Données : le nombre \(n\) de sommets du graphe \(G\), l’application successeur \(\Gamma\) du graphe \(G\) et un sommet \(x\) de du graphe \(G\)

Résultat : la composante connexe \(Z = \mbox{Expl}(G,x)\) contenant \(x\)

Obtenir le symetrique \(G^{-1}\) de \(G\) avec l’algorithme SYM

Construire le graphe \(G_s\) à partir de \(G\) et \(G^{-1}\)

Calculer \(\mbox{Expl}(G_s,x)\) avec l’algorithme Exploration Largeur et sauvegarder le résultat dans \(Z\)

Si le graphe est représenté par un tableau de listes chaînées, la complexité des ligne 1 et 3 est \(\mathcal{O}(n+m)\). La ligne 2 peut également être effectuée en temps linéaire en ajoutant les arcs de \(G_s\) en parcourant successivement les listes de successeurs du graphe \(G\) et du graphe \(G^{-1}\). Ainsi, nous déduisons la propriété suivante qui établit la complexité de l’algorithme CC.

Complexité de l’algorithme CC

Lorsque le graphe est représenté par un tableau de listes chaînées, la complexité de l’algorithme CC est

\(\mathcal{O}(n+m)\),

où \(n\) et \(m\) sont respectivement les nombres de sommets et d’arcs du graphe donné \(G\).

Algorithme CFC

Données : le nombre \(n\) de sommets du graphe \(G\), l’application successeur \(\Gamma\) du graphe \(G\) et un sommet \(x\) de du graphe \(G\)

Résultat : la composante fortement connexe \(Z = \mbox{Expl}(G,x)\) contenant \(x\)

Calculer \(\mbox{Expl}(G,x)\) avec l’algorithme Exploration Largeur et sauvegarder le résultat dans \(X\)

Obtenir le symetrique \(G^{-1}\) de \(G\) avec l’algorithme SYM

Calculer \(\mbox{Expl}(G^{-1}, x)\) avec l’algorithme Exploration Largeur et sauvegareder le résultat dans \(Y\)

\(Z := \emptyset\)

Pour chaque \(x\) de \(0\) à \(n\) Faire

Si \(x\) appartient à \(X\) et \(x\) appartient à \(Y\) Alors

\(Z := Z \cup \{x\}\)

Dans l’algorithme précédent, si le graphe est représenté par un tableau de listes chaînées, la complexité des ligne 1 à 3 est \(\mathcal{O}(n+m)\) d’après les analyses de complexité des algorithmes SYM et Exploration Largeur. Si l’ensemble \(Z\) est représenté par un tableau de booléens, la complexité des lignes 4 et 5 est \(\mathcal{O}(n)\). Comme (i) l’ensemble produit par l’algorithme Exploration Largeur est représenté par un tableau de booléens et comme (ii) la recherche d’un élément dans un ensemble avec cette représentation s’effectue en temps constant, la complexité de la ligne 6 est en temps linéaire (au plus 2n recherche d’éléments en temps constant). Enfin, comme l’insertion d’un élément dans l’ensemble \(Z\) peut être effectué en temps constant (\(Z\) étant représenté par un tableau de booléens), on déduit que la complexité de la ligne 7 est également \(\mathcal{O}(n)\). Nous déduisons donc la propriété suivante qui établit la complexité de calcul linéaire de l’algorithme CFC.

Complexité de l’algorithme CFC

Lorsque le graphe est représenté par un tableau de listes chaînées, la complexité de l’algorithme CFC est

\(\mathcal{O}(n+m)\),

où \(n\) et \(m\) sont respectivement les nombres de sommets et d’arcs du graphe donné \(G\).