MaDIR Arbre et arborescence

Section 7.4 Arbre et arborescence

Pour cette section, on suppose que tous les graphes sont finis, c’est-à-dire qu’ils possèdent un nombre fini de sommets, et donc aussi un nombre fini d’arêtes.

🔗

Sous-section 7.4.1 Forêt et arbre

Définition 7.4.1.

Un graphe \(G=(S,A)\) simple est appelé une forêt s’il ne contient aucun cycle.

🔗

Si en plus le graphe \(G\) est connexe, on dira que \(G\) est un arbre. Pour expliciter qu’un graphe est un arbre, on notera souvent le graphe \(T=(S,A)\) au lieu de \(G=(S,A)\text{.}\)

🔗

Exemple 7.4.2. Une forêt et deux arbres.

\(T_1\)\(T_2\)\(F\)

🔗

Proposition 7.4.3.

Un graphe \(T=(S,A)\) est un arbre si et seulement si pour chaque paire de sommets \(s, t\in S\text{,}\) il existe une unique chaîne reliant \(s\) et \(t\text{.}\)

🔗

On termine la sous-section 7.4.1 avec deux propositions concernant les arbres.

🔗

Tout d’abord, lorsqu’on regarde les graphes d’un arbre, on remarque que certains des sommets ont une caractéristique particulière. En effet, on peut remarquer que pour chaque exemple, il y a toujours des sommets de degré \(1\text{.}\) Ceci n’est pas une coïncidence.

🔗

Par la suite, on remarque aussi qu’il existe une relation entre le nombre d’arêtes d’un arbre et le nombre de sommets de celui-ci.

🔗

Proposition 7.4.4.

Soit \(T=(S,A)\) un arbre tel que \(|S|\geq 2\text{,}\) alors il existe au moins deux sommets distincts \(s, t\in S\) tels que \(\deg(s)=\deg(t)=1\text{.}\)

🔗

Démonstration.

Puisque \(T\) est un graphe connexe avec au moins deux sommets, il existe au moins une chaîne simple de longueur \(n\geq 1\text{.}\) Supposons que \(s=s_0, s_1, \dots s_n=t\) soit la chaîne simple la plus longue possible dans \(T\text{.}\) Une telle chaîne doit nécessairement exister, car le nombre d’arêtes est fini.

🔗

Puisque \(s_{n-1}\) est un voisin de \(t\text{,}\) on a que \(\deg(t)\geq 1\text{.}\) On veut montrer que P\(\deg(t)=1\text{.}\) Supposons le contraire, alors \(t\) possède un voisin différent de \(s_{n-1}\) et de \(s_n\text{.}\) Celui-ci doit aussi être différent de \(s_i\text{,}\) \(i=0, 1, \dots n-2\text{,}\) car sinon on obtiendrait un cycle dans \(T\text{.}\) Notons ce voisin \(s_{n+1}\text{.}\) On a alors que \(s_0, s_1, \dots s_{n}, s_{n+1}\) est une chaîne simple de longueur \(n+1\text{.}\) Ceci est une contradiction, car on avait supposé que la chaîne simple la plus longue était de longueur \(n\text{.}\) On doit donc avoir \(\deg(t)=1\text{.}\)

🔗

Par le même argument, on peut montrer que \(\deg(s)=1\text{.}\) Ainsi, on a trouvé au moins deux sommets de degré \(1\text{.}\)

🔗

Cette proposition nous pousse donc à donner un nom aux sommets de degré \(1\text{,}\) ainsi qu’aux sommets de degré plus grand que \(1\text{.}\)

🔗

Définition 7.4.5.

Soit \(T=(S,A)\) un arbre et soit \(s\in S\) un sommet quelconque.

On dit que \(s\) est une feuille de l’arbre \(T\) si \(\deg(s)=1\text{.}\)
🔗

🔗
On dit que \(s\) est un sommet interne, ou bien une branche de l’arbre \(T\) si \(\deg(s)>1\text{.}\)
🔗

🔗

🔗

Proposition 7.4.6.

Soit \(T=(S,A)\) un arbre, alors \(|S|=|A|+1\text{.}\)

🔗

Démonstration.

