Construire et optimiser un réseau d’espions - partie 1 : arborescence¶

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

Fil rouge¶

Les services secrets doivent établir un réseau d’espionnage. Plus précisément, il s’agit d’établir un plan de routage des messages secrets afin qu’un individu donné puisse faire parvenir des informations à un groupe de \(N\) autres individus. Parmi cet ensemble d’individus, certains ont la possibilité de se contacter et d’échanger directement des informations alors que d’autres ne le peuvent pas. Lorsque deux individus s’échangent un message, le message peut être intercepté avec une certaine probabilité connue. Dans ce cours, nous allons répondre aux questions suivantes :

Comment transmette un message à tous les membres du réseaux ?

Comment effectuer cette transmission en minimisant la probabilité que le message soit intercepté ?

Afin de réaliser cette étude, nous répondrons aux questions suivantes :

Comment modéliser les données du problème ?

Comment modéliser l’ensemble des solutions possibles pour router le message (sans redondance) ?

Comment trouver parmi toutes les solutions possibles, une solution optimale, (c’est-à-dire pour laquelle la probabilité d’interception est minimale) ?

Pour répondre à ces questions,

nous introduirons la notion de graphe (à arêtes) pondérées ;

nous présenterons les notions d’arbres et d’arborescences ; et

nous considérerons le problème de recherche d’un arbre de poids minimum et nous étudierons l’algorithme de Kruskal pour le résoudre.

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 quizz 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. Il n’est pas demandé d’inclure vos réponses aux quiz dans votre rapport.

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 9 individus numérotés de (00)0 à (00)9, l’individu 007 doit transmettre des messages aux neuf autres. Pour cela, les échanges suivants sont possibles :

entre les individus 0 et 9 avec une probabilité d’interception de 0,3%

entre les individus 0 et 3 avec une probabilité d’interception de 0,6%

entre les individus 0 et 2 avec une probabilité d’interception de 0,2%

entre les individus 1 et 3 avec une probabilité d’interception de 0,3%

entre les individus 1 et 4 avec une probabilité d’interception de 0,4%

entre les individus 1 et 6 avec une probabilité d’interception de 0,3%

entre les individus 1 et 9 avec une probabilité d’interception de 0,4%

entre les individus 2 et 5 avec une probabilité d’interception de 0,6%

entre les individus 2 et 7 avec une probabilité d’interception de 0,5%

entre les individus 3 et 7 avec une probabilité d’interception de 0,2%

entre les individus 4 et 6 avec une probabilité d’interception de 0,2%

entre les individus 4 et 8 avec une probabilité d’interception de 0,4%

entre les individus 5 et 7 avec une probabilité d’interception de 0,1%

entre les individus 5 et 8 avec une probabilité d’interception de 0,2%

Exo - Modéliser les données avec un graphe¶

Dessinez le graphe qui modélise les données du problème “exemple jouet” ?
A quoi correspondent les sommets du graphe ?
Expliquez pourquoi un graphe non-orienté est suffisant et à quoi correspondent les arêtes de ce graphe ?
Quelle fonction de pondération préconisez vous ?

Cours - Graphes à arêtes pondérées¶

Dans cette section, nous rappelons la définition d’un graphe non-orienté et introduisons la notion de graphe (non-orienté) pondéré.

Un graphe non-orienté est une représentation plus compacte d’un graphe symétrique (sans boucle). Dans un graphe symétrique les arcs vont par paire puisque chaque arc \((x,y)\) peut être regroupé avec l’arc inverse \((y,x)\). Dans un graphe non-orienté, pour éviter de représenter les deux arcs appariés \((x,y)\) et \((y,x)\), on se contente de considérer la paire non-ordonnée \(\{x,y\}\).

Définition: Graphe non-orienté

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

\(S\) est un ensemble fini ; et

\(A\) est un ensemble d’ensembles de deux éléments distincts de \(S\).

Exemple

Soient

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

\(A = \{\{0, 1\}, \{1, 3\}, \{0, 2\}, \{1,2\} \}\).

Le couple \(G = (S,A)\) est un graphe non-orienté

Définition: graphe non-orienté

Soit \(G = (S,A)\) un graphe non-orienté.

Chaque élément de \(S\) est appelé un sommet de \(G\).

Chaque élément de \(A\) est appelé une arête de \(G\).

On dit que \(x\) est adjacent à \(y\) si \(\{x,y\}\) est une arête de \(G\).

