USTHB, FI - L3 Info. - Th. GRA.

, Série 3 2023/2024

Chapitre 3 Exercice 1
Arbre de Couverture Optimal • Montrer que :
– la moyenne des degrés des sommets d’un arbre
Série d’exercices de TD
– est strictement inférieure à 2.

Présenté par :
H. BENKAOUHA
Bureau 222, Faculté d’Informatique, USTHB
[email protected]
[email protected]

Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique

1 2
(USTHB) (USTHB)

Exercice 1 – Solution Exercice 2

• Trouver l’arbre de poids minimum puis l’arbre de
• Par définition, dans un graphe d’ordre n et de poids maximum.
taille m qui est un arbre, on a m=n – 1
• D’un autre coté on a la somme des degrés est
2m
• Donc la moyenne est 2m/n
• On remplace m par n – 1
• Moyenne_degrés = 2(n – 1)/n = 2n/n – 2/n
= 2 – 2/n < 2 • Donner le codage de Prufer correspondant à l’arbre
trouvé
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
3 4
(USTHB) (USTHB)

Exercice 2 – Solution (1/4)

• On applique l’algorithme de Kruksal pour Exercice 2 – Solution (1/4)
trouver l’arbre de couverture de poids min. • Algo. de Kruksal (1/7)
• Tri par ordre croissant des arêtes 7 7

Arête Poids Décision Arête Poids Décision Arête Poids Décision Arête Poids Décision
1 1
{2,7} 1 {3,8} 3 {2,7} 1 Oui {3,8} 3 1
{5,6} 1 {4,8} 3 {5,6} 1 {4,8} 3
{1,6} 2 {3,5} 4 2 {1,6} 2 {3,5} 4 2
8 8
{3,6} 2 {4,5} 4 {3,6} 2 {4,5} 4
6 6
{7,8} 2 {1,2} 5 {7,8} 2 {1,2} 5
{1,5} 3 {3,4} 5 3 {1,5} 3 {3,4} 5 3

{1,7} 3 {4,7} 5 {1,7} 3 {4,7} 5

{2,3} 3 {2,3} 3
5 4 5 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
5 6
(USTHB) (USTHB)

Enseignant : Dr. H. BENKAOUHA

([email protected]) 1
USTHB, FI - L3 Info. - Th. GRA., Série 3 2023/2024

Exercice 2 – Solution (1/4)

• Algo. de Kruksal (2/7)
Exercice 2 – Solution (1/4)
• Algo. de Kruksal (3/7)
7 7

Arête Poids Décision Arête Poids Décision Arête Poids Décision Arête Poids Décision
1 1
{2,7} 1 Oui {3,8} 3 1 {2,7} 1 Oui {3,8} 3 1
{5,6} 1 Oui {4,8} 3 {5,6} 1 Oui {4,8} 3 2
{1,6} 2 {3,5} 4 2 {1,6} 2 Oui {3,5} 4 2
8 8
{3,6} 2 {4,5} 4 {3,6} 2 {4,5} 4
6 6
{7,8} 2 {1,2} 5 {7,8} 2 {1,2} 5
{1,5} 3 {3,4} 5 3 {1,5} 3 {3,4} 5 3
1 1
{1,7} 3 {4,7} 5 {1,7} 3 {4,7} 5
{2,3} 3 {2,3} 3
5 4 5 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
7 8
(USTHB) (USTHB)

Exercice 2 – Solution (1/4) Exercice 2 – Solution (1/4)

• Algo. de Kruksal (4/7) • Algo. de Kruksal (5/7)
7 7

Arête Poids Décision Arête Poids Décision Arête Poids Décision Arête Poids Décision
1 1 2
{2,7} 1 Oui {3,8} 3 1 {2,7} 1 Oui {3,8} 3 1
{5,6} 1 Oui {4,8} 3 2 {5,6} 1 Oui {4,8} 3 2
{1,6} 2 Oui {3,5} 4 2 {1,6} 2 Oui {3,5} 4 2
8 8
{3,6} 2 Oui {4,5} 4 {3,6} 2 Oui {4,5} 4
6 6
2 2
{7,8} 2 {1,2} 5 {7,8} 2 Oui {1,2} 5
{1,5} 3 {3,4} 5 3 {1,5} 3 {3,4} 5 3
1 1
{1,7} 3 {4,7} 5 {1,7} 3 {4,7} 5
{2,3} 3 {2,3} 3
5 4 5 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
9 10
(USTHB) (USTHB)