On procède par induction sur \(|A|\text{.}\) C’est-à-dire qu’on suppose que \(|A|=n\text{,}\) et on montre par induction que \(|S|=n+1\text{.}\)

🔗

ÉTAPE DE BASE: Pour \(n=0\text{,}\) alors \(T\) ne possède aucune arête. Puisque \(T\) est un graphe connexe, on doit nécessairement avoir \(|S|=1\text{.}\) Ainsi, on a bien \(|S|=n+1=0+1=1\text{.}\)

🔗

ÉTAPE D’INDUCTION: On suppose que si un arbre quelconque possède \(k\) arêtes, pour \(k\geq 0\text{,}\) alors cet arbre possède \(k+1\) sommets. (H.I.)

🔗

Soit \(T=(S,A)\) avec \(|A|=k+1\text{,}\) on veut montrer, à l’aide de l’H.I. que \(|S|=(k+1)+1=k+2\text{.}\) Puisque \(k\geq 0\text{,}\) alors \(|A|=k+1\geq 1\text{.}\) Si \(T\text{,}\) possède au moins une arête, alors \(T\) possède au moins deux sommets, c’est-à-dire que \(|S|\geq 2\text{.}\) Ainsi, par 7.4.4, on sait qu’il existe au moins deux sommets de degré \(1\text{.}\) Soit \(s_0\in S\) tel que \(\deg(s_0)=1\) et \(s_1\) l’unique voisin de \(s_0\text{.}\) On remarque que si une chaîne simple contient l’arête \(\{s_0,s_1\}\text{,}\) alors elle commence (ou termine) nécessairement par cette arête, puisque \(\deg(s_0)=1\text{.}\)

🔗

On pose donc \(T_0==(S-\{s_0\},A-\{s_0,s_1\})\text{,}\) c’est-à-dire que \(T_0\) est l’arbre obtenu en enlevant l’arête \(\{s_0,s_1\}\) et le sommet \(s_0\) à \(T\text{.}\) Ainsi, \(|A-\{s_0,s_1\}|=k\) et \(|S-\{s_0\}|=|S|-1\text{.}\) Par hypothèse d’induction, on a \(|S-\{s_0\}|=k+1\text{,}\) d’où \(|S|=(k+1)+1=k+2\text{.}\)

🔗

On a montré que si \(|A|=0\text{,}\) alors \(|S|=0+1=1\text{.}\) De plus, on a montré que si on suppose que \(|A|=k\) implique que \(|S|=k+1\) pour un certain \(k\geq 0\text{,}\) alors \(|A|=k+1\) implique \(|S|=k+2\text{.}\) Par le principe d’induction, on a donc bien montré que si \(|A|=n\text{,}\) alors \(|S|=n+1\) pour tout entier \(n\geq 0\text{.}\)

🔗

Sous-section 7.4.2 Arbre couvrant

Lorsqu’on conçoit des algorithmes concernant les graphes, il est souvent utile d’avoir une méthode afin de nous assurer de parcourir l’ensemble des sommets de façon systématique. Une méthode pour accomplir cette tâche est de parcourir les sommets de notre graphe à l’aide d’un arbre couvrant.

🔗

Définition 7.4.7.

Soit \(G=(S,A)\) un graphe simple connexe. Un arbre couvrant de \(G\) est un sous-graphe \(T=(S,A_0)\) tel que \(T\) est un arbre. Ainsi, un arbre couvrant de \(G\) est un arbre ayant les mêmes sommets que \(G\text{.}\)

🔗

Pour pouvoir démontrer la proposition 7.4.10, on a besoin d’un résultat intermédiaire. Puisque le résultat sert principalement à démontrer une proposition plus importante, on dira qu’il s’agit d’un lemme.

🔗

Lemme 7.4.8.

Soit \(G=(S,A)\) un graphe connexe. Supposons que \(s_0, s_1, \dots, s_{n-1}, s_0\) soit un cycle simple de longueur \(n\) dans \(G\text{.}\) Le graphe \(G_0=G-\{s_0,s_{n-1}\}\) est aussi un graphe connexe. Pour ce faire, on devra utiliser le fait que la chaîne \(s_0, s_1, \dots s_{n-1}\) est une chaîne de \(G_0\) reliant \(s_0\) et \(s_{n-1}\text{.}\)

