7/25/2019 graphesol_2
1/2
arbres et graphes
1. Etant donne un arbre T et un noeud v de T, on appelle
excentricite de v, la
longueur du plus long chemin entre v et lun des autres noeuds de
T. Un noeud de Tdexcentricite minimum est appele le centre de
T.
a) Donner un algorithme efficace pour trouver le centre dun
arbreT.Reponse :
1. Enlever toutes les feuilles de T. Soit T1 larbre restant.
2. Enlever toutes les feuilles de T1. Soit T2 larbre
restant.
3. Repeter loperation enlever comme suit : Enlever toutes les
feuilles de Ti.Soit Ti+1 larbre restant.
4. Lorsque larbre restant na plus quun ou deux noeuds, arreter.
Supposons
que cet arbre est Tk
.5. Si Tk contient un seul noeud, ce noeud est le centre de T.
Lexcentricite du
noeud est k.
6. Si Tk contient deux noeuds, lun ou lautre est un centre pour
T. Lexcentri-cite est alors de k + 1.
b) Est-ce que le centre est unique ?Reponse : Non, il arrive
quil y ait deux centres possibles. Dans larbre 1 ci-dessous, le
centre estDavec excentricite 2. Dans larbre 2, le centre est soit D
ouEavec excentricite 3.
A
B
C D E
F
Garbre 1
A
B
C D E F
H
G
arbre 2
2. Etant donne un arbre T, le diametre de Test la longueur du
plus long chemin entredeux noeuds de larbre T. Donnez un algorithme
efficace pour calculer le diametre deT.
Reponse : On peut obtenir le diametre de larbre en modifiant un
peu lalgorithme
donne en 1. Lorsquon a trouveTk
un arbre contenant un ou deux noeuds alors, siTk
na quun seul noeud, le diametre est 2k et si Tk a deux noeuds,
le diametre est 2k + 1.
3.Supposons que le reseau RT&T est represente par un graphe
ayant nsommets et maretes. Donnez un algorithme efficace qui
calcule, pour chaque sommet du graphe, lenombre de sommets pouvant
etre rejoints par un chemin de longueur au plus 4.
Reponse :Pour chaque sommetv du graphe, on execute un parcours
en largeur (BFS)a partir de v qui sarrete des que le niveau 4 est
calcule (i.e on calcule L0, L1, L2 etL3.) Une autre facon de
proceder est dexecuter, pour chaque sommet v du graphe,
1