Si \(G = (S,A)\) est un graphe non-orienté, l’application successeur de \(G\), désignée par \(\Gamma_G\) associe à tout sommet l’ensemble des sommets qui lui sont adjacents, c’est à dire :

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

Remarque.

Si \(G = (S,A)\) est un graphe non-orienté, le couple \((S,\Gamma_G)\) est un graphe symétrique sans boucle appelé le graphe orienté associé à \(G\).

Exemple

Soit \(G = (S,A)\) le graphe non-orienté tel que

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

\(A = \{\{0, 1\}, \{1, 3\}, \{0, 2\}, \{1,2\} \}\).

Lorsque l’on veut dessiner un graphe non-orienté, on représente chaque arête par un trait sans flèche reliant deux sommets. On peut ainsi dessiner le graphe ci-dessus de la manière suivante.

Représentation graphique d'un graphe non-oriénté

Le graphe orienté associé à \(G\) est le suivant.

Représentation graphique d'un graphe non-orienté

Soit le graphe non-orienté \(G\) de l’exemple ci-dessus, indiquez pour chacune des affirmations ci-dessous si elle vrai ou fausse.

\(\{0,1\}\) est une arête de \(G\).
\(\{1,0\}\) est une arête de \(G\).
\((0,1)\) est une arête de \(G\).
\((1,0)\) est une arête de \(G\).
\(0\) appartient à \(\Gamma_G(1)\).
\(1\) appartient à \(\Gamma_G(0)\).
1 est adjacent à 3.
3 est adjacent à 1.
0 est adjacent à 3.

Compléter chacune des affirmations suivantes avec la valeur numérique qui convient:

Le graphe \(G\) possède arêtes.
Le graphe orienté associé à \(G\) possède arcs.

Définition: graphe pondéré

Soit \(G =(S,A)\) un graphe non-orienté.

Une application associant un nombre réel à chaque élément de \(A\) est appelée une (fonction de) pondération de \(G\)

Si \(P\) est une pondération de \(G\)

pour toute arête \(u\) de \(G\), le réel \(P(u)\) est appelé le poids de \(u\) ; et

le couple \((G,P)\) est appelé un graphe pondéré.

Dans certains cas, on préfère le terme de valeur ou de coût à celui de poids.

Exemple

Soit \(G = (S,A)\) le graphe non-orienté tel que

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

\(A = \{\{0, 1\}, \{1, 3\}, \{0, 2\}, \{1,2\} \}\).

Soit \(P\) l’application de \(A\) dans l’ensemble des réels définie par

\(P(\{0,1\}) = 12\) ;

\(P(\{1,3\}) = 0,5\) ;

\(P(\{0,2\}) = 1\) ; et

\(P(\{1,2\}) = -7\).

Le couple \((G,P)\) est ainsi un graphe pondéré. Le poids de l’arête \(\{0,1\}\) vaut 12, celui de \(\{1,3\}\) vaut 0,5, celui de \(\{0,2\}\) vaut 1 et celui de \(\{1,2\}\) est -7. Ce graphe pondéré peut être représenté de la manière suivante.

Représentation graphique d'un graphe pondéré

Exo - Transmission sans redondance d’un message secret¶

Proposez, pour le cas de l’exemple jouet, un schéma de transmission d’un message secret qui garantit que chaque espion ne reçoit le message qu’une seule fois (en ce sens on dit que la transmission est sans-redondance). Expliquez votre proposition en langage naturel. Pour cet exercice, nous ne prenons pas en compte les probabilités d’interception des messages.

Reformulez votre proposition en utilisant le vocabulaire de la théorie des graphes.

Combien d’envois sont nécessaires (et suffisants) pour que chaque espion reçoive bien le message ? Justifier votre réponse en utilisant une prorpiété démontrée sur les graphes.

En ajoutant une unique ligne d’instruction dans l’algorithme Exploration Largeur, proposez un algorithme Arboresence qui

étant donné un graphe fortement connexe \(G = (S,A)\) et un sommet \(r\)

