t

[cours-maths-dis.git] / graphes / arbres.tex

\section{Présentation générale}

\subsection{Définitions}

\begin{Def}[Arbre, feuilles]
On nomme \emph{arbre}\index{arbre} un graphe non orienté connexe et acyclique (sa forme évoque en effet la ramification des branches d'un arbre). On distingue deux types de sommets dans un arbre
\begin{itemize}
 \item les \emph{feuilles}\index{feuilles} dont le degré est 1;
\item les \emph{n{\oe}uds internes}\index{noeuds} dont le degré est supérieur à 1.
\end{itemize}
\end{Def}

\begin{Ex}
Un exemple d'arbre :
\begin{center}
\includegraphics[scale=0.7]{graphes/arbre1.eps}
\end{center}
\end{Ex}



%\begin{Rem}
%D'autres définitions équivalentes sont possibles. Par exemple :

%\begin{description}
%\item[basée sur le nombre d'arêtes : ] un arbre est un graphe connexe non orienté possédant \textit{n} $-$ 1 arêtes.
%\item[inductive.]
%\end{description}
%\end{Rem}


\begin{Def}[Forêt]
Un graphe sans cycles mais non connexe est appelé une \emph{forêt}\index{forêt}.
\end{Def}

\begin{Ex}
Un exemple de forêt :
\begin{center}
\includegraphics[scale=0.7]{graphes/foret.eps}
\end{center}
\end{Ex}


\subsection{Caractérisation des arbres}

\begin{Th}\label{prop:equiv}
Les affirmations suivantes sont équivalentes pour tout graphe $G = (V, E)$ à $n$ sommets.
\begin{enumerate}
\item $G$ est un arbre,
\item $G$ est sans cycles et connexe,
\item $G$ est sans cycles et comporte $n-1$ arêtes,
\item $G$ est connexe et comporte $n-1$ arêtes,
\item Chaque paire $(u, v)$ de sommets distincts est reliée par une seule chaîne simple (et le graphe est sans boucles).
\end{enumerate}
\end{Th}


\subsection{Nombre minimal de feuilles}

\begin{Th}
Tout arbre fini avec au moins deux sommets comporte au moins deux feuilles.
\end{Th}

\subsection{Exercices}
\begin{Exo}
Démontrez la propriété précédente.
\end{Exo}

\noindent{\underline{\textit{Indication : }}} Récurrence.

\begin{Exo}
Combien d'arbres différents existe-t-il avec 3, 4, 5 sommets ?
\end{Exo}

\noindent{\underline{\textit{Indication : }}} Réfléchir sur le nombre de feuilles.

\begin{Exo}
Un arbre $T$ a trois sommets de degré 3, quatre sommets de degré 2. Les autres sommets sont tous de degré 1 (des feuilles). Combien y a-t-il de sommets de degré 1?
\end{Exo}

\noindent{\underline{\textit{Réponse : }}} Soit $n$ le nombre total de sommet ; il y a donc $n-1$ arêtes, et $n-3-4 = n-7$ sommets de degré 1. Comptons le nombre d'arêtes...
Chaque sommet partage son arête avec un autre sommet, donc :
\begin{itemize}
\item chaque sommet de degré trois (il y en a 3) a 1,5 arête \og à lui \fg{},
\item chaque sommet de degré deux (il y en a 4) a 1 arête \og à lui \fg{},
\item chaque sommet de degré un (il y en a $n-7$) a 0,5 arête \og à lui \fg{}
\end{itemize}
Ce qui fait un total d'arêtes de $3*1,5+4*1+(n-7)*0,5$. Or, comme on a affaire à un arbre à $n$ sommets, on a $n-1$ arêtes, donc $$3*1,5+4*1+(n-7)*0,5 = n-1$$
\noindent d'où $n=12$, et il y a 5 sommets de degré 1.


\begin{Exo}
Soit un graphe $G$.
Supposons qu'il y ait deux chaînes élémentaires distinctes $P_1$ et
$P_2$ d'un sommet $s$ à un autre sommet $s'$ de $G$. $G$ est-il un
arbre? Justifier par une preuve.
%Seymour Lipschutz 6.14 p 113
\end{Exo}

\section{Codage de Prüfer}


\subsection{Présentation}
Le codage de Prüfer est une manière très compacte de décrire un arbre.

\subsection{Codage}

\subsubsection{La méthode}

Soit l'arbre $T = (V, E)$ et supposons $V = {1, 2, ..., n}$.
L'algorithme ci-dessous fournira le code de $T$, c'est-à-dire une suite $S$ de
$n-2$ termes employant (éventuellement plusieurs fois) des nombres choisis parmi
$\{1, ..., n\}$.

\begin{Th}[Pas général de l'algorithme de codage]
Initialement la suite $S$ est vide.
Ce pas général est à répéter tant qu'il reste plus de
deux sommets dans l'arbre courant $T$ :
\begin{itemize}
\item identifier la feuille $v$ de l'arbre courant ayant le numéro minimum ;
\item ajouter à la suite $S$ le seul sommet $s$ adjacent à $v$ dans l'arbre $T$ courant ;
\item enlever de l'arbre $T$ courant la feuille $v$ et l'arête incidente à $v$.
\end{itemize}
\end{Th}

\subsubsection{Exemple de codage}

\begin{description}
\item[\'Etape 0 :] arbre à coder

\begin{center}
\includegraphics[scale=0.7]{graphes/prufer1.eps}
\end{center}

1: 4

2: 10

3: 6, 8

4: 1, 5, 7, 8

5: 4, 10

6: 3

7: 4

8: 3, 4

9: 10

10: 2, 5, 9

\item[\'Etape 1 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/prufer2.eps}
\end{center}

2: 10

3: 6, 8

4: 5, 7, 8

5: 4, 10

6: 3

7: 4

8: 3, 4

9: 10

10: 2, 5, 9

\begin{center}S=\{4\}\end{center}


\item[\'Etape 2 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/prufer3.eps}
\end{center}

3: 6, 8

4: 5, 7, 8

5: 4, 10

6: 3

7: 4

8: 3, 4

9: 10

10: 5, 9

\begin{center}S=\{4,10\}\end{center}

\item[\'Etape 3 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/prufer4.eps}
\end{center}

3: 8

4: 5, 7, 8

5: 4, 10

7: 4

8: 3, 4

9: 10

10: 5, 9

\begin{center}S=\{4,10,3\}\end{center}

\item[\'Etape 4 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/prufer5.eps}
\end{center}

4: 5, 7, 8

5: 4, 10

7: 4

8: 4

9: 10

10: 5, 9

\begin{center}S = \{4,10,3,8\}\end{center}

\item[\'Etape 5 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/prufer6.eps}
\end{center}

4: 5, 8

5: 4, 10

8: 4

9: 10

10: 5, 9


\begin{center}S = \{4,10,3,8,4\}\end{center}

\item[\'Etape 6 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/prufer7.eps}
\end{center}

4: 5

5: 4, 10

9: 10

10: 5, 9

\begin{center}S = \{4,10,3,8,4,4\}\end{center}

\item[\'Etape 7 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/prufer8.eps}
\end{center}

5: 10

9: 10

10: 5, 9

\begin{center}S = \{4,10,3,8,4,4,5\}\end{center}

\item[\'Etape 8 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/prufer9.eps}
\end{center}

9: 10

10: 9

\begin{center}S = \{4,10,3,8,4,4,5,10\}\end{center}

\item[\'Etape 9 :] S = \{4,10,3,8,4,4,5,10\} est le codage de Prüfer de l'arbre initial.

\end{description}


\subsection{Décodage}

\subsubsection{La méthode}
\begin{description}
\item[Donnée :] suite $S$ de $n-2$ nombres, chacun provenant de \{1, ..., n\}.

Posons $I = \{1, ..., n\}$.

\item[Pas général de l'algorithme de décodage :]
à répéter tant qu'il reste des éléments dans $S$ et plus de deux éléments dans $I$ :
\begin{itemize}
\item identifier le plus petit élément $i$ de $I$ n'apparaissant pas dans la suite $S$ ;
\item relier par une arête de $T$ le sommet $i$ avec le sommet $s$ correspondant au premier élément de la suite $S$ ;
\item enlever $i$ de $I$ et $s$ de $S$.
\end{itemize}

\item[Finalisation :] Les deux éléments qui restent dans I à la fin de l'algorithme constituent les extrémités de la dernière arête à ajouter à T.
\end{description}


\subsubsection{Exemple de décodage}


\begin{description}
\item[\'Etape 0 :] arbre à décoder

\begin{center}
\includegraphics[scale=0.7]{graphes/deprufer1.eps}


I=\{1,2,3,4,5,6,7,8,9,10\}

S=\{4,10,3,8,4,4,5,10\}
\end{center}



\item[\'Etape 1 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/deprufer2.eps}
\end{center}

1: 4

4: 1


\begin{center}
I=\{2,3,4,5,6,7,8,9,10\}

S=\{10,3,8,4,4,5,10\}
\end{center}


\item[\'Etape 2 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/deprufer3.eps}
\end{center}

1: 4

2: 10

4: 1

10: 2

\begin{center}
I=\{3,4,5,6,7,8,9,10\}

S=\{3,8,4,4,5,10\}

\end{center}

\item[\'Etape 3 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/deprufer4.eps}
\end{center}

1: 4

2: 10

3: 6

4: 1

6: 3

10: 2


\begin{center}
I=\{3,4,5,7,8,9,10\}

S=\{8,4,4,5,10\}
\end{center}

\item[\'Etape 4 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/deprufer5.eps}
\end{center}

1: 4

2: 10

3: 6, 8

4: 1

6: 3

8: 3

10: 2


\begin{center}
I=\{4,5,7,8,9,10\}

S=\{4,4,5,10\}
\end{center}

\item[\'Etape 5 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/deprufer6.eps}
\end{center}

1: 4

2: 10

3: 6, 8

4: 1, 7

6: 3

7: 4

8: 3

10: 2

\begin{center}
I=\{4,5,8,9,10\}

S=\{4,5,10\}

\end{center}

\item[\'Etape 6 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/deprufer7.eps}
\end{center}

1: 4

2: 10

3: 6, 8

4: 1, 7, 8

6: 3

7: 4

8: 3, 4

10: 2

\begin{center}
I=\{4,5,9,10\}

S=\{5,10\}
\end{center}

\item[\'Etape 7 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/deprufer8.eps}
\end{center}

1: 4

2: 10

3: 6, 8

4: 1, 5, 7, 8

5: 4

6: 3

7: 4

8: 3, 4

10: 2

\begin{center}
I=\{5,9,10\}

S=\{10\}
\end{center}

\item[\'Etape 8 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/deprufer9.eps}
\end{center}

1: 4

2: 10

3: 6, 8

4: 1, 5, 7, 8

5: 4, 10

6: 3

7: 4

8: 3, 4

10: 2, 5


\begin{center}
I=\{9,10\}

S=\{\}
\end{center}

\item[\'Etape 9 :]

\begin{center}
\includegraphics[scale=0.7]{graphes/deprufer10.eps}
\end{center}

1: 4

2: 10

3: 6, 8

4: 1, 5, 7, 8

5: 4, 10

6: 3

7: 4

8: 3, 4

9: 10

10: 2, 5, 9

\begin{center}
I=\{\}

S=\{\}
\end{center}


\end{description}




\begin{Exo}
Décrivez l'arbre ci-dessous à l'aide du codage de Prüfer.
\begin{center}
\includegraphics[scale=0.7]{graphes/arbre123.eps}
\end{center}
\end{Exo}







\begin{Exo}
Dessinez l'arbre correspondant à la suite S=\{1,1,1,1,1,1,1,1,1\}.
\end{Exo}

\begin{Exo}
Dessinez l'arbre correspondant à la suite S=\{1,2,3,4,5,6,7,8\}.
\end{Exo}



\subsection{Théorème de Cayley}

\begin{Th}[Cayley, 1857]
Le nombre d'arbres que l'on peut construire sur $n$ ($n>1$) sommets numérotés est égal à $n^{n-2}$.
\end{Th}

\begin{Pre}
La preuve est immédiate en utilisant le codage de Prüfer.

En effet, on vérifie aisément que les deux algorithmes constituent les deux sens d'une bijection entre les arbres sur n sommets numérotés et les mots de $n-2$ lettres sur l'alphabet à $n$ lettres.

Ce constat permet de conclure la preuve du théorème de Cayley. En effet, il existe $n^{n-2}$ mots de longueur $n-2$ sur l'alphabet à $n$ lettres, donc d'arbres sur $n$ sommets numérotés.
\end{Pre}

\section{Arbres couvrants}

\subsection{Définition}

\begin{Def}[Arbre couvrant]
 Un \emph{arbre couvrant}\index{arbre!couvrant}
 (ou \emph{arbre maximal}\index{arbre!maximal}) d'un graphe G, est un graphe partiel de G qui est aussi un arbre.
\end{Def}

\begin{Rem}
On rappelle qu'un graphe partiel de G est obtenu en enlevant des arêtes (mais pas de sommets) à G.
\end{Rem}

\begin{Ex}
Un des arbres couvrants (en bleu) d'un graphe donné.
\begin{center}
\includegraphics[scale=0.7]{graphes/couvrant.eps}
\end{center}
\end{Ex}

\subsubsection{Exercices}
\begin{Exo}
Dessiner des arbres couvrants pour chacun des graphes suivants.
\begin{center}
\includegraphics[scale=0.7]{graphes/ex1.eps}
\includegraphics[scale=0.7]{graphes/ex2.eps}
\includegraphics[scale=0.7]{graphes/ex3.eps}
\end{center}

\end{Exo}

\begin{Exo}
Combien d'arbres couvrants différents les graphes ci-dessus possèdent-ils ?
\end{Exo}


\subsection{Arbre maximal de poids minimum}
\subsubsection{Présentation du problème}

On considérera le problème suivant :

\og Soit le graphe $G = (V, E)$ avec un poids associé à
chacune de ses arêtes. Trouver, dans $G$, un arbre maximal
$A = (V, F)$ de poids total minimum.\fg{}


Ce problème se pose, par exemple, lorsqu'on désire relier $n$ villes par un réseau routier de coût minimum.
Les sommets du graphe représentent les villes, les arêtes, les tronçons qu'il est possible de construire et les poids des arêtes correspondent aux coûts de construction du tronçon correspondant.

L'algorithme de Kruskal décrit ci-dessous permet de résoudre ce problème.


\subsubsection{L'algorithme de Kruskal}

Voici un algorithme célèbre permettant de résoudre ce problème :

%\begin{Th}[L'algorithme de Kruskal]

%\begin{description}
%\item[Données :] Graphe $G = (V, E)$ ($|V| = n$, $|E| = m$) et pour chaque arête $e$ de $E$, son poids $c(e)$.
%\item[Résultat :] Arbre ou forêt maximale $A = (V, F)$ de poids minimum.
%\item[Algorithme :] Trier et renuméroter les arêtes de G dans l'ordre croissant de leur poids : $c(e_1) < c(e_2) < ... < c(e_m)$.
%\begin{enumerate}
%\item Poser $F := \varnothing$, $k := 0$
%\item Tant que $k < m$ et $|F| < n-1$ faire
%\begin{itemize}
%\item Début
%\begin{itemize}
%\item si $e_{k+1}$ ne forme pas de cycle avec $F$ alors $F := F \cup \{e_{k+1}\}$
%\item $k := k+1$
%\end{itemize}
%\item Fin
%\end{itemize}
%\end{enumerate}
%\end{description}
%\end{Th}

\begin{Th}[L'algorithme de Kruskal]
\index{Algorithme!de Kruskal}\index{Kruskal (algorithme)}
Pour obtenir un arbre ou une forêt couvrant(e) de poids minimum à partir d'un graphe pondéré $G = (S,A)$, on procède comme suit :
\begin{enumerate}
\item On part du graphe $G' = (S, \varnothing)$ ($G$ sans arête).
\item Tant que le nombre d'arêtes de $G'$ est inférieur à $min(|G|-1,|A|)$, faire
\begin{itemize}
\item Prendre la plus petite arête (de poids minimal) restante dans $G$.
\item L'ajouter à $G'$ si cela ne crée pas de cycle.
\item La supprimer de $G$.
\end{itemize}
\end{enumerate}
\end{Th}




\begin{Exo}
Le tableau suivant donne les coûts de construction de routes (exprimées en unités adéquates) entre six villes d'Irlande.

\begin{center}
\begin{tabular}{l|cccccc}
         & Athlone & Dublin & Galway & Limerick & Sligo & Wexford \\
\hline
Athlone & -%Athlone
& 78 %Dublin
& 56 %Galway
& 73 %Limerick
& 71 %Sligo
& 114 \\ %Wexford
Dublin %
& -%Athlone
& -%Dublin
& 132%Galway
& 121%Limerick
& 135%Sligo
& 96 \\%Wexford \\
Galway %
& -%Athlone
& -%Dublin
& -%Galway
& 64%Limerick
& 85%Sligo
& 154\\%Wexford \\
Limerick %
& -%Athlone
& -%Dublin
& -%Galway
& -%Limerick
& 144%Sligo
& 116\\%Wexford \\
Sligo %
& -%Athlone
& -%Dublin
& -%Galway
& -%Limerick
& -%Sligo
& 185%Wexford
\end{tabular}
\end{center}

Trouver une manière de relier ces six villes, en minimisant le coût total de construction.
\end{Exo}



\begin{Exo}
Faire de même avec le tableau suivant, qui comptabilise cette fois-ci les kilomètres entre chaque ville (valeurs imaginaires) :
\begin{center}
\begin{tabular}{l|cccccc}
         & Athlone & Dublin & Galway & Limerick & Sligo & Wexford \\
\hline
Athlone & -%Athlone
& 121 %Dublin
& 95 %Galway
& 43 %Limerick
& 71 %Sligo
& 74 \\ %Wexford
Dublin %
& -%Athlone
& -%Dublin
& 72%Galway
& 98%Limerick
& 115%Sligo
& 97 \\%Wexford \\
Galway %
& -%Athlone
& -%Dublin
& -%Galway
& 64%Limerick
& 77%Sligo
& 134\\%Wexford \\
Limerick %
& -%Athlone
& -%Dublin
& -%Galway
& -%Limerick
& 144%Sligo
& 126\\%Wexford \\
Sligo %
& -%Athlone
& -%Dublin
& -%Galway
& -%Limerick
& -%Sligo
& 85%Wexford
\end{tabular}
\end{center}
\end{Exo}



\section{Arborescence}

\subsection{Définitions et exemples}

\subsubsection{Définition d'une arborescence}

\begin{Def}[Arborescence]
On appelle \emph{arborescence}\index{arborescence} un arbre avec un sommet distingué, que l'on appelle la racine.
\end{Def}

\begin{Notation}
On représente généralement une arborescence avec la racine en haut du dessin et les feuilles en bas.
\end{Notation}

\subsubsection{Exemples}

\begin{Ex}
Sur l'arborescence ci-dessous, la racine est le sommet 4. Les sommets 5, 6, 7 et 9 sont les feuilles.
\begin{center}
\includegraphics[scale=0.7]{graphes/arbo1.eps}
\end{center}
\end{Ex}

\begin{Ex}
Les systèmes de fichiers ($ext3$ sous linux, $ntfs$ sous windows, etc.) sont agencés en arborescence.
\end{Ex}


\subsubsection{Rang des sommets}


On peut, dans une arborescence, assigner un rang aux sommets :

\begin{Def}[Rang d'un sommet]
Le \emph{rang}\index{sommet!rang} d'un sommet d'une arborescence est la distance de ce sommet à la racine.
\end{Def}


\begin{Ex}
Ainsi, dans l'exemple précédent, le sommet 4 (la racine) a rang 0, le sommet 1 a rang 1, les sommets 2 et 10 ont rang 2, les sommets 3, 5 et 8 ont rang 3 et les sommets 6, 7 et 9 ont rang 4.
\end{Ex}

\begin{Def}[Hauteur d'une arborescence]
On dira que la \emph{hauteur} \index{arborescence!hauteur} de l'arborescence est le rang maximum
\end{Def}

\begin{Ex}
L'exemple ci-dessus a une hauteur de 4.
\end{Ex}


\subsection{Arborescences ordonnées, parcours en largeur et profondeur}

\subsubsection{Arborescences ordonnées}

\begin{Def}[Arborescence ordonnée]
Une \emph{arborescence ordonnée}\index{arborescence!ordonnée} est une arborescence dont les arêtes partant de chaque sommet sont ordonnées.
\end{Def}

Une fois qu'une arborescence a été ordonnée, il existe alors une représentation graphique canonique, la seule qui respecte cet ordre, de telle sorte que, pour chaque arête,
\begin{itemize}
\item elle possède à sa gauche des arêtes plus petites (pour l'ordre considéré), et à sa droite de plus grandes arêtes,
\item au-dessus d'elle, les arêtes sont plus petites pour l'ordre, et plus grandes en-dessous d'elles.
\end{itemize}

En d'autres termes, on va dans le sens des arêtes croissantes quand on parcourt cette représentation canonique :
\begin{itemize}
\item de la gauche vers la droite,
\item ou du haut vers le bas.
\end{itemize}


Il est donc possible de parler, sans ambiguïté, de droite et gauche, de haut et bas, pour une arborescence ordonnée.


\begin{Rem}
Une manière détournée d'ordonner une arborescence consiste à en donner une représentation graphique, et à considérer cette dernière comme canonique.
\end{Rem}


On peut étiqueter sans ambiguïté les sommets d'une arborescence ordonnée, comme suit :
\begin{itemize}
\item on attribue 0 à la racine $r$,
\item puis 1, 2, 3, ... aux sommets qui sont adjacents à $r$, en respectant l'ordre des arêtes issues de la racines.
\item Les étiquettes suivantes sont constituées de l'étiquette du sommet "père", suivie d'un chiffre obtenu comme précédemment.
\item Ainsi, les sommets "fils" attachés au sommet 2 seront numérotés 2.1, 2.2, 2.3,...
\end{itemize}


\begin{Ex}
La figure ci-dessous illustre le procédé.
\begin{center}
\includegraphics[scale=0.7]{graphes/ordo.eps}
\end{center}
\end{Ex}


\begin{Exo}
\'Etiqueter les sommets de l'arborescence ordonnée dont la représentation canonique est la suivante :
\begin{center}
\includegraphics[scale=0.7]{graphes/arbo1.eps}
\end{center}
\end{Exo}

\begin{Def}
Cet ordre des sommets (0, 1, 1.1, 1.2, 2, 2.1, 3, 3.1, 3.1.1, 3.1.2, 3.2, 3.3) est appelé \emph{ordre lexicographique}, puisqu'il est semblable au classement des mots dans un dictionnaire.
\end{Def}



\subsubsection{Parcours en largeur, en profondeur}

\paragraph{Définition des parcours}

\begin{Def}[Parcours en largeur, en profondeur]
Dans le cas du parcours d'une arborescence en suivant l'ordre lexicographique, on parle de \emph{parcours en profondeur}\index{parcours!en profondeur} de l'arborescence, par opposition au \emph{parcours en largeur}\index{parcours!en largeur} qui serait l'ordre: 0, 1, 2, 3, 1.1, 1.2, 2.1, 3.1, 3.2, 3.3, 3.1.1, 3.1.2.
\end{Def}

Le parcours en largeur consiste à visiter les sommets d'une arborescence ordonnée ligne par ligne, de la gauche vers la droite, les lignes étant parcourues du haut vers le bas.



Le parcours en profondeur, par contre, correspond à parcourir de haut en bas la branche la plus à gauche de l'arbre, puis la branche immédiatement à droite, et ainsi de suite jusqu'à la branche la plus à droite.



\begin{Rem}
Chaque sommet n'apparaît qu'une fois dans ce parcours : le but d'un parcours étant justement de visiter une et une seule fois chaque sommet. 

Un cas concret pourrait être la réalisation récursive d'un traitement pour chaque répertoire d'une arborescence : on souhaite visiter chaque répertoire une et une seule fois.
\end{Rem}



\paragraph{Exercices.}


\begin{Exo}
Donner la liste ordonnée des sommets visités lors d'un parcours en largeur, et d'un parcours en profondeur, dans l'arborescence suivante :
\begin{center}
\includegraphics[scale=0.7]{graphes/arbo1.eps}
\end{center}
\end{Exo}


\begin{Exo}
Réfléchir à un algorithme de parcours en largeur d'une arborescence ordonnée.
\end{Exo}

\subsubsection{Lien avec les expressions algébriques}

\paragraph{Arborescence d'une expression algébrique.}

N'importe quelle expression algébrique comprenant des expressions binaires, telle que l'addition, la soustraction, la multiplication et la division, peut être représentée par une arborescence ordonnée.

\begin{Ex}
Par exemple, l'aborescence ci-dessous représente l'expression arithmétique
$(a - b) / ((c \times d) + e)$:
\begin{center}
\includegraphics[scale=0.7]{graphes/polonais.eps}
\end{center}
\end{Ex}


On observe que les variables de l'expression ($a, b, c, d$ et $e$)
 sont les feuilles de l'arborescence, et que les opérations sont les autres sommets.

\begin{Rem}
L'arbre doit être ordonné car $a-b$ et $b-a$, qui ne sont pas égaux,  conduisent au même arbre, mais pas au même arbre ordonné.
\end{Rem}

\begin{Exo}
Construire les arborescences associées aux expressions algébriques : $(a+b)*(c-(d-e))$ et $((a/b)*c)-(d-e)$.
\end{Exo}

\paragraph{Notation polonaise.}

Le mathématicien polonais \emph{Lukasiewicz} \index{Lukasiewicz} a remarqué qu'en plaçant les symboles des opérations binaires avant les arguments, c'est-à-dire $+ ab$ au lieu de $a+b$ ou $/ cd$
 au lieu de $c/d$, nous n'avions plus besoin de parenthèses\ldots

\begin{Def}[Notation polonaise]
On appelle cette nouvelle notation la \emph{notation polonaise}\index{notation polonaise}
 dans sa forme préfixée ou directe.
\end{Def}


Cette notation polonaise revient à effectuer un parcours en profondeur de l'arborescence associée à l'expression algébrique considérée.

\begin{Ex}
L'expression $(a - b) / ((c \times d) + e)$ devient ainsi $/ - a b + \times c d e$.
\end{Ex}

Par analogie, en notation polonaise postfixée ou inverse, on place les symboles après les arguments. Certaines calculatrices - notamment des HP - utilisent la notation polonaise inverse.


\subsection{Exercices}

\begin{Exo}
Ecrire les expressions algébriques $(a+b) \times (c-(d-e))$ et $((a/b) \times c)-(d-e)$ en notation polonaise préfixée, et postfixée.
\end{Exo}

%\begin{Exo}
%Combien d'arborescences existe-t-il sur $n$ sommets numérotés ?
%\end{Exo}

\begin{Exo}
Étant donnée l'expression algébrique $(2x + y) \times (5a - b)^3$,
\begin{enumerate}
\item Dessinez l'arborescence ordonnée correspondante (on utilisera le symbole $\wedge$ pour l'exponentiation).
\item Trouvez la \emph{portée} de l'exponentiation (la portée d'un sommet $s$ dans une arborescence est le sous-arbre généré par $s$ et les sommets qui le suivent, avec $s$ pour racine).
\item Écrire l'expression algébrique en notation polonaise directe, et inversée.
\end{enumerate}
\end{Exo}


\subsection{Codage de Huffman}

\subsubsection{Principe}

Le \emph{codage de Huffman}\footnote{David Albert Huffman}\index{codage de Huffman} (1952) est un algorithme de compression \underline{sans perte}, utilisant la notion d'arbres, qui permet de réduire la taille de données numériques.

Le principe, élémentaire, consiste à choisir de ne plus coder chaque symbole avec un nombre fixe de bits, mais à coder les symboles les plus fréquents avec un plus petit nombre de bits (quitte à devoir utiliser beaucoup de bits pour les symboles les plus rares).

\begin{Ex}
Par exemple, dans un texte donné, le $w$ apparait 20 fois moins souvent que le $e$. Plutôt que de coder chaque lettre sur un octet, on va donc :

\begin{itemize}
\item Coder le $e$ par 1 (un seul bit, au lieu de 8),
\item Coder le $w$ par 010100000100 (12 bits, au lieu de 8).
\end{itemize}

Si le $w$ apparait 10 fois (donc le $e$ 200 fois), le gain sera de $7 \times 200 - 4 \times 10 = 1360$ bits, rien qu'en considérant ces deux lettres.
\end{Ex}

\medskip

Cet algorithme offre des taux de compression démontrés les meilleurs possibles pour un codage par symbole, et il est assez compliqué de mieux compresser.

\subsubsection{Propriété de préfixe}

Le codage ne peut pas se faire n'importe comment : il faut pouvoir décoder, sans ambiguïté.

\begin{Ex}
Si l'on décide de :
\begin{itemize}
\item Coder le $e$ par 0,
\item Coder le $w$ par 010100000100,
\item Coder le $x$ par 10100000100,
\end{itemize}
Alors le texte 010100000100 pourra se traduire à la fois par $ex$, et $w$. On ne peut pas accepter une telle indétermination.
\end{Ex}


Le codage de Huffman a donc une propriété de préfixe : une séquence binaire ne peut jamais être à la fois représentative d'un élément codé et constituer le début du code d'un autre élément.

\begin{Ex}
Si un symbole est représenté par la combinaison binaire 100, alors la combinaison 10001 ne peut être le code d'aucune autre information.
\end{Ex}


Cette caractéristique du codage de Huffman permet une codification à l'aide d'une structure d'arbre binaire...


\subsubsection{Méthode}

On part d'une forêt, constituée d'arbres à une racine et une feuille, avec autant d'arbres que de symboles à coder. La feuille contient le symbole, la racine contient la fréquence d'apparition de ce symbole.

A chaque étape, on choisit les deux arbres x,y de racines minimales, et on les remplacent par l'arbre ayant pour racine r la somme des racines de x et y, et pour fils de r les arbres x et y.

La forêt finale est formée d'un unique arbre.

Le code d'une lettre est alors déterminé en suivant le chemin depuis la racine de l'arbre, jusqu'à la feuille du symbole qui nous intéresse, en concaténant successivement un 0 ou un 1 selon que la branche empruntée est à gauche ou à droite.


On dit que l'algorithme est de type glouton : il choisit à chaque étape les meilleurs choix (locaux) possibles, dans l'espoir que le résultat final sera minimal.


Voici les différentes étapes de la construction d'un code de Huffman pour l'alphabet source {A, B, C, D, E, F}, avec les probabilités P(A)=0.10, P(B)=0.10, P(C)=0.25, P(D)=0.15, P(E)=0.35 et P(F)=0.05.

\begin{center}
\includegraphics[scale=0.8]{graphes/huffman.eps}
\end{center}




\begin{Ex}
Ainsi, sur la figure ci-contre, A=0111, B=010, C=10, D=00, E=11 et F=0110.
\end{Ex}


\begin{Ex}
Par exemple le mot FADE serait codé 011001110011. Pour décoder, on lit simplement la chaîne de bits de gauche à droite. Le seul "découpage" possible, grâce à la propriété du préfixe, est 0110-0111-00-11.
\end{Ex}

\subsubsection{Applications}

Malgré son ancienneté, le codage de Huffman est toujours au goût du jour, et offre encore des performances appréciables. Il est utilisé dans presque toutes les applications qui impliquent la compression et la transmission de données numériques : fax, modems, réseaux informatiques, télévision HD, \emph{etc.}

Les premiers Macintosh utilisaient un code inspiré de Huffman pour la représentation des textes : chaque lettre faisait  tantôt 4 bits, tantôt 12 bits, suivant sa fréquence d'apparition dans le texte. Cette méthode simple se révélait économiser 30\% d'espace sur un texte moyen, à une époque où la mémoire vive restait encore un composant coûteux.

Le MPEG-1/2 Audio Layer 3, plus connu sous son abréviation de MP3, est constitué de deux étapes de compression :
\begin{itemize}
\item La première, avec perte, revient à la mise à l'écart de données inaudibles pour l'oreille humaine.
\item La deuxième est un codage de Huffman.
\end{itemize}

Le logiciel de compression \emph{gzip}\index{gzip} (GNU zip) utilise Huffman (avec un autre algorithme : LZ77). Sa version améliorée, l'algorithme \emph{bzip2}\index{bzip2}, utilise la transformée de Burrows-Wheeler avec le codage de Huffman.

Ce principe de compression est aussi utilisé dans le codage d'images. Il fait par exemple partie des spécifications des formats :
\begin{itemize}
\item TIFF (Tagged Image Format File) spécifié par Microsoft Corporation et Aldus Corporation. Le codage d'image est fait en retranscrivant exactement le contenu d'un écran (image), en utilisant Huffman.
\item JPG (Join Photographic Experts Group), algorithme de compression avec perte, dont un des éléments est Huffman.
\end{itemize}



\subsubsection{Exercices}

\begin{Exo}
Construisez un codage de Huffman du message "ceciestuncodagedehuffman" (on a supprimé les espaces et la ponctuation pour simplifier la construction). Il y a plusieurs codages de Huffman possibles.
Vérifiez la propriété du préfixe.
\end{Exo}

\begin{Exo}
Utilisez le tableau ci-dessous pour déterminer le codage de Huffman de la langue française.

Fréquences d'apparition des lettres en français

\begin{center}
\begin{tabular}{|c|c||c|c|}
\hline
Lettre & Fréquence & Lettre & Fréquence \\
\hline
A & 8.40 \% & N & 7.13 \% \\
B & 1.06 \% & O & 5.26 \% \\
C & 3.03 \% & P & 3.01 \% \\
D & 4.18 \% & Q & 0.99 \% \\
E & 17.26 \% & R & 6.55 \% \\
F & 1.12 \% & S & 8.08 \% \\
G & 1.27 \% & T & 7.07 \% \\
H & 0.92 \% & U & 5.74 \% \\
I & 7.34 \% & V & 1.32 \% \\
J & 0.31 \% & W & 0.04 \% \\
K & 0.05 \% & X & 0.45 \% \\
L & 6.01 \% & Y & 0.30 \% \\
M & 2.96 \% & Z & 0.12 \% \\
\hline
\end{tabular}
\end{center}
\end{Exo}




\gsaut
\centerline{\x{Fin du Chapitre}}