Découverte et exploration des graphes : partie 1¶

Présentation du problème fil rouge et règles du jeu¶

Fil rouge¶

Le premier problème traité dans ce cours est le suivant :

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

Pour cela, nous allons étudier les pistes cyclables de la région parisienne dont une description est donnée sur cette page web :

https://opendata.paris.fr/explore/dataset/reseau-cyclable/information

Afin de réaliser cette étude, nous devrons répondre à deux questions intermédiaires

Comment modéliser les données utiles du problèmes ?

Comment extraire la solution de notre problème à partir de la modélisation des données

La première question nous conduira à introduire la notion d’un graphe alors que la seconde nous conduira à étudier les algorithmes d’exploration de graphes (recherche de composante connexe).

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. Pour cela vous devez

créer un document google doc par groupe ;

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”¶

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 - modéliser des données avec un graphe¶

Dessinez le graphe \(G = (S,A)\) modélisant les données du problème “exemple jouet” .

Combien de sommets possède ce graphe ?

Combien d’arcs possède ce graphe ?

A quoi correspondent les sommets du graphe ?

Numérotez les sommets du graphe ? A partir de maintenant, nous pourrons supposer que \(S = \{0, ..., n-1\}\), l’entier \(n\) étant le nombre de sommets du graphe.

Donnez la liste des arcs de \(G\).

Pour chaque sommet de \(G\), donnez l’ensemble de ses successeurs.

Cours - Graphe¶

Un graphe est une structure de données abstraite qui permet de représenter des relations entre des données. Par exemple, on pourra représenter par un graphe les relations entre

des affaires criminelles,
des unités d’enseignement dans une école d’ingénieurs,
des personnes présentes sur un réseau social,
des villes, des quartiers, des croisements de routes,
les pixels d’une image,
des fragments d’ADN, etc.

Rappel sur les ensembles¶

La notion de graphe est définie et étudiée dans le cadre mathématique de la théorie des ensembles. Nous commençons par rappeler quelques notations ensemblistes utiles pour la suite de notre propos.

Soit \(E\) un ensemble fini.

Un ensemble \(S\) est appelé un sous-ensemble de \(E\) ou une partie de \(E\) si chaque élément de \(S\) est aussi un élément de \(E\).

Si \(S\) est un sous-ensemble de \(E\), on écrit \(S \subseteq E\).

L’ensemble des parties de \(E\) est désigné par \(\mathcal{P}(E)\)

Le nombre d’éléments d’un ensemble \(E\) est désigné par \(|E|\) et l’on dit que \(|E|\) est le cardinal de \(E\)

Soit l’ensemble \(E = \{a,b,c\}\), indiquez si les affirmations suivantes sont vraies ou fausses

