Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
15
CHAPITRE 2.
STRUCTURES ARBORESCENTES.
2.1 DEFINITIONS.
2.1.1 Arbres.
C’est un graphe non orienté, connexe, acyclique.
FIG. 2.1. Arbre.
Un arbre comprend n – 1 arêtes. L’addition à un arbre d’une arête entre deux
sommets crée un cycle et un seul.
2.1.2 Forêts.
C’est un graphe non orienté acyclique (pas forcément connexe). Chaque
composante connexe d’une forêt est un arbre.
2.1.3 Arborescence.
C’est un graphe orienté ó chaque sommet possède un seul précédent sauf un qui
n’en a pas : la RACINE. Pour tout x de X, il existe un chemin unique de la racine
à x.
On considère un nœud x d’une arborescence T, de racine r.
Un nœud y quelconque sur le chemin unique de r à x est appelé
ANCETRE de x ; x est un DESCENDANT de y.
Si le dernier arc sur le chemin de r vers x est (y, x), alors y est le père de
x, x est un fils de y. Si deux nœuds ont le même père, ils sont frères. Un
nœud sans fils est une feuille. Un noeud qui n’est pas une feuille est dit un
noeud interne.
La longueur du chemin entre r et x est la profondeur de x dans T.
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
16
La hauteur d’un noeud x est définie récursivement de la faςon suivante :
h(x) = 0 si x est la racine.
h(x) = 1 + h(y) si y est le père de x.
Degré d’un noeud & Degré d’une aborescence.
Degré d’un noeud est le nombre de ses sous-aborescences.
Degré d’une aborescence est le degré maximal des noeuds. Si une aborescence
T a le degré m, T est dit l’ aborescence à m- aires.
Si chaque nœud a au maximum deux fils, on parle d’arborescence binaire.
EXEMPLE. Arborescence 3-aires de 8 nœuds, de hauteur 4 avec la racine.
d(1) = 3 Niveau 0.
d(4)=2 d(3)=0
Niveau 1.
d( 2)=0
d(5)=2
Niveau 2.
d(9)=0
d(6)=0 d(7) =1 Niveau 3.
d(8)=0 Niveau 4.
FIG.2.2.
2.1.4. EXEMPLE.
On peut parfois représenter une relation d’inclusion entre plusieurs ensembles
par une aborescence :
B, C, D ⊂ A. A
E, F, G, H ⊂ B.
M, N ⊂ D. D C B
I ⊂ E.
J,K ⊂ F. M N E F G H
L ⊂ H. I J K L
2
3
1
4
5
9
6 7
8
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
17
Une variable structurée peut être représentée sous forme d’un arbre. Par exemple :
ETUDIANT
ETABLISEMENT IDENTITÉ
ECOLE UNIVERSITÉ NOM PRENOM NAISSANCE
DATE LIEU
JOUR MOIS ANNEE VILLE DEP.
Une expression arithmétique
X = (x – (2* y) +((x+(y+z)) *z)
A pour représentation : +
- *
x * + z
2 y x +
y z
Les résultats d’un tournoi de tennis :
Premier tour. Marc a battu Franςois, Jean
Jean a battu Jules, et Jean Paul
Luc a battu Pierre. Jean Marc Luc Paul
Deuxième tour. Jean a battu Marc Jean Jules Marc Fr Luc Pierre
et Paul a battu Luc.
Jean a gagné en final contre Paul.
Les Phrases d’une langue naturelle (ou d’un langage de programmation).
La phrase « Le Pilote ferme la porte »
peut se représenter sous la forme : Ferme
Pilote porte
Le la
Le dictionaire « aborescence ». .
Par exemple, le dictionaire composé des mots ART COU
ART, ARTICLE, ARTISTE, COU, COUR, * I * R TEAU VE
COUTEAU, COUVE,COUVENT,COUVER
peuvent se représenter par la figure suivante. CLE STE * * NT R
Le caractère « * » indique la fin d’un mot.
On notera que l’ordre alphabétique est * * * *
respecté de gauche à droite à chaque niveau.
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
18
2.2 PROPRIETES FONDAMENTALES.
2.2.1 THEOREME 1.
Soit G un arbre d’ordre n > 1. Les propriétés suivantes sont équivalentes :
1. G est connexe et sans cycle.
2. G est connexe et admet n – 1 arêtes.
3. G est sans cycle et admet n – 1 arêtes.
4. G est sans cycle et en ajoutant une arête entre deux sommets non adjacents,
on crée un cycle (et un seul).
5. G est connexe et en supprimant une arête quelconque, il n’est plus connexe.
6. Tout couple de sommets est relié par une chne et une seule.
2.2.2 THEOREME 2.
Un graphe G = (X,U) admet un graphe partiel qui soit un arbre si et seulement si il
est connexe.
2.2.3 THEOREME 3.
Toute arborescence est un arbre.
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
19
2.3 ARBRES BINAIRES.
2.3.1. DEFINITION (EN RECURSIVE).
Un arbre binaire est soit vide (noté ∅) soit de la forme :
B = < O, B
1
, B
2
> où :
O : racine,
B
1
: sous arbre gauche et
B
2
: sous arbre droit.
2.3.2. REPRÉSENTATION DES ARBRES BINAIRES.
EXEMPLE.
UTLISATION DE TABLEAU.
Type Arbtab = Array [1 n] of Record v : t ;
G : integer ;
D : integer ;
End ;
Gauche Droit
1
2 d 0 8
3 a 5 6
4 e 0 9
5 b 2 0
6 c 4 0
7
8 f 0 0
9 g 0 0
10
UTILISATION DE POINTEURS :
Type Pt = ^nut ;
nut = Record
G : Pt ;
Val : t ;
D : Pt ;
End ;
e
a
b
d
c
f
g
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
20
2.3.3. PARCOURS D’UN ARBRE BINAIRE.
Nous nous limitons ci-dessous à trois parcours classiques suivants :
1. PREFIXÉ(en préordre).
Le traitement de la racine.
Le parcours du sous arbre gauche.
Le parcours du sous arbre droit.
2. INFIXÉ.
Le parcours du sous arbre gauche.
Le traitement de la racine.
Le parcours du sous arbre droit.
3. POSTFIXÉ (SUFFIXÉ).
Le parcours du sous arbre gauche.
Le parcours du sous arbre droit.
Le traitement de la racine.
EXEMPLE.
Pour le graphe de l’exemple ci-dessus, on a :
1. Parcours préfixé : a b d f c e g
2. Parcours infixé : d f b a e g c
3. Parcours suffixé : f d b g e c a
2.4 ARBRES DE RECOUVREMENT.
2.4.1. DÉDINITION.
Soit G un graphe non orienté. Un arbre H est dit l’arbre de recouvrement de G
si H est sous arbre partiel de G et contenant tous les noeuds de G.
2.4.2. THÉORÈME.
Un graphe G a un arbre de recouverement si et seulement si G est connexe.
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
21
2.4.3. ALGORITHME DE RECHERCHE DE L’ARBRE DE RECOUVREMENT.
Considèrons un graphe G.
ALGORITHME.
1
er
étape. H := { un noeud quelconque de G}.
2
è
étape. Si tous les noeuds de G appartiennent à H , l’algorithme termine.
3
è
étape. Si non, choisir un noeud de G, relié à un noeud de H par une arête.
Ajouter ce noeud à H. Retouner à la 2
è
étape.
EXEMPLE .
Considèrons le graphe G de la figure suivante :
x
3
x
2
x
1
x
6
x
4
x
5
FIG. 2.3.
À partir de x
1
. T= ∅.
1
er
étape. Choisir x
2,
T = {(x
1
,x
2
)}.
2
è
étape. Choisir x
3,
T = {(x
1
,x
2
), (x
2
,x
3
)}.
3
è
étape. Choisir x
4,
T = {(x
1
,x
2
), (x
2
,x
3
), (x
3
,x
4
)}.
4
è
étape. Choisir x
5
,
T = {(x
1
,x
2
), (x
2
,x
3
), (x
3
,x
4
), (x
4
,x
5
)}.
5
è
étape. Choisir x
6
,
T = {(x
1
,x
2
), (x
2
,x
3
), (x
3
,x
4
), (x
4
,x
5
), (x
5
,x
6
)}.
Résultat : T est un arbre de recouvrement du graphe G .
2.4.4. THÉORÈME.
Soit H un arbre de recouvrement du graphe G.
Ajouter à H une arête du G n’appartenant pas à H, on a un cycle du H.
Supprimer une arête quelconque de ce cycle, on a un nouvel arbre de
recouvrement du graphe G.
2.4.5. ALGORITHME DE JUSTIFICATION DE CONNEXITÉ.
Considèrons un graphe non orienté G.
Appliquer l’algorithme ci-dessus à G. Alors, après la termination de l’algorithme:
Si H contenant tous les noeuds du G, alors G est connexe et H est un arbre
de recouvrement du graphe G.
Sinon, G n’est pas connexe et H est un arbre de recouvrement d’une
composante connexe du graphe G.
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
22
EXEMPLE 1
. Dans le cas du graphe G de la figure FIG. 2.3. , on a G connexe.
EXEMPLE 2.
Soit G un graphe de la figure suivante :
x
3
x
2
x
1
x
6
x
4
x
5
À partir de x
1
. T= ∅.
1
er
étape. Choisir x
3,
T = {(x
1
,x
3
)}.
2
è
étape. Choisir x
4,
T = {(x
1
,x
3
), (x
3
,x
4
)}.
L’algorithme se termine. T est un arbre de recouvrement d’une composante
connexe du graphe G.
2.4.6. ALGORITHME DE RECHERCHE DE COMPOSANTES CONNEXES.
À l’aide de parcours en profondeur PROF(s), on peut visiter tous les noeuds
appartenant à la même composante connexe du noeud s, alors le nombre de
composantes connexes est égal au nombre de l’appel de cette procedure. On peut
améliorer cette procedure PROF(s) pour indiquer les noeuds de même
composante connexe comme suit :
PROCEDURE PROF(k :integer) ;
//Parcours en profondeur à partir du noeud k
Int i;
{
Mark[k]:= Nocomp;
for (i =1; i≤ n ; i++)
if (a[i,k]==1) && (Mark[i]= =0) PROF(i);
}
PROCEDURE CONNEXE ;
Int i ;
{//Initialisation de Mark (des noeuds a déjà marqué) et Nocomp (nombre
de composantes connexes)
for (j= 1 ;j≤n ; j++) { Mark[j] =0 ; Nocomp =0 ;}
//Appel de la procedure pour determiner des composantes connexes
for (i =1; i≤ n ; i++)
If (Mark [i] = =0) { Nocomp =Nocomp +1 ; PROF(i) ;}
}
End ;
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
23
EXEMPLE.
s
8
s
1
s
2
s
3
s
7
s
6
s
4
s
5
À partir de s
1
. Appel de DFS(1) , on a l’ensemble marqué {s
1
, s
2
, s
6
, s
7
, s
8
}.
i= 3 Appel de DFS(3) , on a l’ensemble marqué {s
3
, s
4
, s
5
}.
Résultat. On a deux composantes connexes.
C
1
= {s
1
, s
2
, s
6
, s
7
, s
8
}.
C
2
= {s
3
, s
4
, s
5
}.
2.5 ARBRES DE RECOUVREMENT MINIMAUX.
PROBLEME 1. Considérons un graphe G = (X,U) connexe, et, à toute arête u,
associons un nombre l(u) que nous appellerons sa longueur. Il s’agit de trouver un
arbre partiel H=(X,V) du graphe d’une longueur totale
∑
u
ul )( minimum.
EXEMPLE. Ce problème se rencontre très souvent en télécommunications et en des
occasions diverses. Posons nous, par exemple, la question suivante : quelle est la
plus courte longueur de câble nécessaire pour relier entre elles n villes données ?
Les villes sont alors les sommets du graphe, et l(x, y) est la distance kilométrique
séparant les villes x et y. Le réseau de câbles cherché doit être connexe, et, puisque
il est de longueur minimum, il n’admet pas de cycles : c’est donc un arbre. On
cherche ici l’arbre le plus « court » possible qui soit un graphe partiel du graphe
complet de n sommets.
Etablissons tout d’abord un lemme.
LEMME. Si G=(X,U) est un graphe complet, et si les longueurs l(u) associées aux
arêtes sont toutes différentes, le Problème 1 admet une solution et une seule (X,V) ;
l’ensemble V={v
1
,v
2
,…,v
n-1
} est obtenu de la fon suivante :on prend pour v
1
la plus
courte arête ; pour v
2
la plus courte arête telle que v
2
≠ v
1
et V
2
= {v
1
,v
2
} ne
contienne pas de cycles;
pour v
3
la plus courte arête telle que v
3
≠ v
2
≠ v
1
et V
3
= {v
1
,v
2
,v
3
} ne contienne
pas de cycles ; etc…
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
24
2.5.1. Algorithme de PRIM (pour le graphe non orienté, valué et connexe).
Notations :
♦ M = L’ ensemble de noeuds non marqués .
♦ Pr(p) = L’ensemble des sommets précédant p à chaque étape.
♦ d = L’ensemble des distance à chaque étape.
♦ Mark = L’ensemble des noeuds marqués.
PRINCIPE DE L’ALGORITHME.
On part d’un arbre initial T réduit à un seul sommet s (e. g. ; s =1)
Ensuite, à chaque itération, on augmente l’arbre T en le connectant au
«Plus proche » sommet libre au sens des poids.
En détaillé, on a comme suit :
1. Au départ du noeud 1. M = {2,…n}
2. À chaque itération, Choisir un noeud à marquer :c’ est le noeud qui a la plus courte
distance.
k = Argmin
x ∈ M
d[x], c’à d d[k] = Min { d[x] : x ∈ M}
Mises à jour d[i], Pr[i] avec i∈ M \{k} à l’aide de la formule:
• d[i] = l[k,i] si d[i] > l[k,i].
• Pr[i] = k.
Remplacer M := M\{k}.
Si M = ∅. L’ algorithme se termine, sinon retourner à 2.
PROCEDURE PRIM ;
//Suppose que l’ on a la matrice de longuers l est Stocké sous la forme de matrice
d’adjacence
//Initialisations de M, d, Pr, Mark
for (i= 1 ; i≤ n ;i++)
{d[i] = l(1,i) ; pr[i] :=1 ; Mark[i] :=0 ;}
Mark[1] :=1 ; n0 :=n-1 ;
WHILE (n0 > 0)
{
k:= Argmin {d[i] : i∈ M} ;
//Remise à jour d, Pr, M et Mark
Mark[k] :=1 ;
∀ i ∈ M { d[i] := l[k,i] si d[i] > l[k,i].
Pr[i] = k.}
//Supprimer le noeud k
M := M\{k} ;
}END WHILE ;
Complexité : O(m log n).
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
25
EXEMPLE. Voir FIG. 2.3.
Les étapes de l’algorithme comme suivant :
Initialisation : M, d, Pr :
M = { 2, 3, 4, 5, 6}
d = [0, 2, 3, 11, 5, 8]
Pr = [1, 1, 1, 1, 1, 1]
1
er
étape. Choisir s
2
. Remise à jour M, d, Pr :
M = { , 3, 4, 5, 6}
d = [0, 2, 1, 10, 5, 8]
Pr = [1, 1, 2, 2, 1, 1]
2
è
étape. s
2
est le sommet actuel. Choisir s
3
. Remise à jour M, d, Pr :
M = { , 3, 4, 5, 6}
d = [0, 2, 1, 6, 5, 8]
Pr = [1, 1, 2, 3, 1, 1]
3
è
étape. s
3
est le sommet actuel. Choisir s
5
. Remise à jour M, d, Pr :
M = { , 3, 4, 5, 6}
d = [0, 2, 1, 4, 5, 7]
Pr = [1, 1, 2, 5, 1, 5]
4
è
étape. s
5
est le sommet actuel. Choisir s
4
. Remise à jour M, d, Pr :
M = { , 3, 4, 5, 6}
d = [0, 2, 1, 4, 5, 7]
Pr = [1, 1, 2, 5, 1, 5]
5
è
étape. s
4
est le sommet actuel. Choisir s
7
. Algorithme se termine car M = ∅.
T = {(x
1
,x
2
) ,(x
2
,x
3
) ,(x
5
,x
4
), (x
1
,x
5
), (x
5
,x
6
)}
l(T) = { 2, 1, 4, 5, 7,}
Somme de poids minimal = 19.
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
26
10 x
3
1 x
2
x
1
2 9 2
3 8 x
6
x
1
6
11 12 5 7 Arbre initial
11
x
4
4 x
5
1 ère arête
Arbre de départ.
x
3
1 x
2
x
3
1 x
2
2 2
x
1
x
1
5
x
5
2 ème arête
3 ème arête
1
x
3
1 x
2
x
3
x
2
2 2
x
6
x
1
x
1
5 5 7
4 4
x
4
x
5
x
4
x
5
4 ème arête 5 ème arête.
FIG. 2.3. Recherche d’un arbre à cỏt minimum par Prim (s=1).
Chapitre 2. Structures Arborescentes
Truong My Dung
Mail=tmdung@fit.hcmuns.edu.vn
27
2.5.2. Algorithme de KRUSKAL (1956).
On procédera par étapes en choisissant chaque fois la plus courte arête qui ne
forme pas de cycles avec les arêtes déjà choisies.
On s’arrête lorsque tous les sommets du graphe sont connectés ou, ce qui revient
au même, lorsque le nombre d’arêtes retenues égale n – 1. C’est un algorithme
glouton, i.e., il fait un choix optimal localement dans l’espoir que ce choix mènera
à la solution optimale globalement. Ici, il rajoute à chaque étape l’arête de poids
minimal à la forêt qu’il construit. L’arbre obtenu est unique si toutes les arêtes sont
initialement de valeurs différentes.
Complexité : O(m log m).
EXEMPLE. Voir FIG. 2.3.
U={(x
2
, x
3
),(x
1
,x
2
),(x
1
,x
3
),(x
4
,x
5
),(x
1
,x
5
),(x
3,
x
4
), (x
5
,x
6
),(x
1
,x
6
),(x
2
,x
6
),(x
2
,x
4
),(x
1
,x
4
),(x
3
,x
4
)}
L(U) = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
Les étapes de l’algorithme comme suivant :
1
er
étape. T= {(x
2
, x
3
)},
L(T) = { 1}
2
è
étape. T= {(x
2
, x
3
),(x
1
,x
2
)},
L(T) = { 1, 2 }
3
è
étape . T= {(x
2
, x
3
),(x
1
,x
2
), ),(x
4
,x
5
)},
L(T) = { 1, 2 , 4 }
4
è
étape. T= {(x
2
, x
3
),(x
1
,x
2
), ),(x
4
,x
5
) ,(x
1
,x
5
)},
L(T) = { 1, 2 , 4, 5 }
5
è
étape. T= {(x
2
, x
3
), (x
1
,x
2
), ),(x
4
,x
5
) ,(x
1
,x
5
) , (x
5
,x
6
)}
Algorithme se termine car Card(T) = 5 = 6 (noeuds) –1.
Somme de poids minimal = 19.
REMARQUE. Sur cet exemple, on retrouve l’arbre à cỏt minimum calculé par
l’algorithme de PRIM. Dans le cas général, on peut trouver un arbre différent,
mais de même poids.
Không có nhận xét nào:
Đăng nhận xét