produit un sous-graphe \(G' = (S, A')\) de \(G\) (c’est à dire \(A' \subseteq A\)) qui est une arborescence de racine \(r\). Cette arborescence sera représentée sous la forme d’un tableau de prédécesseurs.

Votre proposition devra être donnée en pseudo-langage et devra suivre le formalisme des algorithmes présentés dans le précédent atelier. En particulier, vous veillerez à bien décrire, en plus de la suite des instructions, les données d’entrée et les résultats.

Implémentez l’algorithme précédent. Pour cela, créez une fonction arborescence dans un fichier arborescence.c. Cette fonction devra retourner l’arborescence sous la forme d’un tableau ‘’pred’’. Pour cela, vous devez

copier le fichier explorationLargeur.c implémenté lors de l’atelier sur l’exploration de graphes et

transformer la fonction explorationLargeur en arbrorescence en suivant l’algorithme proposé ci-avant.

Utilisez votre implémentation pour afficher une liste possible des “communications” à établir entre les agents pour faire circuler le message secret sans redondance.

Pour chaque communication, vous afficherez l’émetteur et le récepteur du message

Pour cela, vous devez créer au préalable un fichier au format ‘’.graphe’’ pour contenir le graphe qui modélise les données de l’exemple jouet.

Comme nous ne nous intéressons pas ici aux probabilités d’interception, il n’est pas nécessaire de faire figurer le poids des arcs dans votre fichier.

De plus, vous pouvez enregistrer le graphe sous la forme d’un graphe asymétrique mais, dans ce cas, dans votre programme, n’oubliez pas après avoir lu le graphe depuis le fichier d’en extraire sa fermeture symétrique avant de calculer l’arborescence.

Cours - Arbres et arborescences¶

Les notions d’arbre et d’arborescence sont utiles dans de nombreuses applications et sont omniprésentes en informatique. On peut par exemple citer :

arborescence des fichiers et répertoires ;

arbre de création des processus dans un système d’exploitation ;

arbre phylogénique : relation de parenté entre les espèces vivantes ;

arbre et arborescence de recherche, qui peuvent être binaire, équilibrée, rouge et noir, etc. ;

arbre de décisions ;

arborescence d’évaluation d’une expression arithmétique et plus généralement arbre syntaxique ;

organisation hiérarchique d’une société, de données quelconques ;

carte heuristique (“mind map”) ;

etc.

Intuitivement, un arbre est un graphe dont le dessin fait penser à un arbre en botanique au sens où chaque branche n’est connectée à l’arbre que par une seule de ses extrémités. En d’autres termes, il ne peut y avoir de cycle dans un arbre.

Dans cette section, nous présentons une définition d’un arbre et d’une arborescence et nous étudions certaines de leurs propriétés caractéristiques. Nous terminons la section en montrant qu’il est possible de représenter une arborescence dans un simple tableau.

Remarque liminaire. Dans cette section, tous les graphes considérés sont asymétriques (c’est à dire que si le couple \((a,b)\) est un arc alors \((b,a)\) n’est pas un arc). Afin de simplifier la lecture, dans cette section (et uniquement dans cette section), nous omettons volontairement cette précision lorsque nous mentionnons un graphe.

Arbres¶

Définition: Arbre

Un arbre est un graphe connexe dans lequel il n’y a pas de cycle.

Soient les graphes \(G_1, \ldots, G_6\) suivants. Pour chacun d’eux, indiquez dans le tableau ci-après, s’il est un arbre, s’il est connexe et s’il est sans cycle.

Exemples de graphes dont certains sont des arbre

	est un arbre	est sans cycle	est connexe
\(G_1\)
\(G_2\)
\(G_3\)
\(G_4\)
\(G_5\)
\(G_6\)

Un arbre peut être caractérisé (c’est à dire définit de manière équivalente) de différentes façons. La propriété ci-dessous présente quatre caractérisations standards des arbres. Ces caractérisations nous permettent de mieux comprendre ce qu’est un arbre. Elles nous offrent également différentes possibilité pour reconnaître qu’un graphe est un arbre. Selon le contexte, il est parfois plus simple d’utiliser une caractérisation plutôt qu’une autre.

Propriété

Soit \(G\) un graphe à \(n\) sommets. Les quatre affirmations suivantes sont équivalentes :

\(G\) est un arbre ;

\(G\) est connexe et le nombre d’arcs de \(G\) est égal à \(n-1\) ;

\(G\) est sans cycle et le nombre d’arcs de \(G\) est égal à \(n-1\) ;

pour toute paire de sommets \(x\) et \(y\) de \(G\), il existe une unique chaine élémentaire de \(x\) à \(y\) ;

Une conséquence remarquable de cette propriété est que le nombre d’arcs d’un arbre est égal au nombre de ses sommets moins 1.

Afin d’établir la preuve de cette propriété, nous introduisons la notion d’isthme dans un graphe.

Définition: isthme

Soit \(G =(S,A)\) un graphe et soit \(u\) un arc de \(G\). On dit que \(u\) est un isthme de \(G\) si \(u\) n’apparaît dans aucun cycle de \(G\).

Soient les graphes \(G_1, \ldots, G_3\) suivants.

Pour chacune des affirmations ci-dessous, indiquez si elle est vraie ou fausse.

\((0,2)\) est un isthme de \(G_1\)

\((0,1)\) est un isthme de \(G_1\)

\((5,1)\) est un isthme de \(G_1\)

\((4,1)\) est un isthme de \(G_1\)

\((5,4)\) est un isthme de \(G_1\)

\((3,5)\) est un isthme de \(G_1\)

\((3,6)\) est un isthme de \(G_1\)

\((4,6)\) est un isthme de \(G_1\)

Complétez les 3 affirmations ci-dessous afin qu’elles soient vraies.

Le graphe \(G_1\) possède isthmes.

Le graphe \(G_2\) possède isthmes.

Le graphe \(G_3\) possède isthmes.

On peut observer que s’il on retire un arc \(u =(a,b)\) d’un graphe \(G = (S,A)\), on obtient graphe \(G' = (S, A \setminus \{u\})\) tel que :

\(G\) et \(G'\) possèdent le même nombre de composantes connexes si \(u\) n’est pas un isthme de \(G\); et

\(G'\) possède exactement une composante connexe de plus que \(G\) si \(u\) est un isthme de \(G\).

Ainsi, l’on peut déduire que si l’on retire successivement tous les arcs d’un graphe \(G\) connexe à \(n\) sommets, au cours de la séquence, nous devons retirer exactement \(n-1\) isthmes puisque le graphe final, sans arc, contient exactement \(n\) composantes connexes (une pour chaque sommet). Nous pouvons donc affirmer :

[P1] un graphe connexe contient au moins \(n-1\) arcs.

Par ailleurs, nous pouvons observer qu’un graphe à \(n\) sommets possède au plus \(n-1\) isthmes (sinon, en retirant successivement tous ces isthmes, on obtiendrait un graphe avec strictement plus que \(n\) composantes connexes, ce qui est impossible puisque le graphe ne possède que \(n\) sommets). Comme dans un graphe sans cycle, tout arc est un isthme nous pouvons affirmer également

[P2] un graphe sans cycle possède au plus \(n-1\) arcs.

A l’aide de ces deux affirmations en gras, il est possible de démontrer les caractérisations d’un arbre présentées dans la propriété précédente.

Preuve (pour les curieux).

Pour démontrer que les quatre affirmatioins de la propriété précédente sont équivalentes, nous allons montrer que la première affirmation implique la seconde, que la seconde implique la troisième, que la troisième implique la quatrième et que la quatrième implique la première.

(\((1) \Longrightarrow (2)\)) Démontrons tout d’abord que l’affirmation 1 implique l’affirmation 2. Pour cela, nous supposons que \(G\) est un arbre, c’est-à-dire que :

\(G\) est connexe et sans cycle ;

D’après l’affirmation P2 ci-dessus, ceci implique que :

\(G\) est connexe et possède au plus \(n-1\) arcs.

De plus, comme \(G\) est connexe, d’après l’affirmation (P1), \(G\) contient au moins \(n-1\) arcs, ce qui nous permet de conclure que

\(G\) est connexe et possède exactement \(n-1\) arcs

(\((2) \Longrightarrow (3)\)) Nous allons maintenant démontrer que l’affirmation 2 implique l’affirmation 3. Pour cela nous supposons que :

\(G\) est connexe et possède exactement \(n-1\) arcs.

Chaque arc \(u\) de \(G\) est un isthme. En effet, d’après (P1), le graphe \(G' = (S, A \setminus \{u\})\) ne peut être connexe puisqu’il contient \(|A|-1= n-2\) arcs, donc, comme \(G\) est connexe, d’après les observations qui suivent la définition d’un isthme, nous déduisons que \(u\) est un isthme. Ainsi, aucun arc de \(G\) n’apparaît dans un cycle, ce qui implique que le graphe \(G\) est sans cycle. En d’autre termes, l’affirmation suivante est vraie :

\(G\) est sans cycle et contient \(n-1\) arcs.

(\((3) \Longrightarrow (4)\)) Démontrons maintenant que l’affirmation (3) implique affirmation (4). Pour cela, nous supposons que

\(G\) est sans cycle et contient \(n-1\) arcs.

Comme \(G\) est sans cycle, chaque arc de \(G\) est un isthme. Soit une séquence \((G_1 = G, \ldots, G_{n})\) de graphes obtenues en supprimant successivement chacun des arcs de \(G\) (pris dans n’importe quel ordre). D’après l’observation énoncée après la définition d’un isthme, on peut affirmer que \(G_i\) possède exactement une composante connexe de plus que \(G_{i-1}\). Ainsi, \(G_{n}\) possède exactement \(n-1\) composantes composantes connexes de plus que \(G_{1}\). Comme \(G_n\) ne peut avoir plus de \(n\) composantes connexes (car il possède \(n\) sommets), et que \(G_1\) ne peut en avoir moins que une, nous déduisons que \(G_1 = G\) possède une unique composante connexe, c’est à dire que \(G\) est connexe. Ainsi, pour tous sommets \(x\) et \(y\), il existe une chaine élémentaire \(\pi\) de \(x\) à \(y\). De plus, comme \(G\) est sans cycle, nous pouvons observer qu’il n’existe pas d’autre chaine élémentaire de \(x\) à \(y\) (s’il existait une autre chaine \(\pi'\) de \(x\) à \(y\) alors \(G\) posséderait un cycle voir dessin ci-dessous).

(\((4) \Longrightarrow (1)\)) Démontrons maintenant que l’affirmation (4) implique affirmation (1). Nous supposons donc ici que :

pour toute paire de sommets \(x\) et \(y\) de \(G\), il existe une unique chaine élémentaire de \(x\) à \(y\) ;

Donc, nous pouvons affirmer que \(G\) est connexe. Pour compléter la preuve que \(G\) est un arbre, il reste donc à montrer qu’il n’y a pas de cycle dans \(G\). Pour cela, il est suffisant de montrer que chaque arc de \(G\) est un isthme. Soit \(u = (x,y)\) un arc quelconque de \(G\). Nous allons procéder par l’absurde pour montrer que \(u\) est un isthme, c’est à dire que nous allons supposer que \(u\) n’est pas un isthme et nous allons montrer que cela contredit notre hypothèse (que l’affirmation (4) est vraie). Si \(u\) n’est pas un isthme, il existe alors un circuit qui passe par \(u\). Donc, il existe une chaîne élémentaire \((x_0 = x , x_1 = y, \ldots, x_\ell = x)\) de longueur au moins 3. Ainsi, la séquence \((x_1 = y, \ldots, \x_ell=x)\) est une chaine élémentaire de \(y\) à \(x\) de longueur au moins 2. Comme \((y,x)\) est une chaîne élémentaire de \(y\) à \(x\) de longueur 1, cela signifie qu’il existe deux chaines élémentaires distinctes de \(y\) à \(x\), ce qui est en contradiction avec notre hypothèse. CQFD

Arborescences¶

Définition: Racines et arborescences

Soit \(G =(S,A)\) un graphe et soit \(r\) un sommet de \(G\).

On dit que \(r\) est une racine de \(G\) si tout sommet de \(G\) peut être atteint par un chemin depuis \(r\), c’est-à-dire si :

\(\mbox{Expl}(G,r) = S\)

On dit que \(G\) est une arborescence de racine \(r\) si \(G\) est un arbre et si \(r\) est une racine de \(G\).

Soient les graphes \(G_1, \ldots, G_6\) suivants.

Complétez les 6 affirmations ci-dessous afin qu’elles soient vraies.

Le graphe \(G_1\) possède racine(s).

Le graphe \(G_2\) possède racine(s).

Le graphe \(G_3\) possède racine(s).

Le graphe \(G_4\) possède racine(s).

Le graphe \(G_5\) possède racine(s).

Le graphe \(G_6\) possède racine(s).

Indiquez, pour chacune des affirmations suivantes, si elle est vraie ou fausse.

Le graphe \(G_1\) est une arborescence.

Le graphe \(G_2\) est une arborescence.

Le graphe \(G_3\) est une arborescence.

Le graphe \(G_4\) est une arborescence.

Le graphe \(G_5\) est une arborescence.

Le graphe \(G_6\) est une arborescence.

Nous pouvons observer que si \(G\) est une arborescence de racine \(r\), alors \(r\) et le seul sommet de \(G\) qui est une racine (sinon il y aurait un cycle, ce qui n’est pas possible puisqu’une arborescence est un arbre).

La propriété suivante caractérise les arborescences. Cette caractérisation suggère en particulier une représentation très compacte des arborescence à l’aide d’un tableau de prédécesseurs.

Propriété

Soit \(G =(S,A)\) un graphe à \(n\) sommets. Les deux affirmations suivantes sont équivalentes :

\(G\) est une arborescence de racine \(r\) ; et

\(r\) est une racine de \(G\) qui n’a pas de prédécesseur et chaque sommet de \(S \setminus \{r\}\) possède un unique prédécesseur.

Preuve (pour les curieux).

Démontrons d’abord l’implication directe. Pour cela, nous allons montrer que si l’affirmation 1 est vraie alors l’affirmation 2 l’est également. Nous supposons donc que l’affirmation 1 est vraie. D’après la définition d’une arborescence, cela signifie que \(G\) est un arbre. Donc d’après la propriété caractéristique des arbres, cela implique que \(G\) contient exactement \(n-1\) arcs. Comme \(r\) est une racine, il existe un chemin non trivial de \(r\) à chaque sommet \(x\) dans \(S \setminus \{r\}\). Ainsi chaque sommet de \(S \setminus \{r\}\) possède au moins un prédécesseur. Comme \(S \setminus \{r\}\) contient \(n-1\) sommets et que \(G\) contient \(n-1\) arcs, nous déduisons que chaque sommet \(S \setminus \{r\}\) possède exactement un prédécesseur et que \(r\) n’a pas de prédécesseur.

Démontrons maintenant l’implication réciproque, c’est-à-dire que l’affirmation 2 implique l’affirmation 1. Pour cela, nous supposons donc désormais que l’affirmation 2 est vraie. Comme \(r\) est une racine de \(G\), pour démontrer que l’affirmation 1 est vraie, il suffit de prouver que \(G\) est un arbre. Pour cela, nous allons montrer que

(i) \(G\) est connexe et que

(ii) \(G\) possède \(n-1\) arcs

ce qui d’après la propriété caractéristique des arbres est suffisant pour affirmer que \(G\) est un arbre. Pour démontrer que la proposition (i) est vraie nous allons montrer que toute paire de sommets \(x\) et \(y\) est liée par une chaine. Soient \(x\) et \(y\) deux sommets de \(G\). Comme \(r\) est une racine de \(G\), il existe un chemin de \(r\) à \(x\) dans \(G\) ainsi qu’un chemin de \(r\) à \(y\). D’après la définition d’une chaine, il existe ainsi une chaine de \(x\) à \(r\) et une chaine de \(r\) à \(y\). La concaténation de ces deux chaines est donc une chaine de \(x\) à \(y\), ce qui complète la preuve que (i) \(G\) est connexe. Montrons maintenant que la proposition (ii) est également vraie. Pour cela, il convient d’abord d’observer que le nombre d’arcs de \(G\) est égal à la somme des nombres de prédécesseurs de chaque sommet du graphe. Comme le graphe \(G\) comprend

\(n-1\) sommets qui ont exactement un prédécesseurs (chaque sommet de l’ensemble \(S \setminus \{r\}\) ) et

1 sommet sans prédécesseur (le sommet \(r\)),

nous déduisons que \(G\) possède \(n-1\) arcs. CQFD

Représentation mémoire d’une arborescence¶

Il est possible de représenter une arborescence \(G =(S,A)\) de racine \(r\) à l’aide d’un simple tableau. Soit \(S = \{0, \ldots, n-1\}\) l’ensemble des sommets de cette arborescence alors, d’après la propriété caractéristiques des arborescences présentée dans la section précédente, nous pouvons définir le tableau pred à \(n\) par

pred[x] = NULL si \(x = r\); et

pred[x] = y où \(y\) est l’unique prédécesseur de \(x\) si \(x \neq r\).

Nous pouvons observer que le tableau pred permet bien de retrouver tous les arcs de l’arboresence \(G\), c’est-à-dire l’ensemble

\(A = \{ (pred[x],x)~|~x \in S \text{ tel que } pred[x] \neq NULL\}\).