\(\{a,b\}\) est un ensemble.
\((a,b)\) est un ensemble.
\((a,b)\) est un couple.
\(\{a,b\} = \{b,a\}\).
\((a,b)=(b,a)\).
Un élément peut apparaître plusieurs fois dans un ensemble.
Un élément peut apparaître plusieurs fois dans un couple.
\((a,a)\) est un couple.
\(a\) est un sous ensemble de \(E\).
\(\{a\}\) est un sous ensemble de \(E\).
\(\{a,c\}\) est un sous-ensemble de \(E\).
\(\{a,e\}\) est un sous-ensemble de \(E\).
\(\emptyset\) est un sous-ensemble de \(E\).
\(\mathcal{P}(E) = \{\{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}\).
\(\mathcal{P}(E) = \{\{a\}, \{b\}, \{c\},\{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}\).
\(\mathcal{P}(E) = \{\emptyset, \{a\}, \{b\}, \{c\},\{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}\).

Compléter avec la valeur numérique qui convient:

\(|E|=\)
\(|\mathcal{P}(E)|=\)
\(|\{1,2,3,4\}|=\)
\(|\mathcal{P}(\{1,2,3,4\})|=\)

Première définition d’un graphe¶

Nous allons voir une première définition d’un graphe. Cette définition est la plus naturelle pour représenter des données dont certaines sont en relation (binaire). Nous verrons ultérieurement une autre représentation équivalente (par application successeur) qui conduit à une résolution plus efficaces de certains problèmes formulés en terme de graphe.

Définition: Graphe

Un graphe est un couple \(G=(S,A)\) tel que:

\(S\) est un ensemble fini; et
\(A\) est un ensemble de couples d’éléments de \(S\)

Dans les applications, lorsque nous modélisons les données d’un problème par un graphe,

l’ensemble \(S\) correspond aux données : on associe une donnée à chaque élément de \(S\); et

l’ensemble \(A\) permet d’encoder la relation entre ces données : chaque paire de données en relation est un élément de \(A\).

Définition: sommet et arc

Si \(G=(S,A)\) est un graphe,

tout élément de \(S\) est appelé un sommet de \(G\); et
tout élément de \(A\) est appelé un arc de \(G\).

Chaque donnée est donc modélisée par un sommet du graphe et chaque paire de données en relation s’appelle un arc du graphe.

Exemple: Graphe des amitiés

Considérons un groupe de quatre personnes :

Jean ;

Daniel ;

Yukiko ; et

Michel.

Nous savons également que :

Jean apprécie Daniel ;

Daniel apprécie Jean ;

Yukiko apprécie Michel ; et

Jean apprécie Michel.

Ces informations peuvent être représentées par le graphe \(G = (S,A)\) tel que;

\(S = \{Jean, Daniel, Yukiko, Michel\}\) ; et

\(A = \{(Jean, Daniel), (Daniel, Jean), (Yukiko, Michel), (Jean, Michel) \}\).

\(Jean, Daniel, Yukiko, Michel\) sont ainsi les sommets de \(G\) et \((Jean, Daniel), (Daniel, Jean), (Yukiko, Michel), (Jean, Michel)\) sont les arcs de \(G\).

On remarque que le couple \((Yukiko, Michel)\) est un arc de \(G\) mais que \((Michel, Yukiko)\) n’appartient pas à \(A\) et ne forme donc pas un arc de \(G\). En d’autres termes la relation “apprécie” entre ces quatre personnes n’est pas symétrique et l’on dira que le graphe associé n’est pas symétrique. Nous aborderons formellement cette notion un peu plus loin dans ce cours.

Représentation visuelle d’un graphe¶

Un graphe peut être visuellement représenté par un dessin :

chaque sommet est alors représenté par un cercle (éventuellement numéroté pour pouvoir retrouver le lien avec les données) ; et

chaque arc est une flèche joignant les cercles représentant les sommets en relation.

Dans le dessin, la position des sommets n’a aucune importance car ce qui nous intéresse est la relation entre les données. On dit parfois que l’on s’intéresse à la topologie des données en opposition à leur géomtrie. En topologie, un concept central est celui de voisinage. Nous aborderons cette notion de voisinage pour les graphes dans la section suivante.

Exemple: Dessin du graphes des amitiés

Nous pouvons représenter le graphe \(G =(S,A)\) présenté dans l’exemple de la section précédente par le dessin suivant :

Dans le dessin, le numéro des sommets permet de retrouver le lien avec les personnes mises en relation. On rappelle (et on utilise dans le dessin ci-dessus) le numérotage suivant :

Jean ;

Daniel ;

Yukiko ; et

Michel.

Comme la position des sommets n’a pas importance, on peut aussi très bien tracer le dessin suivant pour \(G\).

Application successeurs (voisinage)¶

Nous allons voir dans cette section qu’un graphe peut être défini de manière équivalente en utilisant la notion de voisinage. Cette définition alternative est très utile en pratique car elle permet de parcourir les données de proche-en-proche. Intuitivement, étant donné (un graphe représentant) des données en relation, le voisinage d’une de ces données est constitué de toutes les données mises en relation avec celle-ci.

Définition: successeur et prédecesseur

Si \(G=(S,A)\) est un graphe et si \((a,b)\) est un arc de ce graphe, on dit que

\(b\) est un successeur de \(a\) ; et que
\(a\) est un prédécesseur de \(b\).

Exemple: Successeur et prédecesseur dans le graphe des amitiés

Dans le graphe \(G =(S,A)\) des exemples précédents :

\(Michel\) est un successeur de \(Jean\) et \(Jean\) est un prédécesseur de \(Michel\) car l’ensemble \(A\) contient l’arc \((Jean,Michel)\); mais
\(Jean\) n’est pas un successeur de \(Michel\) car le couple \((Michel,Jean)\) n’est pas un arc de \(G\) (c’est-à-dire \((Michel,Jean)\) n’appartient pas à \(A\)).

On remarque également qu’un sommet peut être à la fois prédécesseur et successeur d’un autre. Par exemple, \(Jean\) est à la fois un prédécesseur et un successeur de \(Daniel\).

On peut aussi observer que \(Michel\) n’a aucun successeur et que \(Yukiko\) n’a aucun prédécesseur.

Nous notons que dans ce graphe aucun sommet n’est successeur de lui même. Cependant, en général, il est tout à fait possible qu’un sommet \(x\) soit son propre successeur (et son propre prédécesseur) si le couple \((x,x)\) est un arc. Un tel arc d’un sommet vers lui même ests souvent appelé une boucle.

Définition: Application successeurs

Soit un graphe \(G = (S,A)\), l’application successeur de \(G\), désignée par \(\Gamma_G\), est l’application qui associe à tout sommet de \(G\) l’ensemble de ses successeurs, c’est-à-dire:

\begin{eqnarray} \Gamma_G :~& S &\longrightarrow & \mathcal{P}(S)\\ & a & \longmapsto & \Gamma_G(a) = \{b~;~(a,b) \in A\}. \end{eqnarray}

Etant donné un graphe \(G\) et l’un de ses sommets \(x\), l’ensemble \(\Gamma_G(x)\) est parfois appelé le “voisinage” de \(x\) (dans le graphe \(G\)).

Soit le graph \(G = (S,A)\), des exemples précédents (“graphes des amitiés”) et soit \(\Gamma_G\) son application successeur, indiquez si les affirmations suivantes sont vraies ou fausses.

\(Yukiko\) est un successeur de \(Michel\).
\(Yukiko\) est un prédécesseur de \(Michel\).
\(Michel \in \Gamma_G(Yukiko)\).
\(Yukiko \in \Gamma_G(Michel)\).
\(\Gamma_G(Jean) = \{Daniel, Michel\}\).
\(\Gamma_G(Daniel) = Jean\).
\(\Gamma_G(Daniel) = \{Jean\}\).
\(\Gamma_G(Michel) = \{\emptyset\}\).
\(\Gamma_G(Michel) = \emptyset\).
\(\Gamma(Yukiko) = \{Michel\}\).

Comme nous l’avons vu avec les items 5-10 de l’exercice précédent, connaissant l’ensemble des sommets d’un graphe et son ensemble d’arcs, nous pouvons toujours déduire son application successeur. Il s’agit d’une conséquence directe de la définition de l’application successeur. Nous allons voir que, réciproquement, si l’on connait l’ensemble des sommets d’un graphe \(G\) et son application successeur \(\Gamma_G\) alors il est possible d’en déduire l’ensemble des arcs de ce graphe. Autrement dit, l’ensemble des arcs du graphe contient exactement la même information que l’application successeur : les deux représentations (par ensemble d’arcs et par application successeur) sont donc équivalentes.

Nous allons commencer par nous convaincre sur un exemple qu’il est possible de déduire l’ensemble des arcs d’un graphe à partir de son application successeur, puis nous formulerons la propriété mathématique qui établit précisément l’équivalence entre les deux représentations des graphes.

Soit le graphe \(G\),

dont l’ensemble des sommets est \(S = \{0, 1, 2, 3 \}\)
dont l’application successeur \(\Gamma_G\) est définie par
- \(\Gamma_G(0) = \{0,1,2\}\)
- \(\Gamma_G(1) = \{1\}\)
- \(\Gamma_G(2) = \{0, 1\}\)
- \(\Gamma_G(3) = \emptyset\).

Indiquez pour chaque affirmation ci-dessous si elle est vraie ou fausse.

\((0,0)\) est un arc de \(G\).
\((0,1)\) est un arc de \(G\).
\((0,2)\) est un arc de \(G\).
\((0,3)\) est un arc de \(G\).
\((1,0)\) est un arc de \(G\).
\((1,1)\) est un arc de \(G\).
\((1,2)\) est un arc de \(G\).
\((1,3)\) est un arc de \(G\).
\((2,0)\) est un arc de \(G\).
\((2,1)\) est un arc de \(G\).
\((2,2)\) est un arc de \(G\).
\((2,3)\) est un arc de \(G\).
\((3,0)\) est un arc de \(G\).
\((3,1)\) est un arc de \(G\).
\((3,2)\) est un arc de \(G\).
\((3,3)\) est un arc de \(G\).
\(G = (S,A)\) avec \(A= \{(0,1), (0,2), (2,0), (2,1)\}\).
\(G = (S,A)\) avec \(A= \{(0,0), (1,0), (2,0), (1,1), (0,2), (1,2)\}\).
\(G = (S,A)\) avec \(A= \{(0,0), (0,1), (0,2), (1,1), (2,0), (2,1)\}\).

Propriété: Représentations des graphes

Soit \(G\) un graphe dont l’ensemble de sommets est \(S\), dont l’ensemble d’arcs est \(A\) et dont l’application sucesseur est \(\Gamma_G\). L’affirmation suivante est vrai :

pour tous éléménts \(x\) et \(y\) de \(S\), le couple \((x,y)\) appartient à \(A\) si et seulement si \(y\) appartient à \(\Gamma_G(x)\).

La propriété précédente établit que l’on peut représenter un graphe par le couple \((S,A)\) ou par le couple \((S, \Gamma_G)\). Ainsi, le couple \((S, \Gamma_G)\) est également appelé un graphe. Selon nos besoins, nous pourrons désormais considérer indifféremment l’une ou l’autre de ces représentations.

Exo - Représentation mémoire d’un graphe¶

Dessinez la représentation mémoire du graphe modélisant les données du problème “exemple jouet”

si l’on utilise un tableau de liste chainées

si l’on utilise une matrice booléenne

si l’on utilise un tableau d’arcs (tableaux tete queue)

Dans le graphe “exemple jouet” quelle information complémentaire peut-on avoir intérêt à associer aux sommets du graphe. Représentez le tableau (ou les tableaux) permettant de stocker ces informations annexes.

Un code en C pour représenter un graphe a été implémenté pour vous. Prenez connaissance du fichier graphes.h et indiquez comment les graphes sont représentés dans ce code.

Cours - Représentation mémoire d’un graphe¶

Nous allons étudier trois représentations mémoire fondamentales pour les graphes :

par tableau de listes chaînées

par matrice booléenne (c’est-à-dire par tableau de tableau de booléens)

par tableau d’arcs

Les deux premières visent à représenter en mémoire l’application successeur du graphe, alors que la troisième s’intéresse à la représentation de l’ensemble des arcs du graphe. Quelle que soit la représentation choisie, les sommets sont toujours représentés de la même manière. Comme nous l’avons vu précédemment, les successeurs d’un sommet forment un sous-ensemble des sommets du graphe. Nous étudions donc également comment représenter en mémoire un sous-ensemble de sommets. Le plan de ce chapitre est donc le suivant.

Représentation mémoire des sommets du graphe

Représentation mémoire d’un sous ensemble de sommets : liste chaînée et tableau de booléens

Représentation mémoire d’un graphe par tableau de listes chaînées

Représentation mémoire d’un graphe par matrice booléenne

Représentation mémoire d’un graphe par tableau d’arcs

Représentation mémoire des sommets du graphe¶

Dans la mémoire d’un ordinateur, l’ensemble des sommets d’un graphe \(G\), à \(n\) sommets est représenté par :

un ensemble d’entiers consécutifs commençant à la valeur 0 et se terminant à l’indice \(n-1\). Ainsi, on pose dans la suite du cours \(S = \{0, \ldots, n-1\}\). En mémoire, il suffit de stocker le nombre \(n\) de sommets du graphe et l’on ne stocke donc pas explicitement la liste complète des entiers de 0 à \(n-1\); et

éventuellement un (ou plusieurs) tableau pour associer des informations complémentaires à chaque sommet. Les informations relatives au sommet i sont positionnées à l’indice i de ce tableau.

Exemple: représentation mémoire des sommets du graphe des amitiés

Le graphe des amitiés présenté dans la section précédentes comporte 4 sommets associés aux noms des quatre amis. Ainsi dans la mémoire,

les sommets du graphe seront les entiers 0, 1, 2, 3 et il nous suffit de mémoriser que le graphe contient 4 sommets ;

on considère un tableau additionnel, appelé info, tel que info[0] = "Jean", info[1] = "Daniel", info[2] = "Michel" et info[3] = "Yukiko". Ce tableau mémorise l’association entre les numéros des sommets et les prénoms des quatre amis.

Représentation mémoire d’un sous ensemble de sommets : liste chaînée et tableau de booléen¶

Dans la suite de cette section, nous désignons par \(X\) le sous-ensemble de \(S = \{0, \ldots, n-1\}\) que nous souhaitons représenter en mémoire.

L’ensemble \(X\) peut être représenté par une liste chainée.

La liste chaînée est composée de maillons.

Chaque maillon représente un élément de \(X\).

Chaque maillon contient deux champs :

le premier est un élément de \(S\) (donc un entier entre \(0\) et \(n-1\) ) ; et

le second est un pointeur vers le maillon suivant dans la liste chainée; le pointeur NULL indiquant la fin de la liste.

La liste est référencée par l’adresse de son premier maillon ou par le pointeur NULL si l’ensemble \(X\) est vide.

Exemple: représentation d’un sous-ensemble par liste chaînée

Le sous-ensemble \(X = \{1,2,4\}\) de \(S = \{0, \ldots, 9\}\) peut être représenté par la liste chainée dessinée ci-dessous :

Exemple de liste chaînée pour représenter un sous-ensemble

L’ensemble \(X\) peut également être représenté par un tableau de booléens.

Le tableau de booléen contient \(n\) cases, indicées de \(0\) jusqu’à \(n-1\).

La case d’indice \(i\) vaut vrai si \(i\) appartient à \(X\).

La case d’indice \(i\) vaut faux si \(i\) n’appartient pas à \(X\).

Exemple: représentation d’un sous-ensemble par tableau de booléens

Le sous-ensemble \(X = \{1,2,4\}\) de \(S = \{0, \ldots, 9\}\) peut être représenté par le tableau suivant :

L’efficacité des algorithmes de graphes dépend très souvent des opérations élémentaires effectuées sur des ensembles (sous-ensemble de sommets, ensemble de successeurs, etc.). Les choix des structures de données pour représenter ces ensembles doivent donc être effectués avec discernement à partir de l’efficacité des opérations élémentaires mises en jeu. Dans l’exercice suivant, on vous demande d’évaluer la complexité algorithmique des opérations ensemblistes élémentaires selon que l’on choisit d’implémenter un ensemble par une liste chaînée ou par un tableau de booléen. Afin de pouvoir concevoir par la suite des algorithmes de graphes efficaces, il est donc nécessaire d’être capable de retrouver rapidement par soi même les réponses à l’exercice suivant.

Donnez la complexité algorithmique de chacune des opérations ci-dessous, selon que l’on implémente un sous-ensemble \(X\) de \(S = \{0, \ldots, n-1\}\) avec une liste chainée (LC) ou avec un tableau de booléen (TB).

Opération	peudo-code	Complexité LC	Complexité TB
Initialisation	\(X := \emptyset\)	O()	O()
Test ensemble vide	si (\(X = \emptyset\))	O()	O()
Sélection	\(x :=\) élément quelconque de \(X\)	O()	O()
Sélection-suppression	\(x :=\) élément quelconque de \(X\); \(X := X \setminus \{x\}\) ;	O()	O()
Recherche	si (\(x \in S\))	O()	O()
Insertion externe 1	\(X := X \cup \{x\}\)	O()	O()
Insertion (générale) 2	\(X := X \cup \{x\}\)	O()	O()
Suppression	\(X := X \setminus \{x\}\)	O()	O()
Parcours	Pout chaque \(x\) dans \(X\)	O()	O()

Notes

1: Une insertion d’un élément \(x\) dans une ensemble \(X\) est dite externe lorsque l’on sait par avance que l’élément à insérer \(x\) n’appartient pas à \(X\).
2: Une insertion d’un élément \(x\) dans une ensemble \(X\) est dite général lorsque l’on ne sait pas à l’avance si l’élément \(x\) à insérer apprtient déjà à l’ensemble \(X\).

Représentation mémoire d’un graphe par tableau de listes chaînées¶

Avec cette première représentation mémoire des graphes, il faut stocker les deux informations suivantes :

l’ensemble des sommets du graphe \(G\) étant l’ensemble \(S = \{0, \ldots, n-1\}\), il suffit de sauvegarder le nombre \(n\) de sommets pour mémoriser les sommets du graphes;

l’application successeur de \(G\) est sauvegardée en mémoire par un tableau T de listes chainées tel que :

T[i] pointe sur une liste chaînée représentant l’ensemble \(\Gamma_G(i)\) des successeurs du sommet \(i\).

Exemple

Représentation d'un graphe par liste chaînée de successeurs.

Représentation mémoire d’un graphe par matrice booléenne¶

Comme précédemment, avec cette deuxième représentation, il faut stocker deux informations pour mémoriser un graphe :

l’ensemble des sommets du graphe \(G\) étant l’ensemble \(S = \{0, \ldots, n-1\}\), il suffit de sauvegarder le nombre \(n\) de sommets pour mémoriser les sommets du graphes ;

l’application successeur de \(G\) est représentée par une matrice booléenne M de de taille n par n (n lignes comportant chacune n éléments) :

La ligne i est la représentation de l’ensemble \(\Gamma(i)\) des successeurs du somment \(i\) par un tableau de booléens. C’est à dire que l’on a T[i][j] = VRAI si et seulement si le sommet \(j\) est successeur du sommet \(i\).

Exemple

Représentation d'un graphe par matrice booléenne.

Représentation mémoire d’un graphe par tableau d’arcs¶

Enfin, avec cette troisième représentation des graphes en mémoire, il est nécessaire de mémoriser les trois informations suivantes :

l’ensemble des sommets du graphe \(G\) étant l’ensemble \(S = \{0, \ldots, n-1\}\), il suffit de sauvegarder en mémoire le nombre \(n\) de sommets.

Le nombre \(m\) d’arcs du graphe est également sauvegardé.

Les arcs du graphe sont numérotés de manière arbitraire et ils sont représentés par deux tableaux I et T de \(m\) entiers tels que

I[i] est le sommet intial de l’arc numéro \(i\) ; et

T[i] est le sommet terminal de l’arc numéro \(i\).

Exemple

Représentation d'un graphe par tableau d'arcs.

Exo - Graphe des sens interdits¶

Vous l’avez peut être expérimenté, certains cyclistes à Paris sont “rebels” ! Ils empruntent allègrement les pistes cyclables en sens interdit. Nous pouvons cependant distinguer deux catégories de rebelles :

le rebelle-rebelle n’emprunte que des pistes cyclable à contre-sens ;

le rebelle pratique emprunte les pistes cyclables indiférement dans le sens de la marche ou en sens interdit selon ce qui est le plus pratique pour lui.

Etant donné le graphe \(G = (S,A)\) trouvé lors des exercices fil rouge précédents,

Quel graphe doit-on considérer pour modéliser les trajets d’un individu rebelle rebelle ?

Quel graphe doit-on considérer pour modéliser les trajets d’un individu rebelle pratique ?

Nommez ces deux graphes en utilisant le vocabulaire de la théorie des graphes et dessinez les (dans le cas de l’exemple jouet).

Si, pour une ville donnée, le graphe des pistes cyclables est symétrique, que peut-on en conclure des pistes cylables dans cette ville ?

Cours - Symétrique et graphes¶

Dans cette section nous étudions les notions de

symétrique d’un graphe,

fermeture symétrique d’un graphe; et

graphe symétrique.

Cela, nous conduira, dans une prochaine section, à introduire notre premier algorithme de graphes dont l’objectif sera précisément de calculer le symétrique d’un graphe donné.

Définition: symétrique d’un graphe

Soit \(G = (S,A)\) un graphe. Le symétrique de \(G\) est le graphe désigné par \(G^{-1}\) tel que :

l’ensemble de sommets de \(G^{-1}\) est égal à l’ensemble de sommets de \(G\) ; et
pour tout sommet \(x\) de \(G^{-1}\), nous avons \(\Gamma_{G^{-1}}(x) = \{ y \in S \text{ tel que } x \in \Gamma_G(y) \}\).

En d’autres termes,

\(G\) et \(G^{-1}\) ont les mêmes sommets ; et

un sommet \(y\) est un successeur d’un sommet \(x\) dans \(G^{-1}\) si et seulement si \(x\) est un successeur de \(y\) dans \(G\).

On peut ainsi observer que \((x,y)\) forme un arc de \(G^{-1}\) si et seulement si \((y,x)\) est un arc de \(G\). Graphiquement, il suffit d‘“inverser les flèches” du graphe \(G\) pour obtenir celles de \(G^{-1}\).

Exemple

Dans l’exemple ci-dessous, on a :

\(G = (\{0,1,2,3\}, \{ (0,1), (1,0), (0,3), (2,3)\})\) et

\(G^{-1} = (\{0,1,2,3\}, \{ (1,0), (0,1), (3,0), (3,2)\})\).

Comme le graphe \(G\) ci-dessus représente la relation “apprécie” dans le groupe de 4 amis (cf premier exemple du cours), nous pouvons affirmer que le graphe \(G^{-1}\) représente la relation “est apprécié par” dans ce même groupe.

Définition: graphe symétrique

Soit \(G = (S,A)\) un graphe. On dit que \(G\) est un graphe symétrique s’il est égal à son symétrique, c’est à dire si

\(G^{-1} = G\).

Considérez les 3 graphes suivants et répondez au vrai-faux :

\(G_1 = (S_1, A_1)\) avec \(S_1 = \{0, 1, 2\}\) et \(A_1 = \{(0,0), (0,1), (1,0)\}\) ;

\(G_2 = (S_2, \Gamma_{G_2})\) avec \(S_2 = \{0, 1, 2\}\) et \(\Gamma_{G_2}(0) = \{1,2\}, \Gamma_{G_2}(1) = \{2\},\) et \(\Gamma_{G_2}(2) = \emptyset\) ;

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

Indiquez pour chaque affirmation ci-dessous si elle est vraie ou fausse.

\(G_1\) est symétrique.
\(G_2\) est symétrique.
\(G_3\) est symétrique.

Définition: fermeture symétrique

Soit \(G\) un graphe. La fermeture symétrique de \(G\) est le graphe désigné par \(G_s\) tel que

l’ensemble de sommets de \(G_s\) est égal à l’ensemble de sommets de \(G\) ; et
l’ensemble des arcs de \(G_s\) est égal à l’union des ensembles d’arcs de \(G\) et de son symétrique \(G^{-1}\).

Exemple

Exo - Implémentation d’un premier algorithme de graphes¶

On vous propose le code suivant pour calculer le symétrique d’un graphe en utilisant la bibliothèque graphes.h étudiée précédemment.

#include "graphes.h"

graphe * symInefficace(graphe * g)
/* ====================================================================== */
{
    graphe *g_1;
    int nsom, narc, k, x, y;
    pcell p;

    nsom = g->nsom;
    narc = g->narc;
    g_1 = initGraphe(nsom, narc); /* Initialise une structure pour un graphe de nsom sommets et narc arcs */

    for (y = 0; y < nsom; y++) /* pour tout y sommet de g */
        for (x = 0; x < nsom; x++) /* pour tout x sommet de g */
            if (estSuccesseur(g, x, y)) /* si y est un successeur de x dans g */
                ajouteSuccesseur(g_1, y, x); /*  gamma_1[y] =: gamma_1[y] U {x} */
    return g_1;
} /* Sym() */

Ce code fait appel à la fonction estSuccesseur donnée ci-dessous :

int estSuccesseur(graphe *g, int x, int y)
/* ====================================================================== */
{
    pcell p; /* pointeur de maillon utilise pour parcourir la liste de successeurs */
    int z; /* pour stocker les successeurs de x */
    /* parours de la liste des successeurs de x */
    p = g->gamma[x];
    while(p != NULL){
        z = p->som;
        if (z == y) return 1;
        p = p->suivant;
    }
    /* On a atteint la fin de la liste des successeurs sans trouver y */
    return 0;
} /* EstSuccesseur() */

L’algorithme sous-jacent est inefficace. Evaluez sa complexité de calcul en fonction du nombre \(n\) de sommets du graphe et du nombre \(m\) d’arcs. Justifiez avec quelques arguments en langage naturel cette complexité.

Donnez l’implémentation en C d’un algorithme linéaire (\(O(n+m)\)) pour calculer le symétrique d’un graphe. Pour cela, complétez le code ci-dessous qui a été démarré pour vous.

graphe * symEfficace(graphe * g)
/* ====================================================================== */
{
    graphe *g_1;
    int nsom, narc, k, x, y;
    pcell p;

    nsom = g->nsom;
    narc = g->narc;
    g_1 = initGraphe(nsom, narc);
    /* A Completer ci-dessous, possible en 3 lignes, souhaitable en moins de 6 :-) */

    return g_1;
} /* Sym() */

Afin de tester ces deux algorithmes en pratique, nous mettons à votre disposition les fichiers suivants que vous devez télécharger :

graphes.h contient la déclaration de la structure de graphe et les prototypes des fonctions élémentaire pour manipuler des graphes.

graphes.c contient le code des fonctions de manipulations élémentaires de graphes déclarées dans graphes.h

symetrique.c contient les codes ci-dessus, ainsi qu’une fonction main qui

lit un graphe depuis un fichier dont le chemin d’accès est passé en paramètre au programme ;

calcule le symétrique de ce graphe (en utilisant la fonction inefficace). Remarquez que le temps d’exécution est mesuré et affiché à l’écran ; et

sauvegarde le résultat dans un fichier dont le chemin d’accès est passé comme second argument au programme.

Pour utiliser le programme de calcul du symétrique sous Linux vous devez :

télécharger les fichiers ci-dessus et les sauvegarder dans un même répertoire

ouvrir un terminal et positionner le repertoire de travail vers le repertoire contenant vos fichiers source

compiler le programme avec la commande gcc graphes.c symetrique.c -o symetrique` (voire mieux en utilisant make et ce Makefile téléchargeable)

executer le programme avec la commande ./symetrique entree.graphe resultat.graphe

Vérifier le résultat des deux algorithmes 3 sur un graphe de petite taille (par exemple amitie.graphe). Pour vérifier que le résultat est correct, il suffit d’ouvrir avec un éditeur de texte le fichier contenant le graphe d’entrée et de le comparer avec celui contenant le graphe résultat produit par le programme.

Reportez les temps d’exécution 3 des deux algorithmes pour différents graphes :

graphe aléatoire à 100 sommets et 500 arcs

graphe aléatoire à 1 000 sommets et 5 000 arcs

graphe aléatoire à 10 000 sommets et 50 000 arcs

graphe aléatoire à 100 000 sommets et 500 000arcs

graphe aléatoire à 10 000 sommets et 20 000 arcs

graphe aléatoire à 10 000 sommets et 150 000 arcs

graphe aléatoire à 10 000 sommets et 200 000 arcs

graphe aléatoire à 10 000 sommets et 300 000 arcs

sous-ensemble de pistes cyclables 4

pistes cyclables (complet)

Commentez, ces résultats de temps de calcul. Est-ce conforme aux analyses de complexité des algorithmes étudiés ?

Notes

3(1,2)

N’oubliez pas d’insérer dans symetrique.c le code que vous avez produit pour la fonction symEfficace, et d’appeler cette fonction depuis le programme main lorsque vous souhaitez mesurer les temps exécution de l’algorithme efficace de calcul du symétrique !!

4

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 -lm
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.

N’oubliez pas d’inclure une visualisation de (certains de) vos graphes dans votre rapport ;-) !

Cours - Algorithme SYM : calcul du symétrique d’un graphe¶

Dans cette section, nous nous intéressons au problème suivant :

étant donné un graphe \(G\),

calculer le symétrique de \(G\).

Dans le cas où l’on représente les graphes par des tableaux d’arcs un algorithme trivial pour résoudre ce problème (en temps constant) consiste à échanger (“swapper”) les deux tableaux “I” et “T”.

Nous proposons ci-dessous un algorithme pour le cas de graphes représentés par leur application successeur et nous analysons sa complexité dans les deux cas suivants :

les applications successeurs sont sauvegardées dans des matrices booléennes ; et

les applications successeurs sont sauvegardées dans des tableaux de liste chaînée.

Algorithme SYM

Données : le nombre \(n\) de sommets du graphe \(G\) et l’application successeur \(\Gamma\) du graphe \(G\)
Résultat : l’application successeur \(\Gamma^{-1}\) du symétrique de \(G\)

Pour chaque \(x\) de \(0\) à \(n-1\) Faire \(\Gamma^{-1}(x) := \emptyset\)
Pour chaque \(x\) de \(0\) à \(n-1\) Faire
1. Pour chaque \(y\) dans \(\Gamma(x)\) Faire
  \(\Gamma^{-1}(y) := \Gamma^{-1}(y) \cup \{x\}\)

Pour évaluer la complexité de calcul d’un algorithme, il faut évaluer la complexité de chacune des ses lignes.

Supposons d’abord que \(\Gamma\) et \(\Gamma^{-1}\) sont représentées par des matrices booléennes et désignons par \(m\) le nombre d’arcs du graphe \(G\).

La complexité de la ligne 1 est \(\mathcal{O}(n^2)\) car cette ligne consiste à initialiser \(n\) sous-ensembles représentés sous forme de tableaux de booléens.

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

La complexité de la ligne 3 est \(\mathcal{O}(n^2)\) car cette ligne consiste à parcourir \(n\) sous-ensembles représentés sous forme de tableaux de booléen.

La complexité de la ligne 4 est \(\mathcal{O}(m)\) car cette ligne est exécutée exactement une fois par arc du graphe et, pour chaque arc, elle consiste à insérer un élément dans un ensemble représenté sous forme de tableau de booléens.

Comme \(m\) est inférieur à \(n^2\), nous déduisons la propriété suivante qui établit la complexité de l’algorithme SYM dans ce premier cas de figure.

Complexité de l’algorithme SYM avec matrices booléennes

Lorsque les graphes sont implémentés sous forme de matrices booléennes, la complexité de l’algorithme SYM est

\(\mathcal{O}(n^2)\),

où \(n\) est le nombre de sommet du graphe donné \(G\).

Supposons maintenant que \(\Gamma\) et \(\Gamma^{-1}\) sont représentées par des tableaux de listes chaînées.

La complexité de la ligne 1 est \(\mathcal{O}(n)\) car cette ligne consiste à initialiser \(n\) sous-ensembles représentés sous forme de liste chaînée.

La complexité de la ligne 2 est trivialement \(\mathcal{O}(n)\).
L’analyse de la ligne 3 est plus délciate. Elle consiste à parcourir la liste des successeurs de chaque sommet du graphe. L’algorithme de parcours d’une liste chainée L est le suivant:
1
2
3
4
5
m := L.premierMaillon
Tant que (m != NULL) Faire
    x := m.sommet // x prend la valeur du sommet associé au maillon m (premier champ de m)
    // opérations à effectuer pour le sommet x
    m := m.next // m prend la valeur de l'adresse du prochain maillon (second champ de m)
Nous observons que pour parcourir une liste de \(k\) éléments, la ligne 1 est exécutée une fois, le test de la ligne 2 est exécuté \(k+1\) fois (\(k\) tests positifs suivis d’un test négatif), et les instructions des lignes 3-5 sont exécutées \(k\) fois. Dans l’algorithme SYM, à la ligne 3, \(n\) parcours de listes sont effectués et le nombre total d’éléments contenus dans ces listes est \(m\) (puisque le graphe contient \(m\) arcs). Ainsi, la complexité de la ligne 3 de l’algorithme SYM est \(\mathcal{O}(n+m)\).

La complexité de la ligne 4 est \(\mathcal{O}(m)\) car cette ligne est exécutée exactement \(m\) fois et qu’elle consiste à insérer un élément externe dans une liste (opération en temps constant).

Complexité de l’algorithme SYM avec listes chaînées de successeurs

Lorsque les graphes sont représentés par tableaux de listes chaînées, la complexité de l’algorithme SYM est

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

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

Lorsque le nombre d’arcs n’est pas trop grand par rapport au nombre de sommets, l’algorithme utilisant les listes chaînées présente une meilleure complexité que celui utilisant des matrices booléenne. Cet avantage se réduit lorsque le nombre d’arcs augmente et que lon se rapproche du cas limite où \(m = n^2\). Cette constatation est très souvent vérifiée pour les algorithmes de graphe : il est généralement avantageux de considérer la représentation par listes de successeurs lorsque les graphes à traiter sont peu denses.

Bonus culture générale - Quelques graphes remarquables¶

Un graphe \(G = (S,A)\) est symétrique si, pour tout arc \((a,b)\) dans \(A\), le couple “inverse” \((b,a)\) est également un arc dans \(A\).
Un graphe \(G = (S,A)\) est asymétrique si, pour tout arc \((a,b)\) dans \(A\), le couple “inverse” \((b,a)\) n’est pas dans \(A\).
Un graphe symétrique est également appelé un graphe non-orienté. Une paire d’arc \(\{(a,b), (b,a)\}\) dans un tel graphe est appelé une arête et peut être représentée simplement par l’ensemble \(\{a,b\}\) pour lequel l’ordre d’apparence entre \(a\) et \(b\) n’a pas importance. Graphiquement, on peut dessiner une arête par un trait sans flèche reliant deux sommets. En conséquence, un graphe non-orienté est souvent défini comme la donnée d’une paire \((S,A)\), où \(S\) est un ensemble fini et où \(A\) est un ensemble d’ensembles de deux éléments distincts de \(S\).
Un graphe \(G = (S,A)\) est réflexif si, pour tout sommet \(x\) dans \(S\), le couple \((x,x)\) est un arc dans \(A\). Tout arc \((x,x)\) dans \(A\) est appelé une boucle de \(G = (S,A)\).
Un graphe \(G = (S,A)\) est antiréflexif s’il n’existe aucune boucle pour \(G\).
Un graphe \(G = (S,A)\) est complet si tout couple de sommets distinct forme un arc dans \(A\).

Considérez les graphes \(G_1, G_2, \ldots, G_5\) ci dessous.

Compléter ci-dessous afin que les affirmations soient vrais !

Je suis symétrique mais pas complet. Je suis le graphe d’indice .
Je suis asymétrique. Je suis le graphe d’indice .
Je possède trois sommet et suis complet. Je suis le graphe d’indice .
Je ne suis ni symétrique ni asymétrique. Je suis le graphe d’indice .
Je suis complet et non encore cité dans les affirmations ci-dessus. Je suis le graphe d’indice .
Je ne suis ni réflexif, ni irreflexif. Je suis le graphe d’indice .
Je suis réflexif. Je suis le graphe d’indice .