4.8 Exercices
153
Fig. 4.21. R´ egions R et L de l’exercice 6.
7. Penser ` a un algorithme permettant de tracer le squelette d’un polygone convexe ou
non. En d´ eduire un algorithme permettant de calculer le r-squelette du polygone.
8. Dans le cadre de la chirurgie radioactive au scalpel `
a rayons gamma, supposons
qu’une solution optimale pour une r´ egion R soit donn´ ee par ∪
N
i=1 B(X
∗
i , r i ). Expliquer pourquoi il est naturel que, si I ⊂ {1, . . . , N}, alors ∪ i/ ∈I B(X
∗
i , r i ) est une
solution optimale pour R \ ∪ i∈I B(X
∗
i , r i ).
9. La preuve du th´ eor` eme 4.27 ne s’applique pas au squelette du triangle puisque les
vecteurs tangents aux sommets ne sont pas bien d´ efinis. Montrez (par une autre
m´ ethode) que ce th´ eor` eme est quand mˆ eme valide pour les triangles.
10. Trouver le squelette d’un parall´ el´ epip` ede rectangle avec des arˆ etes de trois longueurs distinctes ? Quel est son r-squelette ?
11. Quel est le squelette d’un t´ etra` edre ? Trouver son r-squelette.
12. Quel est le squelette d’un cˆ one dont la section est une ellipse ?
13. On se donne un ellipso¨ ıde de r´ evolution
x
2
a 2 +
y
2
b 2 +
z
2
b 2 = 1,
avec b < a. Donner son squelette. Justifier votre r´ eponse.
14. Quel est le squelette d’un cylindre dont la base est un disque de rayon r et la
hauteur est h. Vous devrez ´ etudier les trois cas : (i) h > 2r, (ii) h = 2r et (iii)
h < 2r.
15. a) Montrer qu’un graphe connexe est un arbre si et seulement si sa caract´ eristique
d’Euler, d´ efinie comme le nombre de sommets moins le nombre d’arˆ etes, est 1.
153
Fig. 4.21. R´ egions R et L de l’exercice 6.
7. Penser ` a un algorithme permettant de tracer le squelette d’un polygone convexe ou
non. En d´ eduire un algorithme permettant de calculer le r-squelette du polygone.
8. Dans le cadre de la chirurgie radioactive au scalpel `
a rayons gamma, supposons
qu’une solution optimale pour une r´ egion R soit donn´ ee par ∪
N
i=1 B(X
∗
i , r i ). Expliquer pourquoi il est naturel que, si I ⊂ {1, . . . , N}, alors ∪ i/ ∈I B(X
∗
i , r i ) est une
solution optimale pour R \ ∪ i∈I B(X
∗
i , r i ).
9. La preuve du th´ eor` eme 4.27 ne s’applique pas au squelette du triangle puisque les
vecteurs tangents aux sommets ne sont pas bien d´ efinis. Montrez (par une autre
m´ ethode) que ce th´ eor` eme est quand mˆ eme valide pour les triangles.
10. Trouver le squelette d’un parall´ el´ epip` ede rectangle avec des arˆ etes de trois longueurs distinctes ? Quel est son r-squelette ?
11. Quel est le squelette d’un t´ etra` edre ? Trouver son r-squelette.
12. Quel est le squelette d’un cˆ one dont la section est une ellipse ?
13. On se donne un ellipso¨ ıde de r´ evolution
x
2
a 2 +
y
2
b 2 +
z
2
b 2 = 1,
avec b < a. Donner son squelette. Justifier votre r´ eponse.
14. Quel est le squelette d’un cylindre dont la base est un disque de rayon r et la
hauteur est h. Vous devrez ´ etudier les trois cas : (i) h > 2r, (ii) h = 2r et (iii)
h < 2r.
15. a) Montrer qu’un graphe connexe est un arbre si et seulement si sa caract´ eristique
d’Euler, d´ efinie comme le nombre de sommets moins le nombre d’arˆ etes, est 1.