Exercice 2 – Solution (1/4)

Exercice 2 – Solution (1/4) • Algo. de Kruksal (7/7)
• Algo. de Kruksal (6/7) Arête Poids Décision
Arête Poids Décision
7 {2,7} 1 Oui 7
3 {3,8} 3 Non 3
{5,6} 1 Oui
Arête Poids Décision Arête Poids Décision {4,8} 3 Oui
1 2 {1,6} 2 Oui 1 2
{2,7} 1 Oui {3,8} 3 1 {3,5} 4 Non 1
{3,6} 2 Oui
{5,6} 1 Oui {4,8} 3 2 {4,5} 4 Non 2
{7,8} 2 Oui
{1,6} 2 Oui {3,5} 4 2 {1,2} 5 Non 2
8 {1,5} 3 Non 8
{3,6} 2 Oui {4,5} 4 {3,4} 5 Non
6
2 {1,7} 3 Oui 6
2
{7,8} 2 Oui {1,2} 5 {4,7} 5 Non
{2,3} 3 Non
{1,5} 3 Non {3,4} 5 3 3
3
1 1
{1,7} 3 Oui {4,7} 5
{2,3} 3
– Poids de l’arbre de couverture
5 4
de poids minimal : 14 5 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
11 12
(USTHB) (USTHB)

Enseignant : Dr. H. BENKAOUHA

([email protected]) 2
USTHB, FI - L3 Info. - Th. GRA., Série 3 2023/2024

Exercice 2 Exercice 2 – Solution (2/4)

• Trouver l’arbre de poids minimum puis l’arbre de • On applique l’algorithme de Kruksal pour
poids maximum. trouver l’arbre de couverture de poids max.
• Tri par ordre croissant des arêtes 3 7 5

Arête Poids Décision

Arête Poids Décision 1
{2,7} 1 2
1
{3,8} 3 5
{5,6} 1 2
{4,8} 3
{1,6} 2 3
2
{3,5} 4 8
{3,6} 2 3
{4,5} 4 6
2
3
{7,8} 2
{1,2} 5
{1,5} 3 3
{3,4} 5 3
1
{1,7} 3 5
• Donner le codage de Prufer correspondant à l’arbre {2,3} 3
{4,7} 5 4

trouvé 5 4 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
13 14
(USTHB) (USTHB)

Exercice 2 – Solution (2/4) Exercice 2 – Solution (2/4)

• Algo. de Kruksal 1/11 • Algo. de Kruksal 2/11
1 1
Arête Poids Décision Arête Poids Décision 3
Arête Poids Décision Arête Poids Décision
{2,7} 1 Non 5 {2,7} 1 Non 5
{3,8} 3 7 {3,8} 3 7
{5,6} 1 3 {5,6} 1 Non
{4,8} 3 {4,8} 3
{1,6} 2 {1,6} 2
{3,5} 4 2 {3,5} 4 2
{3,6} 2 5 {3,6} 2 5
{4,5} 4 2
{4,5} 4 2
{7,8} 2 {7,8} 2
{1,2} 5 2 {1,2} 5 2
{1,5} 3 3 8 {1,5} 3 3 8
{3,4} 5 3 {3,4} 5 3
{1,7} 3 6 3 {1,7} 3 6 3
{4,7} 5 2 {4,7} 5 2
{2,3} 3 {2,3} 3
3 3
3 3
1
5 5
4 4
5 4 4 5 4 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
15 16
(USTHB) (USTHB)

Exercice 2 – Solution (2/4) Exercice 2 – Solution (2/4)

