4.5 Un algorithme num´ erique
139
permet de d´ ecider quand arrˆ eter. Si l’on veut am´ eliorer l’algorithme, on lui fait choisir
plusieurs doses initiales B(X
∗
1 , r 1 ) et, pour chacune, plusieurs doses subs´ equentes.
4.5 Un algorithme num´ erique pour trouver le squelette
C’est un probl` eme non trivial que de programmer un bon algorithme pour trouver le
squelette d’une r´ egion. Nous nous limiterons ici `
a examiner le probl` eme pour une r´ egion
plane R. Nous admettrons sans preuve que, si notre r´ egion est simplement connexe
(c’est-` a-dire d’un seul tenant et sans trou), alors le squelette est un graphe particulier
appel´ e arbre.
Les d´ efinitions de graphe varient dans la litt´ erature. Dans cette section, nous
consid´ erons des graphes non orient´ es.
D´ efinition 4.14 1. Un graphe (non orient´ e) est form´ e d’un ensemble de sommets
S 1 , . . . , S n et d’arˆ etes joignant deux sommets. Pour chaque paire de sommets
{S i , S j } distincts, i = j ∈ {1, . . . , n}, on a au plus une arˆ ete de sommets S i et
S j .
2. On dit que deux graphes sont ´ equivalents si les deux conditions suivantes sont satisfaites :
• on a une bijection h entre les sommets du premier graphe et ceux du second
graphe ;
• il y a une arˆ ete entre S i et S j dans le premier graphe si et seulement si il y a une
arˆ ete entre h(S i ) et h(S j ) dans le second graphe.
D´ efinition 4.15 1. Un graphe est connexe si, pour toute paire de sommets S i et S j , il
existe des sommets T 1 = S i , T 2 , . . . , T n−1 , T n = S j tels que chaque paire de sommets
cons´ ecutifs {T m , T m+1 } est connect´ ee par une arˆ ete. La suite {T 1 , . . . T n } est un
chemin entre S i et S j .
2. ´
Etant donn´ e un graphe, un ensemble d’arˆ etes distinctes A i , i = 1, . . . , n, de sommets
respectifs S i et S i+1 , est un cycle si S 1 = S n+1 .
3. Un graphe est un arbre s’il est connexe et n’a pas de cycle.
Num´ eriquement, on teste si les points int´ erieurs d’une r´ egion sont sur le squelette.
Les erreurs num´ eriques peuvent conduire `
a deux types de probl` emes :
(i) Le squelette peut devenir non connexe si on a manqu´ e certains points.
(ii) Au contraire, on peut voir des branches suppl´ ementaires si on a faussement inclus
des points dans le squelette.
Dans tous les cas, on a chang´ e la « topologie » du squelette. D’o` u l’importance d’un
algorithme « robuste », c’est-` a-dire qui ne produise pas de tels d´ efauts. Nous allons
d´ ecrire un algorithme de [2].
139
permet de d´ ecider quand arrˆ eter. Si l’on veut am´ eliorer l’algorithme, on lui fait choisir
plusieurs doses initiales B(X
∗
1 , r 1 ) et, pour chacune, plusieurs doses subs´ equentes.
4.5 Un algorithme num´ erique pour trouver le squelette
C’est un probl` eme non trivial que de programmer un bon algorithme pour trouver le
squelette d’une r´ egion. Nous nous limiterons ici `
a examiner le probl` eme pour une r´ egion
plane R. Nous admettrons sans preuve que, si notre r´ egion est simplement connexe
(c’est-` a-dire d’un seul tenant et sans trou), alors le squelette est un graphe particulier
appel´ e arbre.
Les d´ efinitions de graphe varient dans la litt´ erature. Dans cette section, nous
consid´ erons des graphes non orient´ es.
D´ efinition 4.14 1. Un graphe (non orient´ e) est form´ e d’un ensemble de sommets
S 1 , . . . , S n et d’arˆ etes joignant deux sommets. Pour chaque paire de sommets
{S i , S j } distincts, i = j ∈ {1, . . . , n}, on a au plus une arˆ ete de sommets S i et
S j .
2. On dit que deux graphes sont ´ equivalents si les deux conditions suivantes sont satisfaites :
• on a une bijection h entre les sommets du premier graphe et ceux du second
graphe ;
• il y a une arˆ ete entre S i et S j dans le premier graphe si et seulement si il y a une
arˆ ete entre h(S i ) et h(S j ) dans le second graphe.
D´ efinition 4.15 1. Un graphe est connexe si, pour toute paire de sommets S i et S j , il
existe des sommets T 1 = S i , T 2 , . . . , T n−1 , T n = S j tels que chaque paire de sommets
cons´ ecutifs {T m , T m+1 } est connect´ ee par une arˆ ete. La suite {T 1 , . . . T n } est un
chemin entre S i et S j .
2. ´
Etant donn´ e un graphe, un ensemble d’arˆ etes distinctes A i , i = 1, . . . , n, de sommets
respectifs S i et S i+1 , est un cycle si S 1 = S n+1 .
3. Un graphe est un arbre s’il est connexe et n’a pas de cycle.
Num´ eriquement, on teste si les points int´ erieurs d’une r´ egion sont sur le squelette.
Les erreurs num´ eriques peuvent conduire `
a deux types de probl` emes :
(i) Le squelette peut devenir non connexe si on a manqu´ e certains points.
(ii) Au contraire, on peut voir des branches suppl´ ementaires si on a faussement inclus
des points dans le squelette.
Dans tous les cas, on a chang´ e la « topologie » du squelette. D’o` u l’importance d’un
algorithme « robuste », c’est-` a-dire qui ne produise pas de tels d´ efauts. Nous allons
d´ ecrire un algorithme de [2].