🔗

Démonstration.

Soit \(s, t\in S\text{,}\) puisque \(G\) est connexe, on sait qu’il y a une chaîne simple reliant \(s\) et \(t\text{.}\) Si cette chaîne ne passe pas par \(\{s_0, s_{n-1}\}\text{,}\) alors cette chaîne est aussi une chaîne de \(G_0\text{.}\) Si cette chaîne passe par \(s_0, s_{n-1}\text{,}\) alors on peut écrire cette chaîne de la façon suivante.

🔗

On a \(s= t_0, t_1, \dots, t_{i-1}, t_{i}, t_{i+1}, t_{i+2}, \dots, t_{m}=t \text{,}\) avec \(t_{i}=s_0\) et \(t_{i+1}=s_{n-1}\text{.}\) Mais alors on sait qu’il y a une chaîne de \(G_0\) entre \(t_0=s\) et \(t_{i}\text{,}\) qu’il y a une chaîne de \(G_0\) entre \(t_i=s_0\) et \(t_{i+1}=s_{n-1}\) et qu’il y a une chaîne de \(G_0\) entre \(t_{i+1}\) et \(t_{m}=t\text{.}\) Ainsi, par l’exercice 7.3.5.2, il y a une chaîne entre \(s\) et \(t\) dans \(G_0\text{.}\)

🔗

On a montré qu’il existe une chaîne de \(G_0\) entre chaque paire de sommets, c’est-à-dire que \(G_0\) est connexe.

🔗

Exemple 7.4.9.

On montre un cas particulier du lemme précédent pour bien visualiser. Soit \(G\) le graphe ci-dessous, et \(G_1\) le graphe obtenu de \(G\) en enlevant l’arête \(\{1, 2\}\) de \(G\text{.}\) On remarque que la chaîne \(0, 1, 2, 3\) est une chaîne de \(G\) reliant \(0\) avec \(3\text{.}\) Puisque \(G_1\) ne possède pas l’arête \(\{1,2\}\text{,}\) cette chaîne n’est pas une chaîne de \(G_1\text{.}\) Cependant, puisque \(\{1,2\}\) fait parti d’un cycle dans \(G\text{,}\) on remarque que la chaîne \(0,1,4,5,6,7,2,3\) et une chaîne de \(G_1\) reliant \(0\) et \(3\text{.}\)

🔗

Proposition 7.4.10.

Soit \(G=(S,A)\) un graphe simple connexe, alors \(G\) possède un arbre couvrant \(T\text{.}\)

🔗

Démonstration.

On construit une suite \(G_k=(S,A_k)\) de sous-graphe de \(G\) par récurrence, c’est-à-dire qu’on définit \(G_0\text{,}\) et ensuite, ayant défini \(G_k=(S,A_k)\) pour \(k\geq 0\text{,}\) on définit \(G_{k+1}\text{.}\) On va continuer le processus jusqu’à ce que le graphe obtenu soit un arbre. Ce processus se terminera nécessairement en un nombre fini d’étape, disons \(n\) étapes. À la fin, on posera \(T=G_n\text{.}\)

🔗

On pose \(G_0=G\text{.}\) Ensuite, on suppose qu’on a défini \(G_k=(S,A_k)\) un graphe simple connexe pour \(k\geq 0\text{.}\) Si \(G_k\) est un arbre, alors il s’agit d’un arbre couvrant pour \(G\text{,}\) et on a terminé. Si au contraire \(G_k\) n’est pas un arbre, on doit définir \(G_{k+1}\) un graphe simple connexe contenant une arête de moins que \(G_k\text{.}\)

🔗

Puisque \(G_k\) n’est pas un arbre, \(G_k\) possède un cycle, disons le cycle \(s_0, s_1, \dots, s_{m-1}, s_m\text{,}\) avec \(s_{m}=s_0\text{.}\) On pose alors \(G_{k+1}=(S,A_{k+1}):= G_k-\{s_{m-1}, s_m\}=(S,A_k-\{s_{m-1},s_m\})\text{.}\) Le graphe obtenu est donc un graphe avec les mêmes sommets que \(G\text{,}\) possédant une arête de moins que le graphe \(G_k\text{.}\) On doit vérifier qu’il s’agit toujours de graphe connexe. Or, par le lemme 7.4.8, on sait que \(G_{k+1}\) est connexe.