• Algo. de Kruksal 3/11 • Algo. de Kruksal 4/11
1 1
Arête Poids Décision 3 Arête Poids Décision 3
Arête Poids Décision Arête Poids Décision
{2,7} 1 Non 5 {2,7} 1 Non 5
{3,8} 3 7 {3,8} 3 7
{5,6} 1 Non {5,6} 1 Non
{4,8} 3 {4,8} 3
{1,6} 2 Non 5 {1,6} 2 Non 5
{3,5} 4 2 {3,5} 4 2
{3,6} 2 {3,6} 2 Oui
{4,5} 4 {4,5} 4
{7,8} 2 {7,8} 2
{1,2} 5 2 {1,2} 5 2
{1,5} 3 3 8 {1,5} 3 3 8
{3,4} 5 3 {3,4} 5 3
{1,7} 3 6 3 {1,7} 3 6 3
{4,7} 5 2 {4,7} 5 2
{2,3} 3 {2,3} 3
3 3
3 3
5 5
4 4
5 4 4 5 4 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
17 18
(USTHB) (USTHB)

Enseignant : Dr. H. BENKAOUHA

([email protected]) 3
USTHB, FI - L3 Info. - Th. GRA., Série 3 2023/2024

Exercice 2 – Solution (2/4) Exercice 2 – Solution (2/4)

• Algo. de Kruksal 5/11 • Algo. de Kruksal 6/11
1 1
Arête Poids Décision 3 Arête Poids Décision 3
Arête Poids Décision Arête Poids Décision
{2,7} 1 Non 5 {2,7} 1 Non 5
{3,8} 3 7 {3,8} 3 7
{5,6} 1 Non {5,6} 1 Non
{4,8} 3 5
{4,8} 3 5
{1,6} 2 Non {1,6} 2 Non
{3,5} 4 {3,5} 4
{3,6} 2 Oui {3,6} 2 Oui
{4,5} 4 {4,5} 4
{7,8} 2 Non {7,8} 2 Non
{1,2} 5 2 {1,2} 5 2
{1,5} 3 3 8 {1,5} 3 Non 8
{3,4} 5 3 {3,4} 5 3
{1,7} 3 6 3 {1,7} 3 6 3
{4,7} 5 2 {4,7} 5 2
{2,3} 3 {2,3} 3
3 3
3 3
5 5
4 4
5 4 4 5 4 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
19 20
(USTHB) (USTHB)

Exercice 2 – Solution (2/4) Exercice 2 – Solution (2/4)

• Algo. de Kruksal 7/11 • Algo. de Kruksal 8/11
1 1
Arête Poids Décision Arête Poids Décision
Arête Poids Décision Arête Poids Décision
{2,7} 1 Non 5 {2,7} 1 Non 5
{3,8} 3 7 {3,8} 3 7
{5,6} 1 Non {5,6} 1 Non
{4,8} 3 5
{4,8} 3 5
{1,6} 2 Non {1,6} 2 Non
{3,5} 4 {3,5} 4
{3,6} 2 Oui {3,6} 2 Oui
{4,5} 4 {4,5} 4
{7,8} 2 Non {7,8} 2 Non
{1,2} 5 2 {1,2} 5 2
{1,5} 3 Non 8 {1,5} 3 Non 8
{3,4} 5 3 {3,4} 5 3
{1,7} 3 Non 6 3 {1,7} 3 Non 6 3
{4,7} 5 2 {4,7} 5 2
{2,3} 3 {2,3} 3 Oui
3 3
3 3
5 5
4 4
5 4 4 5 4 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
21 22
(USTHB) (USTHB)

Exercice 2 – Solution (2/4) Exercice 2 – Solution (2/4)

