]> AND Private Git Repository - cours-maths-dis.git/blob - graphes/arbres.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
ajout d'un cours de TS
[cours-maths-dis.git] / graphes / arbres.tex
1
2
3 \section{Présentation générale}
4
5 \subsection{Définitions}
6
7 \begin{Def}[Arbre, feuilles]
8 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
9 \begin{itemize}
10  \item les \emph{feuilles}\index{feuilles} dont le degré est 1;
11 \item les \emph{n{\oe}uds internes}\index{noeuds} dont le degré est supérieur à 1.
12 \end{itemize}
13 \end{Def}
14
15 \begin{Ex}
16 Un exemple d'arbre :
17 \begin{center}
18 \includegraphics[scale=0.7]{graphes/arbre1.eps}
19 \end{center}
20 \end{Ex}
21
22
23
24 %\begin{Rem}
25 %D'autres définitions équivalentes sont possibles. Par exemple :
26
27 %\begin{description}
28 %\item[basée sur le nombre d'arêtes : ] un arbre est un graphe connexe non orienté possédant \textit{n} $-$ 1 arêtes.
29 %\item[inductive.]
30 %\end{description}
31 %\end{Rem}
32
33
34 \begin{Def}[Forêt]
35 Un graphe sans cycles mais non connexe est appelé une \emph{forêt}\index{forêt}.
36 \end{Def}
37
38 \begin{Ex}
39 Un exemple de forêt :
40 \begin{center}
41 \includegraphics[scale=0.7]{graphes/foret.eps}
42 \end{center}
43 \end{Ex}
44
45
46 \subsection{Caractérisation des arbres}
47
48 \begin{Th}\label{prop:equiv}
49 Les affirmations suivantes sont équivalentes pour tout graphe $G = (V, E)$ à $n$ sommets.
50 \begin{enumerate}
51 \item $G$ est un arbre,
52 \item $G$ est sans cycles et connexe,
53 \item $G$ est sans cycles et comporte $n-1$ arêtes,
54 \item $G$ est connexe et comporte $n-1$ arêtes,
55 \item Chaque paire $(u, v)$ de sommets distincts est reliée par une seule chaîne simple (et le graphe est sans boucles).
56 \end{enumerate}
57 \end{Th}
58
59
60 \subsection{Nombre minimal de feuilles}
61
62 \begin{Th}
63 Tout arbre fini avec au moins deux sommets comporte au moins deux feuilles.
64 \end{Th}
65
66 \subsection{Exercices}
67 \begin{Exo}
68 Démontrez la propriété précédente.
69 \end{Exo}
70
71 \noindent{\underline{\textit{Indication : }}} Récurrence.
72
73 \begin{Exo}
74 Combien d'arbres différents existe-t-il avec 3, 4, 5 sommets ?
75 \end{Exo}
76
77 \noindent{\underline{\textit{Indication : }}} Réfléchir sur le nombre de feuilles.
78
79 \begin{Exo}
80 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?
81 \end{Exo}
82
83 \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...
84 Chaque sommet partage son arête avec un autre sommet, donc :
85 \begin{itemize}
86 \item chaque sommet de degré trois (il y en a 3) a 1,5 arête \og à lui \fg{},
87 \item chaque sommet de degré deux (il y en a 4) a 1 arête \og à lui \fg{},
88 \item chaque sommet de degré un (il y en a $n-7$) a 0,5 arête \og à lui \fg{}
89 \end{itemize}
90 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$$
91 \noindent d'où $n=12$, et il y a 5 sommets de degré 1.
92
93
94 \begin{Exo}
95 Soit un graphe $G$.
96 Supposons qu'il y ait deux chaînes élémentaires distinctes $P_1$ et
97 $P_2$ d'un sommet $s$ à un autre sommet $s'$ de $G$. $G$ est-il un
98 arbre? Justifier par une preuve.
99 %Seymour Lipschutz 6.14 p 113
100 \end{Exo}
101
102 \section{Codage de Prüfer}
103
104
105 \subsection{Présentation}
106 Le codage de Prüfer est une manière très compacte de décrire un arbre.
107
108 \subsection{Codage}
109
110 \subsubsection{La méthode}
111
112 Soit l'arbre $T = (V, E)$ et supposons $V = {1, 2, ..., n}$.
113 L'algorithme ci-dessous fournira le code de $T$, c'est-à-dire une suite $S$ de
114 $n-2$ termes employant (éventuellement plusieurs fois) des nombres choisis parmi
115 $\{1, ..., n\}$.
116
117 \begin{Th}[Pas général de l'algorithme de codage]
118 Initialement la suite $S$ est vide.
119 Ce pas général est à répéter tant qu'il reste plus de
120 deux sommets dans l'arbre courant $T$ :
121 \begin{itemize}
122 \item identifier la feuille $v$ de l'arbre courant ayant le numéro minimum ;
123 \item ajouter à la suite $S$ le seul sommet $s$ adjacent à $v$ dans l'arbre $T$ courant ;
124 \item enlever de l'arbre $T$ courant la feuille $v$ et l'arête incidente à $v$.
125 \end{itemize}
126 \end{Th}
127
128 \subsubsection{Exemple de codage}
129
130 \begin{description}
131 \item[\'Etape 0 :] arbre à coder
132
133 \begin{center}
134 \includegraphics[scale=0.7]{graphes/prufer1.eps}
135 \end{center}
136
137 1: 4
138
139 2: 10
140
141 3: 6, 8
142
143 4: 1, 5, 7, 8
144
145 5: 4, 10
146
147 6: 3
148
149 7: 4
150
151 8: 3, 4
152
153 9: 10
154
155 10: 2, 5, 9
156
157 \item[\'Etape 1 :]
158
159 \begin{center}
160 \includegraphics[scale=0.7]{graphes/prufer2.eps}
161 \end{center}
162
163 2: 10
164
165 3: 6, 8
166
167 4: 5, 7, 8
168
169 5: 4, 10
170
171 6: 3
172
173 7: 4
174
175 8: 3, 4
176
177 9: 10
178
179 10: 2, 5, 9
180
181 \begin{center}S=\{4\}\end{center}
182
183
184 \item[\'Etape 2 :]
185
186 \begin{center}
187 \includegraphics[scale=0.7]{graphes/prufer3.eps}
188 \end{center}
189
190 3: 6, 8
191
192 4: 5, 7, 8
193
194 5: 4, 10
195
196 6: 3
197
198 7: 4
199
200 8: 3, 4
201
202 9: 10
203
204 10: 5, 9
205
206 \begin{center}S=\{4,10\}\end{center}
207
208 \item[\'Etape 3 :]
209
210 \begin{center}
211 \includegraphics[scale=0.7]{graphes/prufer4.eps}
212 \end{center}
213
214 3: 8
215
216 4: 5, 7, 8
217
218 5: 4, 10
219
220 7: 4
221
222 8: 3, 4
223
224 9: 10
225
226 10: 5, 9
227
228 \begin{center}S=\{4,10,3\}\end{center}
229
230 \item[\'Etape 4 :]
231
232 \begin{center}
233 \includegraphics[scale=0.7]{graphes/prufer5.eps}
234 \end{center}
235
236 4: 5, 7, 8
237
238 5: 4, 10
239
240 7: 4
241
242 8: 4
243
244 9: 10
245
246 10: 5, 9
247
248 \begin{center}S = \{4,10,3,8\}\end{center}
249
250 \item[\'Etape 5 :]
251
252 \begin{center}
253 \includegraphics[scale=0.7]{graphes/prufer6.eps}
254 \end{center}
255
256 4: 5, 8
257
258 5: 4, 10
259
260 8: 4
261
262 9: 10
263
264 10: 5, 9
265
266
267 \begin{center}S = \{4,10,3,8,4\}\end{center}
268
269 \item[\'Etape 6 :]
270
271 \begin{center}
272 \includegraphics[scale=0.7]{graphes/prufer7.eps}
273 \end{center}
274
275 4: 5
276
277 5: 4, 10
278
279 9: 10
280
281 10: 5, 9
282
283 \begin{center}S = \{4,10,3,8,4,4\}\end{center}
284
285 \item[\'Etape 7 :]
286
287 \begin{center}
288 \includegraphics[scale=0.7]{graphes/prufer8.eps}
289 \end{center}
290
291 5: 10
292
293 9: 10
294
295 10: 5, 9
296
297 \begin{center}S = \{4,10,3,8,4,4,5\}\end{center}
298
299 \item[\'Etape 8 :]
300
301 \begin{center}
302 \includegraphics[scale=0.7]{graphes/prufer9.eps}
303 \end{center}
304
305 9: 10
306
307 10: 9
308
309 \begin{center}S = \{4,10,3,8,4,4,5,10\}\end{center}
310
311 \item[\'Etape 9 :] S = \{4,10,3,8,4,4,5,10\} est le codage de Prüfer de l'arbre initial.
312
313 \end{description}
314
315
316 \subsection{Décodage}
317
318 \subsubsection{La méthode}
319 \begin{description}
320 \item[Donnée :] suite $S$ de $n-2$ nombres, chacun provenant de \{1, ..., n\}.
321
322 Posons $I = \{1, ..., n\}$.
323
324 \item[Pas général de l'algorithme de décodage :]
325 à répéter tant qu'il reste des éléments dans $S$ et plus de deux éléments dans $I$ :
326 \begin{itemize}
327 \item identifier le plus petit élément $i$ de $I$ n'apparaissant pas dans la suite $S$ ;
328 \item relier par une arête de $T$ le sommet $i$ avec le sommet $s$ correspondant au premier élément de la suite $S$ ;
329 \item enlever $i$ de $I$ et $s$ de $S$.
330 \end{itemize}
331
332 \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.
333 \end{description}
334
335
336 \subsubsection{Exemple de décodage}
337
338
339 \begin{description}
340 \item[\'Etape 0 :] arbre à décoder
341
342 \begin{center}
343 \includegraphics[scale=0.7]{graphes/deprufer1.eps}
344
345
346 I=\{1,2,3,4,5,6,7,8,9,10\}
347
348 S=\{4,10,3,8,4,4,5,10\}
349 \end{center}
350
351
352
353 \item[\'Etape 1 :]
354
355 \begin{center}
356 \includegraphics[scale=0.7]{graphes/deprufer2.eps}
357 \end{center}
358
359 1: 4
360
361 4: 1
362
363
364 \begin{center}
365 I=\{2,3,4,5,6,7,8,9,10\}
366
367 S=\{10,3,8,4,4,5,10\}
368 \end{center}
369
370
371 \item[\'Etape 2 :]
372
373 \begin{center}
374 \includegraphics[scale=0.7]{graphes/deprufer3.eps}
375 \end{center}
376
377 1: 4
378
379 2: 10
380
381 4: 1
382
383 10: 2
384
385 \begin{center}
386 I=\{3,4,5,6,7,8,9,10\}
387
388 S=\{3,8,4,4,5,10\}
389
390 \end{center}
391
392 \item[\'Etape 3 :]
393
394 \begin{center}
395 \includegraphics[scale=0.7]{graphes/deprufer4.eps}
396 \end{center}
397
398 1: 4
399
400 2: 10
401
402 3: 6
403
404 4: 1
405
406 6: 3
407
408 10: 2
409
410
411 \begin{center}
412 I=\{3,4,5,7,8,9,10\}
413
414 S=\{8,4,4,5,10\}
415 \end{center}
416
417 \item[\'Etape 4 :]
418
419 \begin{center}
420 \includegraphics[scale=0.7]{graphes/deprufer5.eps}
421 \end{center}
422
423 1: 4
424
425 2: 10
426
427 3: 6, 8
428
429 4: 1
430
431 6: 3
432
433 8: 3
434
435 10: 2
436
437
438 \begin{center}
439 I=\{4,5,7,8,9,10\}
440
441 S=\{4,4,5,10\}
442 \end{center}
443
444 \item[\'Etape 5 :]
445
446 \begin{center}
447 \includegraphics[scale=0.7]{graphes/deprufer6.eps}
448 \end{center}
449
450 1: 4
451
452 2: 10
453
454 3: 6, 8
455
456 4: 1, 7
457
458 6: 3
459
460 7: 4
461
462 8: 3
463
464 10: 2
465
466 \begin{center}
467 I=\{4,5,8,9,10\}
468
469 S=\{4,5,10\}
470
471 \end{center}
472
473 \item[\'Etape 6 :]
474
475 \begin{center}
476 \includegraphics[scale=0.7]{graphes/deprufer7.eps}
477 \end{center}
478
479 1: 4
480
481 2: 10
482
483 3: 6, 8
484
485 4: 1, 7, 8
486
487 6: 3
488
489 7: 4
490
491 8: 3, 4
492
493 10: 2
494
495 \begin{center}
496 I=\{4,5,9,10\}
497
498 S=\{5,10\}
499 \end{center}
500
501 \item[\'Etape 7 :]
502
503 \begin{center}
504 \includegraphics[scale=0.7]{graphes/deprufer8.eps}
505 \end{center}
506
507 1: 4
508
509 2: 10
510
511 3: 6, 8
512
513 4: 1, 5, 7, 8
514
515 5: 4
516
517 6: 3
518
519 7: 4
520
521 8: 3, 4
522
523 10: 2
524
525 \begin{center}
526 I=\{5,9,10\}
527
528 S=\{10\}
529 \end{center}
530
531 \item[\'Etape 8 :]
532
533 \begin{center}
534 \includegraphics[scale=0.7]{graphes/deprufer9.eps}
535 \end{center}
536
537 1: 4
538
539 2: 10
540
541 3: 6, 8
542
543 4: 1, 5, 7, 8
544
545 5: 4, 10
546
547 6: 3
548
549 7: 4
550
551 8: 3, 4
552
553 10: 2, 5
554
555
556 \begin{center}
557 I=\{9,10\}
558
559 S=\{\}
560 \end{center}
561
562 \item[\'Etape 9 :]
563
564 \begin{center}
565 \includegraphics[scale=0.7]{graphes/deprufer10.eps}
566 \end{center}
567
568 1: 4
569
570 2: 10
571
572 3: 6, 8
573
574 4: 1, 5, 7, 8
575
576 5: 4, 10
577
578 6: 3
579
580 7: 4
581
582 8: 3, 4
583
584 9: 10
585
586 10: 2, 5, 9
587
588 \begin{center}
589 I=\{\}
590
591 S=\{\}
592 \end{center}
593
594
595 \end{description}
596
597
598
599
600 \begin{Exo}
601 Décrivez l'arbre ci-dessous à l'aide du codage de Prüfer.
602 \begin{center}
603 \includegraphics[scale=0.7]{graphes/arbre123.eps}
604 \end{center}
605 \end{Exo}
606
607
608
609
610
611
612
613 \begin{Exo}
614 Dessinez l'arbre correspondant à la suite S=\{1,1,1,1,1,1,1,1,1\}.
615 \end{Exo}
616
617 \begin{Exo}
618 Dessinez l'arbre correspondant à la suite S=\{1,2,3,4,5,6,7,8\}.
619 \end{Exo}
620
621
622
623 \subsection{Théorème de Cayley}
624
625 \begin{Th}[Cayley, 1857]
626 Le nombre d'arbres que l'on peut construire sur $n$ ($n>1$) sommets numérotés est égal à $n^{n-2}$.
627 \end{Th}
628
629 \begin{Pre}
630 La preuve est immédiate en utilisant le codage de Prüfer.
631
632 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.
633
634 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.
635 \end{Pre}
636
637 \section{Arbres couvrants}
638
639 \subsection{Définition}
640
641 \begin{Def}[Arbre couvrant]
642  Un \emph{arbre couvrant}\index{arbre!couvrant}
643  (ou \emph{arbre maximal}\index{arbre!maximal}) d'un graphe G, est un graphe partiel de G qui est aussi un arbre.
644 \end{Def}
645
646 \begin{Rem}
647 On rappelle qu'un graphe partiel de G est obtenu en enlevant des arêtes (mais pas de sommets) à G.
648 \end{Rem}
649
650 \begin{Ex}
651 Un des arbres couvrants (en bleu) d'un graphe donné.
652 \begin{center}
653 \includegraphics[scale=0.7]{graphes/couvrant.eps}
654 \end{center}
655 \end{Ex}
656
657 \subsubsection{Exercices}
658 \begin{Exo}
659 Dessiner des arbres couvrants pour chacun des graphes suivants.
660 \begin{center}
661 \includegraphics[scale=0.7]{graphes/ex1.eps}
662 \includegraphics[scale=0.7]{graphes/ex2.eps}
663 \includegraphics[scale=0.7]{graphes/ex3.eps}
664 \end{center}
665
666 \end{Exo}
667
668 \begin{Exo}
669 Combien d'arbres couvrants différents les graphes ci-dessus possèdent-ils ?
670 \end{Exo}
671
672
673 \subsection{Arbre maximal de poids minimum}
674 \subsubsection{Présentation du problème}
675
676 On considérera le problème suivant :
677
678 \og Soit le graphe $G = (V, E)$ avec un poids associé à
679 chacune de ses arêtes. Trouver, dans $G$, un arbre maximal
680 $A = (V, F)$ de poids total minimum.\fg{}
681
682
683 Ce problème se pose, par exemple, lorsqu'on désire relier $n$ villes par un réseau routier de coût minimum.
684 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.
685
686 L'algorithme de Kruskal décrit ci-dessous permet de résoudre ce problème.
687
688
689 \subsubsection{L'algorithme de Kruskal}
690
691 Voici un algorithme célèbre permettant de résoudre ce problème :
692
693 %\begin{Th}[L'algorithme de Kruskal]
694
695 %\begin{description}
696 %\item[Données :] Graphe $G = (V, E)$ ($|V| = n$, $|E| = m$) et pour chaque arête $e$ de $E$, son poids $c(e)$.
697 %\item[Résultat :] Arbre ou forêt maximale $A = (V, F)$ de poids minimum.
698 %\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)$.
699 %\begin{enumerate}
700 %\item Poser $F := \varnothing$, $k := 0$
701 %\item Tant que $k < m$ et $|F| < n-1$ faire
702 %\begin{itemize}
703 %\item Début
704 %\begin{itemize}
705 %\item si $e_{k+1}$ ne forme pas de cycle avec $F$ alors $F := F \cup \{e_{k+1}\}$
706 %\item $k := k+1$
707 %\end{itemize}
708 %\item Fin
709 %\end{itemize}
710 %\end{enumerate}
711 %\end{description}
712 %\end{Th}
713
714 \begin{Th}[L'algorithme de Kruskal]
715 \index{Algorithme!de Kruskal}\index{Kruskal (algorithme)}
716 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 :
717 \begin{enumerate}
718 \item On part du graphe $G' = (S, \varnothing)$ ($G$ sans arête).
719 \item Tant que le nombre d'arêtes de $G'$ est inférieur à $min(|G|-1,|A|)$, faire
720 \begin{itemize}
721 \item Prendre la plus petite arête (de poids minimal) restante dans $G$.
722 \item L'ajouter à $G'$ si cela ne crée pas de cycle.
723 \item La supprimer de $G$.
724 \end{itemize}
725 \end{enumerate}
726 \end{Th}
727
728
729
730
731 \begin{Exo}
732 Le tableau suivant donne les coûts de construction de routes (exprimées en unités adéquates) entre six villes d'Irlande.
733
734 \begin{center}
735 \begin{tabular}{l|cccccc}
736          & Athlone & Dublin & Galway & Limerick & Sligo & Wexford \\
737 \hline
738 Athlone & -%Athlone
739 & 78 %Dublin
740 & 56 %Galway
741 & 73 %Limerick
742 & 71 %Sligo
743 & 114 \\ %Wexford
744 Dublin %
745 & -%Athlone
746 & -%Dublin
747 & 132%Galway
748 & 121%Limerick
749 & 135%Sligo
750 & 96 \\%Wexford \\
751 Galway %
752 & -%Athlone
753 & -%Dublin
754 & -%Galway
755 & 64%Limerick
756 & 85%Sligo
757 & 154\\%Wexford \\
758 Limerick %
759 & -%Athlone
760 & -%Dublin
761 & -%Galway
762 & -%Limerick
763 & 144%Sligo
764 & 116\\%Wexford \\
765 Sligo %
766 & -%Athlone
767 & -%Dublin
768 & -%Galway
769 & -%Limerick
770 & -%Sligo
771 & 185%Wexford
772 \end{tabular}
773 \end{center}
774
775 Trouver une manière de relier ces six villes, en minimisant le coût total de construction.
776 \end{Exo}
777
778
779
780 \begin{Exo}
781 Faire de même avec le tableau suivant, qui comptabilise cette fois-ci les kilomètres entre chaque ville (valeurs imaginaires) :
782 \begin{center}
783 \begin{tabular}{l|cccccc}
784          & Athlone & Dublin & Galway & Limerick & Sligo & Wexford \\
785 \hline
786 Athlone & -%Athlone
787 & 121 %Dublin
788 & 95 %Galway
789 & 43 %Limerick
790 & 71 %Sligo
791 & 74 \\ %Wexford
792 Dublin %
793 & -%Athlone
794 & -%Dublin
795 & 72%Galway
796 & 98%Limerick
797 & 115%Sligo
798 & 97 \\%Wexford \\
799 Galway %
800 & -%Athlone
801 & -%Dublin
802 & -%Galway
803 & 64%Limerick
804 & 77%Sligo
805 & 134\\%Wexford \\
806 Limerick %
807 & -%Athlone
808 & -%Dublin
809 & -%Galway
810 & -%Limerick
811 & 144%Sligo
812 & 126\\%Wexford \\
813 Sligo %
814 & -%Athlone
815 & -%Dublin
816 & -%Galway
817 & -%Limerick
818 & -%Sligo
819 & 85%Wexford
820 \end{tabular}
821 \end{center}
822 \end{Exo}
823
824
825
826 \section{Arborescence}
827
828 \subsection{Définitions et exemples}
829
830 \subsubsection{Définition d'une arborescence}
831
832 \begin{Def}[Arborescence]
833 On appelle \emph{arborescence}\index{arborescence} un arbre avec un sommet distingué, que l'on appelle la racine.
834 \end{Def}
835
836 \begin{Notation}
837 On représente généralement une arborescence avec la racine en haut du dessin et les feuilles en bas.
838 \end{Notation}
839
840 \subsubsection{Exemples}
841
842 \begin{Ex}
843 Sur l'arborescence ci-dessous, la racine est le sommet 4. Les sommets 5, 6, 7 et 9 sont les feuilles.
844 \begin{center}
845 \includegraphics[scale=0.7]{graphes/arbo1.eps}
846 \end{center}
847 \end{Ex}
848
849 \begin{Ex}
850 Les systèmes de fichiers ($ext3$ sous linux, $ntfs$ sous windows, etc.) sont agencés en arborescence.
851 \end{Ex}
852
853
854 \subsubsection{Rang des sommets}
855
856
857 On peut, dans une arborescence, assigner un rang aux sommets :
858
859 \begin{Def}[Rang d'un sommet]
860 Le \emph{rang}\index{sommet!rang} d'un sommet d'une arborescence est la distance de ce sommet à la racine.
861 \end{Def}
862
863
864 \begin{Ex}
865 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.
866 \end{Ex}
867
868 \begin{Def}[Hauteur d'une arborescence]
869 On dira que la \emph{hauteur} \index{arborescence!hauteur} de l'arborescence est le rang maximum
870 \end{Def}
871
872 \begin{Ex}
873 L'exemple ci-dessus a une hauteur de 4.
874 \end{Ex}
875
876
877 \subsection{Arborescences ordonnées, parcours en largeur et profondeur}
878
879 \subsubsection{Arborescences ordonnées}
880
881 \begin{Def}[Arborescence ordonnée]
882 Une \emph{arborescence ordonnée}\index{arborescence!ordonnée} est une arborescence dont les arêtes partant de chaque sommet sont ordonnées.
883 \end{Def}
884
885 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,
886 \begin{itemize}
887 \item elle possède à sa gauche des arêtes plus petites (pour l'ordre considéré), et à sa droite de plus grandes arêtes,
888 \item au-dessus d'elle, les arêtes sont plus petites pour l'ordre, et plus grandes en-dessous d'elles.
889 \end{itemize}
890
891 En d'autres termes, on va dans le sens des arêtes croissantes quand on parcourt cette représentation canonique :
892 \begin{itemize}
893 \item de la gauche vers la droite,
894 \item ou du haut vers le bas.
895 \end{itemize}
896
897
898 Il est donc possible de parler, sans ambiguïté, de droite et gauche, de haut et bas, pour une arborescence ordonnée.
899
900
901 \begin{Rem}
902 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.
903 \end{Rem}
904
905
906 On peut étiqueter sans ambiguïté les sommets d'une arborescence ordonnée, comme suit :
907 \begin{itemize}
908 \item on attribue 0 à la racine $r$,
909 \item puis 1, 2, 3, ... aux sommets qui sont adjacents à $r$, en respectant l'ordre des arêtes issues de la racines.
910 \item Les étiquettes suivantes sont constituées de l'étiquette du sommet "père", suivie d'un chiffre obtenu comme précédemment.
911 \item Ainsi, les sommets "fils" attachés au sommet 2 seront numérotés 2.1, 2.2, 2.3,...
912 \end{itemize}
913
914
915 \begin{Ex}
916 La figure ci-dessous illustre le procédé.
917 \begin{center}
918 \includegraphics[scale=0.7]{graphes/ordo.eps}
919 \end{center}
920 \end{Ex}
921
922
923 \begin{Exo}
924 \'Etiqueter les sommets de l'arborescence ordonnée dont la représentation canonique est la suivante :
925 \begin{center}
926 \includegraphics[scale=0.7]{graphes/arbo1.eps}
927 \end{center}
928 \end{Exo}
929
930 \begin{Def}
931 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.
932 \end{Def}
933
934
935
936 \subsubsection{Parcours en largeur, en profondeur}
937
938 \paragraph{Définition des parcours}
939
940 \begin{Def}[Parcours en largeur, en profondeur]
941 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.
942 \end{Def}
943
944 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.
945
946
947
948 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.
949
950
951
952 \begin{Rem}
953 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. 
954
955 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.
956 \end{Rem}
957
958
959
960 \paragraph{Exercices.}
961
962
963 \begin{Exo}
964 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 :
965 \begin{center}
966 \includegraphics[scale=0.7]{graphes/arbo1.eps}
967 \end{center}
968 \end{Exo}
969
970
971 \begin{Exo}
972 Réfléchir à un algorithme de parcours en largeur d'une arborescence ordonnée.
973 \end{Exo}
974
975 \subsubsection{Lien avec les expressions algébriques}
976
977 \paragraph{Arborescence d'une expression algébrique.}
978
979 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.
980
981 \begin{Ex}
982 Par exemple, l'aborescence ci-dessous représente l'expression arithmétique
983 $(a - b) / ((c \times d) + e)$:
984 \begin{center}
985 \includegraphics[scale=0.7]{graphes/polonais.eps}
986 \end{center}
987 \end{Ex}
988
989
990 On observe que les variables de l'expression ($a, b, c, d$ et $e$)
991  sont les feuilles de l'arborescence, et que les opérations sont les autres sommets.
992
993 \begin{Rem}
994 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é.
995 \end{Rem}
996
997 \begin{Exo}
998 Construire les arborescences associées aux expressions algébriques : $(a+b)*(c-(d-e))$ et $((a/b)*c)-(d-e)$.
999 \end{Exo}
1000
1001 \paragraph{Notation polonaise.}
1002
1003 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$
1004  au lieu de $c/d$, nous n'avions plus besoin de parenthèses\ldots
1005
1006 \begin{Def}[Notation polonaise]
1007 On appelle cette nouvelle notation la \emph{notation polonaise}\index{notation polonaise}
1008  dans sa forme préfixée ou directe.
1009 \end{Def}
1010
1011
1012 Cette notation polonaise revient à effectuer un parcours en profondeur de l'arborescence associée à l'expression algébrique considérée.
1013
1014 \begin{Ex}
1015 L'expression $(a - b) / ((c \times d) + e)$ devient ainsi $/ - a b + \times c d e$.
1016 \end{Ex}
1017
1018 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.
1019
1020
1021 \subsection{Exercices}
1022
1023 \begin{Exo}
1024 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.
1025 \end{Exo}
1026
1027 %\begin{Exo}
1028 %Combien d'arborescences existe-t-il sur $n$ sommets numérotés ?
1029 %\end{Exo}
1030
1031 \begin{Exo}
1032 Étant donnée l'expression algébrique $(2x + y) \times (5a - b)^3$,
1033 \begin{enumerate}
1034 \item Dessinez l'arborescence ordonnée correspondante (on utilisera le symbole $\wedge$ pour l'exponentiation).
1035 \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).
1036 \item Écrire l'expression algébrique en notation polonaise directe, et inversée.
1037 \end{enumerate}
1038 \end{Exo}
1039
1040
1041 \subsection{Codage de Huffman}
1042
1043 \subsubsection{Principe}
1044
1045 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.
1046
1047 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).
1048
1049 \begin{Ex}
1050 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 :
1051
1052 \begin{itemize}
1053 \item Coder le $e$ par 1 (un seul bit, au lieu de 8),
1054 \item Coder le $w$ par 010100000100 (12 bits, au lieu de 8).
1055 \end{itemize}
1056
1057 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.
1058 \end{Ex}
1059
1060 \medskip
1061
1062 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.
1063
1064 \subsubsection{Propriété de préfixe}
1065
1066 Le codage ne peut pas se faire n'importe comment : il faut pouvoir décoder, sans ambiguïté.
1067
1068 \begin{Ex}
1069 Si l'on décide de :
1070 \begin{itemize}
1071 \item Coder le $e$ par 0,
1072 \item Coder le $w$ par 010100000100,
1073 \item Coder le $x$ par 10100000100,
1074 \end{itemize}
1075 Alors le texte 010100000100 pourra se traduire à la fois par $ex$, et $w$. On ne peut pas accepter une telle indétermination.
1076 \end{Ex}
1077
1078
1079 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.
1080
1081 \begin{Ex}
1082 Si un symbole est représenté par la combinaison binaire 100, alors la combinaison 10001 ne peut être le code d'aucune autre information.
1083 \end{Ex}
1084
1085
1086 Cette caractéristique du codage de Huffman permet une codification à l'aide d'une structure d'arbre binaire...
1087
1088
1089 \subsubsection{Méthode}
1090
1091 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.
1092
1093 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.
1094
1095 La forêt finale est formée d'un unique arbre.
1096
1097 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.
1098
1099
1100 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.
1101
1102
1103 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.
1104
1105 \begin{center}
1106 \includegraphics[scale=0.8]{graphes/huffman.eps}
1107 \end{center}
1108
1109
1110
1111
1112 \begin{Ex}
1113 Ainsi, sur la figure ci-contre, A=0111, B=010, C=10, D=00, E=11 et F=0110.
1114 \end{Ex}
1115
1116
1117 \begin{Ex}
1118 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.
1119 \end{Ex}
1120
1121 \subsubsection{Applications}
1122
1123 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.}
1124
1125 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.
1126
1127 Le MPEG-1/2 Audio Layer 3, plus connu sous son abréviation de MP3, est constitué de deux étapes de compression :
1128 \begin{itemize}
1129 \item La première, avec perte, revient à la mise à l'écart de données inaudibles pour l'oreille humaine.
1130 \item La deuxième est un codage de Huffman.
1131 \end{itemize}
1132
1133 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.
1134
1135 Ce principe de compression est aussi utilisé dans le codage d'images. Il fait par exemple partie des spécifications des formats :
1136 \begin{itemize}
1137 \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.
1138 \item JPG (Join Photographic Experts Group), algorithme de compression avec perte, dont un des éléments est Huffman.
1139 \end{itemize}
1140
1141
1142
1143 \subsubsection{Exercices}
1144
1145 \begin{Exo}
1146 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.
1147 Vérifiez la propriété du préfixe.
1148 \end{Exo}
1149
1150 \begin{Exo}
1151 Utilisez le tableau ci-dessous pour déterminer le codage de Huffman de la langue française.
1152
1153 Fréquences d'apparition des lettres en français
1154
1155 \begin{center}
1156 \begin{tabular}{|c|c||c|c|}
1157 \hline
1158 Lettre & Fréquence & Lettre & Fréquence \\
1159 \hline
1160 A & 8.40 \% & N & 7.13 \% \\
1161 B & 1.06 \% & O & 5.26 \% \\
1162 C & 3.03 \% & P & 3.01 \% \\
1163 D & 4.18 \% & Q & 0.99 \% \\
1164 E & 17.26 \% & R & 6.55 \% \\
1165 F & 1.12 \% & S & 8.08 \% \\
1166 G & 1.27 \% & T & 7.07 \% \\
1167 H & 0.92 \% & U & 5.74 \% \\
1168 I & 7.34 \% & V & 1.32 \% \\
1169 J & 0.31 \% & W & 0.04 \% \\
1170 K & 0.05 \% & X & 0.45 \% \\
1171 L & 6.01 \% & Y & 0.30 \% \\
1172 M & 2.96 \% & Z & 0.12 \% \\
1173 \hline
1174 \end{tabular}
1175 \end{center}
1176 \end{Exo}
1177
1178
1179
1180
1181 \gsaut
1182 \centerline{\x{Fin du Chapitre}}