🔗

Puisqu’on enlève une arête à chaque étape, et que le nombre d’arêtes de \(G\) est fini, on doit nécessairement arriver à un point où \(G_k\) ne possède pas de cycle. Si le processus se termine avec \(k=n\text{,}\) alors on pose \(T=G_n\text{.}\) Puisque \(T\) possède les mêmes sommets que \(G\text{,}\) est connexe et ne possède aucun cycle. \(T\) est donc bien un arbre couvrant de \(G\text{.}\)

🔗

Sous-section 7.4.3 Arborescence

Un exemple classique d’utilisation des arbres est les arbres généalogiques. Une façon de représenter un arbre généalogique est de commencer par un ancêtre commun de la famille, qu’on représente par un sommet, et de relier ce sommet par une arête à un sommet représentant chacun des enfants de cette personne. Par la suite, on ajoute un sommet pour chaque enfant de la génération suivante, reliant les enfants à leur parent.

🔗

On veut utiliser cette idée afin de représenter les arbres, c’est-à-dire qu’on choisira un sommet pour être l’ancêtre de tous les autres sommets. Ceci permettra de donner un certain ordre à nos arbres. Pour chaque sommet, on pourra considérer l’unique chaîne simple le reliant à l’ancêtre commun. La longueur de cette chaîne représentera en quelque sorte la génération à laquelle chaque sommet appartient.

🔗

Cette représentation est très utile lorsqu’on veut représenter un arbre de décision, c’est-à-dire un arbre permettant de répondre à un problème particulier. En effet, cette représentation nous permettra de donner une longueur minimale associée à notre arbre de décision. Ceci servira à vérifier si l’algorithme utilisé peut être optimisé, ou bien s’il s’agit déjà de l’algorithme le plus efficace.

🔗

La combinaison d’un arbre et de notre ancêtre commun est ce qu’on appelle une arborescence. Ainsi, une arborescence n’est rien d’autre qu’un arbre pour lequel on a choisi un sommet particulier.

🔗

Définition 7.4.11.

Une arborescence est une paire \((T,r)\) où \(T=(S,A)\) est un arbre et \(r\in S\) est un sommet de \(T\text{.}\) On appellera \(r\) la racine de \(T\text{.}\)

🔗

Si \((T,r)\) est une arborescence, puisque \(T\) est un arbre, pour tout sommet \(s\) de \(T\text{,}\) il existe une unique chaîne simple entre \(r\) et \(s\text{.}\) Ceci nous permet de donner les définitions suivantes.

🔗

Définition 7.4.12.

Soit \((T,r)\) une arborescence et soit \(s\) un sommet de \(T\text{.}\) On note l’unique chaîne entre de \(T\) entre \(s\) par \(r=s_0, s_1, \dots , s_{n}=s\)

🔗

Le niveau du sommet \(s\) est la longueur de la chaîne \(s_0, \dots s_n\text{,}\) c’est-à-dire \(n\text{.}\)
🔗

🔗
Le plus grand niveau de l’arborescence \(T\) est appelé la hauteur de \(T\text{.}\)
🔗

🔗
Les sommets \(s_0, s_1, \dots, s_{n-1}\) sont appelés les ancêtres de \(s\text{.}\) À l’inverse, on dira que \(s\) est un descendant des sommets \(s_0, s_1, \dots, s_{n-1}\text{.}\)
🔗

🔗
Le sommet \(s_{n-1}\) est appelé le parent de \(s\text{,}\) alors qu’on dira que \(s\) est l’enfant de \(s_{n-1}\)
🔗

🔗

🔗

Questions de compréhension de la lecture 7.4.4 Questions de compréhension de la lecture

Ces questions sont à faire avant de venir en classe et à remettre au début du cours.

🔗

1.

Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.

🔗

Précédent TopSuivant