• Algo. de Kruksal 9/11 • Algo. de Kruksal 10/11
1 1
Arête Poids Décision Arête Poids Décision
Arête Poids Décision Arête Poids Décision
{2,7} 1 Non 5 {2,7} 1 Non 5
{3,8} 3 Non 7 {3,8} 3 Non 7
{5,6} 1 Non {5,6} 1 Non
{4,8} 3 5
{4,8} 3 Oui 5
{1,6} 2 Non {1,6} 2 Non
{3,5} 4 {3,5} 4
{3,6} 2 Oui {3,6} 2 Oui
{4,5} 4 {4,5} 4
{7,8} 2 Non {7,8} 2 Non
{1,2} 5 2 {1,2} 5 2
{1,5} 3 Non 8 {1,5} 3 Non 8
{3,4} 5 3 {3,4} 5 3
{1,7} 3 Non 6
2 {1,7} 3 Non 6
2
{4,7} 5 {4,7} 5
{2,3} 3 Oui {2,3} 3 Oui
3 3
3 3
5 5
4 4
5 4 4 5 4 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
23 24
(USTHB) (USTHB)

Enseignant : Dr. H. BENKAOUHA

([email protected]) 4
USTHB, FI - L3 Info. - Th. GRA., Série 3 2023/2024

Exercice 2 – Solution (2/4) Exercice 2 – Solution (2/4)

• Algo. de Kruksal 11/11 • Algo. de Kruksal (fin)
1 1
Arête Poids Décision Arête Poids Décision
Arête Poids Décision Arête Poids Décision
{2,7} 1 Non 5 {2,7} 1 Non 5
{3,8} 3 Non 7 {3,8} 3 Non 7
{5,6} 1 Non {5,6} 1 Non
{4,8} 3 Oui 5
{4,8} 3 Oui 5
{1,6} 2 Non {1,6} 2 Non
{3,5} 4 Non {3,5} 4 Non
{3,6} 2 Oui {3,6} 2 Oui
{4,5} 4 {4,5} 4 Oui
{7,8} 2 Non {7,8} 2 Non
{1,2} 5 2 {1,2} 5 Oui 2
{1,5} 3 Non 8 {1,5} 3 Non 8
{3,4} 5 3 {3,4} 5 Oui 3
{1,7} 3 Non 6
2 {1,7} 3 Non 6
2
{4,7} 5 {4,7} 5 Oui
{2,3} 3 Oui {2,3} 3 Oui
3 3
On prend toutes les arêtes 5
3
Poids de l’arbre de couverture 5
3

restantes de poids max : 27

5 4 4 5 4 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
25 26
(USTHB) (USTHB)

Exercice 2 – Solution (3/4) Exercice 2 – Solution (3/4)

• Codage de Prufer (1/7) de l’arbre de • Codage de Prufer (2/7) de l’arbre de
couverture de poids minimal 7 couverture de poids minimal 7

– Sommets de degré 1 : – Supprimer 2 et l’arête incidente

– 2, 3, 4, 5 – Sommets de degré 1 :
1 1
– Le min : 2 – 3, 4, 5
– 2 est relié à 7 2
– Le min : 3
– P=7 8
– 3 est relié à 6 8
6 6
– P=7 6
3 3

5 4 5 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
27 28
(USTHB) (USTHB)

Exercice 2 – Solution (3/4) Exercice 2 – Solution (3/4)

• Codage de Prufer (3/7) de l’arbre de • Codage de Prufer (4/7) de l’arbre de
couverture de poids minimal 7 couverture de poids minimal 7

– Supprimer 3 et l’arête incidente – Supprimer 4 et l’arête incidente

– Sommets de degré 1 : – Sommets de degré 1 :
1 1
– 4, 5 – 5, 8
– Le min : 4 – Le min : 5
– 4 est relié à 8 8
– 5 est relié à 6 8
6 6
– P=7 6 8 – P=7 6 8 6

5 4 5
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
29 30
(USTHB) (USTHB)

Enseignant : Dr. H. BENKAOUHA

([email protected]) 5
USTHB, FI - L3 Info. - Th. GRA., Série 3 2023/2024

Exercice 2 – Solution (3/4) Exercice 2 – Solution (3/4)

• Codage de Prufer (5/7) de l’arbre de • Codage de Prufer (6/7) de l’arbre de
couverture de poids minimal 7 couverture de poids minimal 7

– Supprimer 5 et l’arête incidente – Supprimer 6 et l’arête incidente

– Sommets de degré 1 : – Sommets de degré 1 :
1 1
– 6, 8 – 1, 8
– Le min : 6 – Le min : 1
– 6 est relié à 1 8
– 1 est relié à 7 8
6
– P=7 6 8 6 1 – P=7 6 8 6 1 7

Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique

31 32
(USTHB) (USTHB)

Exercice 2 – Solution (3/4) Exercice 2 – Solution (4/4)

• Codage de Prufer (7/7) de l’arbre de • Codage de Prufer (1/7) de l’arbre de
couverture de poids minimal 7 couverture de poids maximal 1
– Supprimer 1 et l’arête incidente – Sommets de degré 1 : 7

– Il ne reste que 2 sommet – 1, 5, 6, 7, 8

 Fin. – Le min : 1
– P=7 6 8 6 1 7 – 1 est relié à 2 2
8
– P=2 8
6

5 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
33 34
(USTHB) (USTHB)

Exercice 2 – Solution (4/4) Exercice 2 – Solution (4/4)

• Codage de Prufer (2/7) de l’arbre de • Codage de Prufer (3/7) de l’arbre de
couverture de poids minimal couverture de poids minimal
– Supprimer 1 et l’arête incidente 7 – Supprimer 2 et l’arête incidente 7

– Sommets de degré 1 : – Sommets de degré 1 :

– 2, 5, 6, 7, 8 – 5, 6, 7, 8
– Le min : 2 2
– Le min : 5
– 2 est relié à 3 8
– 5 est relié à 4 8
6 6
– P=2 3 – P=2 3 4
3 3

5 4 5 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
35 36
(USTHB) (USTHB)

Enseignant : Dr. H. BENKAOUHA

([email protected]) 6
USTHB, FI - L3 Info. - Th. GRA., Série 3 2023/2024

Exercice 2 – Solution (4/4) Exercice 2 – Solution (4/4)

• Codage de Prufer (4/7) de l’arbre de • Codage de Prufer (5/7) de l’arbre de
couverture de poids minimal couverture de poids minimal
– Supprimer 5 et l’arête incidente 7 – Supprimer 6 et l’arête incidente 7

– Sommets de degré 1 : – Sommets de degré 1 :

– 6, 7, 8 – 3, 7, 8
– Le min : 6 – Le min : 3
– 6 est relié à 3 8
– 3 est relié à 4 8
6
– P=2 3 4 3 – P=2 3 4 3 4
3 3

4 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
37 38
(USTHB) (USTHB)

Exercice 2 – Solution (4/4) Exercice 2 – Solution (4/4)

• Codage de Prufer (6/7) de l’arbre de • Codage de Prufer (7/7) de l’arbre de
couverture de poids minimal couverture de poids minimal
– Supprimer 3 et l’arête incidente 7 – Supprimer 7 et l’arête incidente
– Sommets de degré 1 : – Il ne reste que 2 sommet
– 7, 8  Fin.
– Le min : 7 – P=2 3 4 3 4 4
– 7 est relié à 4 8 8

– P=2 3 4 3 4 4

4 4
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
39 40
(USTHB) (USTHB)

Exercice 3 Exercice 3 - Suite

• On désire installer au moindre coût un réseau 1. Identifier le problème associé.
de communication entre divers sites. 2. Déterminer la solution optimale.
• Les coûts des connexions intersites sont les
suivants (symétriques) :
B C D E F G H
A 5 18 9 13 7 38 22
B 17 11 7 10 38 15
C 27 23 15 20 25
D 20 15 40 25
E 15 40 30
F 35 10
Dr. H. BENKAOUHA - Faculté d'Informatique
(USTHB)
G 45 41
Dr. H. BENKAOUHA - Faculté d'Informatique
(USTHB)
42

Enseignant : Dr. H. BENKAOUHA

([email protected]) 7
USTHB, FI - L3 Info. - Th. GRA., Série 3 2023/2024

Exercice 3 – Solution (1/4) Exercice 3 – Solution (2/4)

1. Identifier le problème associé. 1. Identifier le problème associé.
• Modélisation • Identification
– Chaque sommet x représente un site x, x de A à H. – Tous les sites connectés : graphe connexe
– Chaque arête {i, j} représente une connexion – Coût minimal : graphe connexe minimal avec
intersites. somme de poids des arêtes minimal
– Le coût de la connexion intersites est représenté – Revient à trouver l’arbre de couverture maximal de
par le poids de l’arête correspondante. poids minimal.

Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique

43 44
(USTHB) (USTHB)

Exercice 3 – Solution (3/4) Exercice 3 – Solution (4/4)

2. Déterminer la solution optimale. 2. Déterminer la solution optimale : Kruksal (1/8) H
– On applique l’algorithme de Kruksal Arête Poids Décision A
F
– Tri par ordre croissant des arêtes {A,B} 5
Arête Poids Décision Arête Poids Décision Arête Poids Décision {A,F} 7
{A,B} 5 {D,F} 15 {D,H} 25 {B,E} 7
{A,F} 7 {E,F} 15 {C,D} 27 {A,D} 9
{B,E} 7 {B,C} 17 {E,H} 30 {D,F} 10 C
{A,D} 9 {A,C} 18 {F,G} 35 {F,H} 10 B D
{D,F} 10 {C,G} 20 {A,G} 38 {B,D} 11
{F,H} 10 {D,E} 20 {B,G} 38 {A,E} 13
{B,D} 11 {A,H} 22 {D,G} 40 {B,H} 15
{A,E} 13 {C,E} 23 {E,G} 40 {C,F} 15
G
{B,H} 15 {C,H} 25 {G,H} 45
E
{C,F} 15 Dr. H. BENKAOUHA - Faculté d'Informatique
45
Dr. H. BENKAOUHA - Faculté d'Informatique
46
(USTHB) (USTHB)

Exercice 3 – Solution (4/4) Exercice 3 – Solution (4/4)

2. Déterminer la solution optimale : Kruksal (2/8) H 2. Déterminer la solution optimale : Kruksal (3/8) H
Arête Poids Décision A Arête Poids Décision A 7
F F
{A,B} 5 Oui {A,B} 5 Oui
{A,F} 7 {A,F} 7 Oui
{B,E} 7 {B,E} 7
5 5
{A,D} 9 {A,D} 9
{D,F} 10 C {D,F} 10 C
{F,H} 10 B D {F,H} 10 B D
{B,D} 11 {B,D} 11
{A,E} 13 {A,E} 13
{B,H} 15 {B,H} 15
{C,F} 15 {C,F} 15
G G
E E
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
47 48
(USTHB) (USTHB)

Enseignant : Dr. H. BENKAOUHA

([email protected]) 8
USTHB, FI - L3 Info. - Th. GRA., Série 3 2023/2024

Exercice 3 – Solution (4/4) Exercice 3 – Solution (4/4)

2. Déterminer la solution optimale : Kruksal (4/8) H 2. Déterminer la solution optimale : Kruksal (5/8) H
Arête Poids Décision A 7 Arête Poids Décision A 7
F F
{A,B} 5 Oui {A,B} 5 Oui
{A,F} 7 Oui {A,F} 7 Oui
{B,E} 7 Oui {B,E} 7 Oui 9
5 5
{A,D} 9 {A,D} 9 Oui
{D,F} 10 C {D,F} 10 C
{F,H} 10 B D {F,H} 10 B D
{B,D} 11 {B,D} 11
{A,E} 13 {A,E} 13
7 7
{B,H} 15 {B,H} 15
{C,F} 15 {C,F} 15
G G
E E
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
49 50
(USTHB) (USTHB)

Exercice 3 – Solution (4/4) Exercice 3 – Solution (4/4)

2. Déterminer la solution optimale : Kruksal (6/8) H 2. Déterminer la solution optimale : Kruksal (7/8) H
Arête Poids Décision 7 10 Arête Poids Décision 7 10
A A
F F
{A,B} 5 Oui {A,B} 5 Oui
{A,F} 7 Oui {A,F} 7 Oui
9 9 15
{B,E} 7 Oui {B,E} 7 Oui
5 5
{A,D} 9 Non {A,D} 9 Non
{D,F} 10 Non C {D,F} 10 Non C
{F,H} 10 Oui B D {F,H} 10 Oui B D
{B,D} 11 {B,D} 11 Non
{A,E} 13 {A,E} 13 Non
7 7
{B,H} 15 {B,H} 15 Non
{C,F} 15 {C,F} 15 Oui
G G
E E
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
51 52
(USTHB) (USTHB)

Exercice 3 – Solution (4/4) Exercice 4

2. Déterminer la solution optimale : Kruksal (8/8) H
Arête Poids Décision A 7 10 • Un arbre est dit binaire, s’il est constitué :
F
{D,F} 15 Non – d’un unique sommet de degré 2 (appelé racine de
{E,F} 15 Non
15
l’arbre)
9
{B,C} 17 Non
5 – et tout autre sommet est soit de degré 3, soit de
{A,C} 18 Non
degré 1.
{C,G} 20 Oui C
{D,E} 20 B D • Les sommets de degré 1 sont appelés les feuilles
{A,H} 22 de l’arbre.
{C,E} 23 20

{C,H} 25
7
• Exemple de 9 sommets
Arbre de poids = 73 G
et 5 feuilles
E
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
53 54
(USTHB) (USTHB)

Enseignant : Dr. H. BENKAOUHA

([email protected]) 9
USTHB, FI - L3 Info. - Th. GRA., Série 3 2023/2024

Exercice 4 - Suite Exercice 4 – Solution (1/7)

1. Énumérez (à isomorphisme près) tous les 1. Énumérez (à isomorphisme près) tous les
arbres binaires ayant exactement 7 feuilles. arbres binaires ayant exactement 7 feuilles.
2. Combien de sommets peut avoir un arbre
binaire ayant exactement 7 feuilles.
3. Combien de sommets peut avoir un arbre
binaire ayant exactement k feuilles (avec k 2).

Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique

55 56
(USTHB) (USTHB)

Exercice 4 – Solution (2/7) Exercice 4 – Solution (3/7)

1. Énumérez (à isomorphisme près) tous les 1. Énumérez (à isomorphisme près) tous les
arbres binaires ayant exactement 7 feuilles. arbres binaires ayant exactement 7 feuilles.

Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique

57 58
(USTHB) (USTHB)

Exercice 4 – Solution (4/7) Exercice 4 – Solution (5/7)

1. Énumérez (à isomorphisme près) tous les 2. Combien de sommets peut avoir un arbre
arbres binaires ayant exactement 7 feuilles. binaire ayant exactement 7 feuilles.
• Il y a 13 sommets selon la question précédente.

Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique

59 60
(USTHB) (USTHB)

Enseignant : Dr. H. BENKAOUHA

([email protected]) 10
USTHB, FI - L3 Info. - Th. GRA., Série 3 2023/2024

Exercice 4 – Solution (6/7) Exercice 4 – Solution (7/7)

3. Combien de sommets peut avoir un arbre 3. Combien de sommets peut avoir un arbre
binaire ayant exactement k feuilles (avec k 2). binaire ayant exactement k feuilles (avec k 2).
• On pose n le nombre de sommets et m le • n=k+p+1 … (1)
nombre d’arêtes • k + 3p + 2 = 2m … (2)
• On a k feuilles (degré 1), 1 racine (degré 2) et p • m=n–1 … (3)
autres sommets (degré 3) • De (2) et (3)  k + 3p + 2 = 2 (n–1) … (4)
• n=k+p+1 • De (1)  p=n – k – 1
• 2*1 + 1*k + 3*p = 2m (formule des degrés) • On remplace dans (4)  k+3(n–k–1)+2=2(n–1)
• m=n–1 (propriété d’un arbre) •  k+3n–3k–3+2=2n–2  n–2k=–1  n=2k–1
Dr. H. BENKAOUHA - Faculté d'Informatique Dr. H. BENKAOUHA - Faculté d'Informatique
61 62
(USTHB) (USTHB)

Enseignant : Dr. H. BENKAOUHA

([email protected]) 11