Mémoire de M2

Mémoire de M2

-

Documents
24 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

  • rapport de stage
  • rapport de stage - matière potentielle : mpri
  • exposé
Déformation de graphes sur les surfaces Arnaud de Mesmay Sous la direction d'Éric Colin de Verdière Laboratoire d'Informatique de l'École Normale Supérieure Août 2011 Le contexte général Mon stage s'inscrit dans le domaine de la topologie algorithmique. Cette discipline encore très jeune vise à formaliser et à résoudre des versions algorithmiques de problèmes issus de la topologie algébrique, ou réciproquement à apporter des outils topologiques pour résoudre des problèmes d'origine informatique, nous renvoyons à [11] pour une présentation détaillée.
  • descriptions combinatoires
  • homéomorphisme
  • recherche algorithmique dans la direction de la classification des homéomorphismes
  • isotopie
  • graphes
  • graphe
  • courbes
  • courbe
  • complexité
  • surfaces
  • surface
  • théorie
  • théories

Sujets

Informations

Publié par
Nombre de visites sur la page 127
Langue Français
Signaler un problème

Déformation de graphes sur les surfaces
Arnaud de Mesmay
Sous la direction d’Éric Colin de Verdière
Laboratoire d’Informatique de l’École Normale Supérieure
Août 2011
Le contexte général
Mon stage s’inscrit dans le domaine de la topologie algorithmique. Cette discipline encore
très jeune vise à formaliser et à résoudre des versions algorithmiques de problèmes issus de la
topologie algébrique, ou réciproquement à apporter des outils topologiques pour résoudre des
problèmes d’origine informatique, nous renvoyons à [11] pour une présentation détaillée.
Le sujet de ce rapport est l’étude des courbes et des graphes sur les surfaces. Durant les
dix dernières années, des avancées significatives ont été faites, et des algorithmes efficaces ont
été développés pour résoudre des problèmes naturels. Par exemple, on sait calculer des courbes
constituant une décomposition topologique de la surface [23,29], décider si deux courbes qui
y sont plongées sont homotopes [10] ou bien raccourcir autant que possible une courbe en la
déformant continûment sur une surface [6].
Ces problèmes sont également reliés à de nombreuses branches des mathématiques et de
l’informatique. Ainsi par exemple, les communautés de géométrie algorithmique s’intéressent
de près aux propriétés topologiques des objets géométriques qu’elles manipulent, l’étude des
graphes plongés sur les surfaces fournit un angle d’attaque différent pour attaquer les problèmes
1combinatoiresdethéoriedesgraphes ,etnaturellementl’étudedestriangulationssurlessurfaces
est essentielle dans les problèmes liés à l’infographie.
Le problème étudié
Durant ce stage, je me suis essentiellement intéressé au problème suivant :
Isotopie de graphes
Entrée : Un graphe G plongé de deux façons différentes sur une surface S.
Question:Lesplongementsdugraphesont-ilsisotopes,i.e.ya-t-ilunedéformationcontinue
de la surface permettant d’aller de l’un vers l’autre?
Deux instances simples de ce problème peuvent servir d’exemples pour l’introduire. La pre-
mière est le cas d’un graphe dessiné de deux façons dans le plan parsemé de nombreux obstacles.
On se demande alors si l’on peut passer d’un graphe à l’autre de façon continue sans traverser
les obstacles. On verra dans ce rapport que même dans ce cas, le problème n’est pas trivial, voir
figure 5.
Un deuxième cas d’application est celui d’une surface triangulée avec un graphe plongé de
deux manières différentes sur cette triangulation. Il ne s’agit alors plus d’éviter ses obstacles
planaires mais plutôt des obstacles topologiques (trous, poignées).
Étonnamment, ce rapport propose à notre connaissance le premier algorithme pour résoudre
le problème, ce qui peut s’expliquer par la jeunesse relative du domaine. De plus, il est lié à
1. Ils interviennent par exemple de façon essentielle dans la preuve du théorème de Robertson-Seymour.
12
la théorie des mapping class groups (cf. infra), sujet possédant une certaine profondeur ma-
thématique, qui n’a presque pas été exploré du point de vue algorithmique. C’est pourtant un
problème naturel qui se place bien dans le contexte plus général de l’étude des graphes sur les
surfaces (voir par exemple [25] pour une introduction au sujet) : tester si deux graphes sont
isotopes permet de tester si deux graphes plongés sont les « mêmes », dans un sens largement
plus fort que le simple isomorphisme combinatoire. L’aspect mathématique du sujet a été en
partie traité par Ladegaillerie [20–22], qui propose dans une série d’articles une caractérisation
topologique et combinatoire de la question, permettant de ramener le test d’isotopie de graphes
au test d’homotopie d’un certain nombre de courbes bien choisies.
La contribution proposée
L’algorithmequenousproposonsdanscerapportreposesurl’observationque,commel’apré-
cédemment montré Ladegaillerie [20], deux conditions naturelles pour que les deux plongements
d’un même graphe sur une surface soient isotopes sont en fait suffisantes. Ceci nous permet,
en utilisant de plus la décomposition en octogones introduite par [7], de fournir un algorithme
efficace pour résoudre le problème posé, en utilisant comme boîte noire un algorithme dû à Dey
et Guha pour tester l’homotopie de deux courbes [10].
La démarche scientifique employée s’articule en plusieurs étapes. D’une part, nous avons
procédé à une lecture critique de l’article de Ladegaillerie [20], que nous avons mise en relief
avec les progrès sur les connaissances et la présentation de la théorie des mapping class groups,
par exemple exposée dans [14]. Ceci nous a permis de simplifier et de moderniser la preuve du
théorème principal, c’est le premier apport de ce travail. Le deuxième a été ensuite de propo-
ser une construction algorithmique des courbes à tester et enfin de s’intéresser aux possibles
améliorations et ouvertures apportées par cette démarche.
Les arguments en faveur de sa validité
Nous présentons dans ce rapport un algorithme qui résout le problème avec une complexité
linéaire donc optimale en genre fixé, et quadratique sinon. La dépendance au genre est courante
et tolérée dans ce genre de problèmes, voir par exemple [4]. Néanmoins, nous ne disposons pas de
borne inférieure prouvant que cette dépendance au genre est nécessaire. La technique employée
pour justifier la correction et la complexité de l’algorithme est assez robuste, nous montrons
ainsi en section 6.1 comment généraliser celui-ci à un problème plus large que celui considéré.
Enfin, l’algorithme est implantable en pratique : Il ne requiert aucune structure de données de
grande complexité et les constantes intervenant dans la notation O() sont très raisonnables.
Le bilan et les perspectives
L’approcheutiliséedanscerapportnoussembleêtreassezgénérale:d’unepartnouslerelions
à des problèmes mathématiques bien compris (la classification des éléments du mapping class
group), d’autre part nous apportons des outils algorithmiques pour s’atteler à ces problèmes.
Plusieurs ouvertures sur le sujet sont possibles, nous en discuterons plus en profondeur en
conclusion. L’algorithme présenté dans ce rapport a une complexité presque optimale : seule la
dépendance en le genre de la surface induit un facteur non linéaire, une amélioration naturelle de
l’algorithme serait de le faire disparaître. Dans le cas des graphes planaires, on peut se demander
si les mêmes techniques peuvent nous permettre d’obtenir des isotopies rectilignes. Ce problème
est brièvement discuté en section 6.2. On peut également se demander comment traiter le cas
non orientable. La question semble particulièrement épineuse, puisqu’elle est reliée à la théorie
des mapping class groups des surfaces non orientables, qui est extrêmement délicate.
A. de Mesmay 2 Rapport de stage MPRI1. Définitions 3
Organisation du rapport
Ce rapport s’organise de la façon suivante. Dans la première partie, nous introduisons les
définitions et les concepts nécessaires. La seconde partie est une présentation générale de l’algo-
rithme, dont les détails et la preuve de correction sont réparties sur les deux parties suivantes.
L’algorithme final est présenté dans la cinquième partie, la sixième discute les généralisations
possibles et les ouvertures liées à ce travail et la septième conclut.
1 Définitions
1.1 Topologie et courbes sur les surfaces
Commençons par définir précisément les notions utilisées dans la suite de ce rapport. De
bonnes références pour approfondir les concepts de topologie algébrique sont [26] et [16].
Une surface S ou 2-variété à bord est un espace topologique séparé tel que le voisinage
de chaque point soit homéomorphe à un plan ou un demi-plan. L’ensemble des points homéo-
morphes au demi-plan constitue le bord de la surface. Une surface est orientable si et seulement
si elle ne contient pas de ruban de Möbius. Dans tout ce qui suit, les surfaces que l’on consi-
dère sont compactes et orientables, sauf si spécifié autrement. La classification des surfaces à
homéomorphisme près, souvent attribuée à Möbius, fait l’objet du théorème suivant :
[1.A] Théorème (Classification des surfaces orientables)
Toute surface compacte orientable est caractérisée à homéomorphisme près par
deux entiers positifs g (le genre) et b (le nombre de bords). Une surface de type
(g;b) est alors homéomorphe à une sphère à laquelle on a attaché g poignées et
retiré b disques ouverts.
On a coutume de nommer ainsi les surfaces simples : la surface (0; 0) est unesphère, la surface
(1; 0) un tore, la surface (0; 1) un disque, la surface (0; 2) est un cylindre ou anneau, et la surface
(0; 3) est un pantalon.
L’objet de ce rapport est l’étude des graphes sur les surfaces, pour décrire ceux-ci on com-
mence par distinguer les différents types de courbes que l’on peut y tracer. Il y a d’abord les
chemins, il s’agit d’une application continue c : [0; 1]! S; ses extrémités sont c(0) et c(1).
Un lacet est un chemin dont les deux extrémités sont confondues, elles constituent son point
1base. Un cycle est une application continue du cercleS sur la surface, et un arc est un chemin
intersectant le bord de la surface exactement à ses extrémités. Une courbe est simple si elle ne
présente pas d’auto-intersection (à part, pour un lacet, en son point base).
La notion d’homotopie correspond à l’idée intuitive de déformation : deux courbes sont
homotopes si l’on peut déformer continûment l’une en l’autre. Plus formellement, deux chemins
0c et c sont homotopes s’il existe une application continue h : [0; 1] [0; 1] ! S telle que
0h(0;t) = c(t), h(1;t) = c (t), et h(; 0) et h(; 1) sont des applications constantes. Deux cycles
0 1 et sont librement homotopes s’il existe une application continue h : [0; 1]S telle que
0h(0;t) = (t) et h(1;t) = (t) pour tout t. Par la suite, lorsqu’il n’y aura pas d’ambiguïté,
on fera l’ellipse du « librement », tout en remarquant que deux lacets, vus comme des cycles,
peuvent être librement homotopes sans être homotopes, voir figure 1. Un lacet ou un cycle est
dit contractile s’il este à un lacet ou un cycle constant, un arc est dit contractile s’il est
homotope à un chemin sur un bord. Enfin un cycle simple est séparateur s’il sépare la surfaceS
en deux composantes connexes.
A. de Mesmay 3 Rapport de stage MPRI1. Définitions 4
Figure 1 – La courbe en traits pleins et la courbe en pointillés sont homotopes sans être
homotopes librement.
On dit que deux courbes sont en position minimale si leur nombre de
points d’intersection est minimal dans leurs classes d’homotopie. On dit que
deux courbes simples fermées et sur une surfaceS forment un bigone s’il
existe un disque plongé dans S (le « bigone », voir figure ci-contre) dont le
bord est l’union d’un sous-arc de et d’un sous-arc de qui s’intersectent
seulement en leurs extrémités. La proposition suivante fournit un critère
Figure2–Unbi-essentiel pour déterminer si deux courbes sont en position minimale. Nous
gonerenvoyons à [14, Proposition 1.7] pour la preuve.
[1.B] Proposition (Critère du bigone)
Deux courbes simples transverses fermées sur une surface S sont en position
minimale si et seulement elles ne forment pas de bigone.
Le concept de voisinage tubulaire d’un graphe ou d’une sous-surface correspond à l’idée intui-
tivequel’ons’enfait:ils’agitdegrossirunpeuchaquearêteouchaquebord,toutenmaintenant
la même structure topologique. Pour définir cette notion convenablement, on introduit d’abord
la définition suivante. Si X est un surface et Y un sous-ensemble de X et qu’il existe une ap-
plication continue F : [0; 1]X! X telle que pour tout x2 X F (0;x) = x, F (1;x)2 Y et
pour tout y2 Y, t2 [0; 1], F (t;y) = y, on dit que X se rétracte par déformation forte sur Y.
Cette notion permet de définir le voisinage tubulaire d’une sous-surface ou d’un graphe sur une
surface : le voisinage tubulaire deY X oùX est une surface est une sous-surface deX qui se
rétracte par déformation forte sur Y.
1.2 Graphes sur les surfaces et descriptions combinatoires
Une surface étant par essence un objet continu et infini, il convient de la discrétiser convena-
blement pour pouvoir la manipuler algorithmiquement. Deux modèles sont couramment utilisés
pour arriver à cette fin.
Une surface combinatoire est la donnée d’une surface S et d’un graphe non dirigé G plongé
sur cette surface, c’est-à-dire envoyé injectivement dans son intérieur tel que chaque face soit
un disque, et tel que le bord de S soit inclus dans des arêtes de G. En pratique, le plongement
spécifie les informations suivantes : quel sommet est envoyé sur quel point de S, et quelle demi-
2arête est envoyée sur quelle « demi-courbe »incidente à l’image du sommet extrémité dans S .
Dans ce modèle, les courbes sur la surfaceS sont des marches surG, c’est-à-dire la donnée d’une
suite alternante de sommets et d’arêtes, commençant et finissant par une arête, telle que deux
éléments consécutifs de la suite sont incidents. Une telle marche est fermée si le premier et le
dernier sommet sont identiques. La complexité d’une courbe est le nombre d’arêtes empruntées,
2. Préciser seulement quelle arête est envoyée sur quelle courbe est source d’ambiguïtés, par exemple dans le
cas du graphe à un unique sommet et un boucle plongé sur un cylindre : si l’on donne une orientation à la boucle,
le plongement ne spécifie pas comment transporter cette orientation sur le graphe plongé
A. de Mesmay 4 Rapport de stage MPRI1. Définitions 5
comptéesavecmultiplicité.Lacomplexité delasurfaceS estalorslenombredesommets,d’arêtes
et de faces du graphe G.
Si cette première formulation semble assez naturelle (elle se rapproche fortement de la tri-
angulation d’une surface utilisée couramment en infographie), on lui préfèrera souvent dans ce
rapport un modèle dual que nous présentons maintenant. Une surface à métrique de croisements
est la donnée d’une surfaceS et d’un graphe non dirigéG tel que chaque face de ce graphe soit
un disque et le bord deS soit inclus dans les arêtes deG . Dans ce modèle, au lieu de considérer
des chemins sur les arêtes du graphe, on considère des chemins qui lui sont transverses, c’est-à-
dire qu’ils intersectent le graphe uniquement de façon à le traverser, et ceci loin de ses sommets.
La complexité d’un chemin est le nombre d’arêtes croisées. Comme précédemment, la complexité
de la surface est la somme du nombre de sommets, d’arêtes et de faces du grapheG. Un exemple
classique de surface à métrique de croisements est une surface munie d’une triangulation, comme
cela est couramment utilisé en infographie. La description d’un graphe sur cette surface est alors
naturellement l’arrangement de ce graphe par rapport au graphe sous-jacent que constitue la
triangulation. La notion générale de surface à métrique de croisements n’est ainsi qu’une légère
abstraction de ce modèle naturel, où l’on autorise les faces à avoir un degré supérieur à 3.
On peut aisément jongler entre les deux modèles pour décrire les sur-
faces:Si (S;G)correspondàunesurfacecombinatoire,onpeutenconstruire
une surface à métrique de croisements en introduisant son graphe dual H
ainsi : chaque face deG correspond à un sommet deH, et à chaque arête de
3G on associe une arête de H, reliant les deux faces qui lui sont incidentes .
La figure ci-contre représente les deux modèles : le graphe primal (solide)
et dual (en pointillé) sur un anneau combinatoire. Ces graphes sont fixés
avec la surface, et on représentera les diverses courbes par leurs positions
par rapport à eux. On peut alors transcrire la représentation d’une courbe
sur la surface combinatoire en une courbe sur la surface à métrique des croisements : si elle suit
les arêtese :::e dansG, elle croisera les arêtes dualese :::e dansH, et cette transformation1 p 1 p
préserve les classes d’homotopie des courbes.
4On s’intéresse maintenant à comment décrire un graphe plongé sur une surface à métrique
de croisements. On peut représenter un ensemble de courbes (potentiellement non simples) sur
une telle surface en conservant l’arrangement de ces courbes avec le grapheH, c’est-à-dire qu’on
plonge chaque courbe une par une de façon régulière, et chaque croisement de la nouvelle courbe
avec l’arrangement, ainsi que chaque auto-intersection de cette courbe, donne lieu à un sommet
de degré 4. On en vient ainsi à séparer des arêtes en deux sous-arêtes. Ainsi, la description
combinatoire d’un grapheG sur une surface (S;H) est l’arrangement deG en surimposition sur
le graphe sous-jacent H. Le fait que H soit plongé cellulairement, c’est-à-dire que chacune de
ses faces soit un disque, garantit que toute courbe peut être décrite à homotopie près sans
ambiguïté dans ce modèle, et donc tout graphe également. La complexité de G est la somme
des complexités des chemins qui le constituent. Dans ce qui suit, on utilisera souvent par abus
de langage le même vocable graphe pour désigner indifféremment un graphe abstrait, représenté
par exemple par une matrice d’adjacence, et un graphe plongé sur une surface, c’est-à-dire
l’arrangement de courbes sur une métrique de croisements.
Sans rentrer dans les détails, notons qu’il existe des structures algorithmiques bien adaptées à
la combinatoire des graphes planaires ou plongés sur des surfaces [18] [13], permettant de réaliser
3. Il convient de faire un peu plus attention dans le cas des surfaces à bord : on ajoute alors un sommet pour
chaque arête sur le bord deG et on relie ce sommet aux autres arêtes sur le bord auquel il est relié dans G, ainsi
qu’à la face qui lui est incidente.
4. On ne traitera que le cas des graphes plongés dans ce rapport, qui ne présentent donc pas d’intersection
avec le bord de la surface. Une généralisation succincte au cas des graphes plongés sur le bord est présentée à la
fin.
A. de Mesmay 5 Rapport de stage MPRI1. Définitions 6
toutes les opérations « naturelles »en temps constant (trouver les faces adjacentes d’une arête,
les arêtes adjacentes à un sommet, etc.). La libraire de référence en géométrie algorithmique
5CGAL implémente l’une d’entre elles .
La caractéristique d’Euler (G) d’un graphe plongé cellulairement sur une surface est la
grandeurv e +f oùv est le nombre de sommets,e le nombre d’arêtes etf le nombre de faces.
La formule d’Euler (voir par exemple [26]) stipule que (G) = 2 2g b oùg est le genre de la
surface sur laquelle est plongée le graphe et b le nombre de composantes connexes du bord.
La notion d’isotopie ambiante correspond à une déformation continue de toute la surface, et
est ainsi l’analogue global de l’homotopie : une isotopie de la surface est une application continue
h : [0; 1]S! S telle que pour chaque t, h(t;) est un homéomorphisme. Pour A S, une
isotopie relative àA est une isotopieh telle que pour toutt;h(t;) vaut l’identité. Deux cyclesjA
0 6 0et sont dites isotopes si il existe une isotopieh telle queh(; 0) soit l’identité eth(; 1)) = .
Intuitivement, alors que l’homotopie entre deux courbes autorise celles-ci à s’auto-intersecter
0dans l’intérieur deS pendant la déformation, l’isotopie l’interdit. Deux graphes G etG sont de
la même façon isotopes s’il existe une isotopie h telle que h(; 0) soit l’identité et h(; 1) envoie
0G sur G . Enfin, deux homéomorphismes sont isotopes s’il existe une isotopie entre les deux.
Le théorème suivant stipule que les notions d’homotopie et d’istopie coïncident dans le cas
des courbes fermées simples :
[1.C] Théorème (Baer [1])
Deux courbes simples fermées non contractiles sur une surface sont homotopes si
et seulement si elles sont isotopes.
1.3 Isotopie d’homéomorphismes et mapping class group
Cette partie pourra être sautée en première lecture, elle présente des résultats qui ne sont
pas directement utilisés dans ce rapport mais fournit un point de vue éclairant sur l’heuristique
de l’algorithme et de la preuve de sa correction.
Le problème que nous considérons est relié à la théorie plus générale des homéomorphismes
de surface. Deux plongements d’un même graphe fournissent naturellement un homéomorphisme
du voisinage tubulaire de l’un vers le voisinage tubulaire de l’autre, qui peut s’étendre à toute
la surface (ceci sera détaillé plus loin). Le problème est alors réduit à caractériser la classe
d’isotopiedel’homéomorphismeobtenu,etonvientdoncàétudierlegroupedesclassesd’isotopie
d’homéomorphismes d’une surface, communément appelé Mapping Class Group ou groupe de
Teichmüller, nous renvoyons le lecteur intéressé à [14] pour une introduction plus approfondie à
ce sujet. C’est un invariant topologique abondamment étudié, dont les propriétés et les vertus
en terme d’études de surfaces sont assez bien comprises.
Un des résultats essentiels de cette théorie dû à Thurston [15] permet de classifier un élément
dumappingclassgroupentroisclassesauxpropriétésbiendistinctes.Larecherchealgorithmique
dansladirectiondelaclassificationdeshoméomorphismes,quiestdoncunproblèmeplusgénéral
que le nôtre, a été légèrement plus défrichée et consitute l’objet de plusieurs articles [3,27]; mais
le point de vue présenté y est essentiellement mathématique et les complexités impratiquables,
desortequenotrealgorithmeestàlafoisplussimpleetplusrapidequeceuxquiysontprésentés,
mais est évidemment moins général.
5. http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/HalfedgeDF/Chapter_main.html
6. La notion d’isotopie couramment utilisée dans la littérature est différente mais peut s’étendre à celle-ci,
voir [14, Proposition 1.11]
A. de Mesmay 6 Rapport de stage MPRI6
1. Définitions 7
On peut voir le mapping class group comme un groupe discret traduisant les symétries de la
surface. Il est défini comme étant le groupe de classes d’isotopies d’homéomorphismes orientés
de S (valant l’identité sur @S si @S =;), on le notera MCG(S).
Ildécritainsilesdifférentesfaçonsqu’unesurfaceades’envoyersurelle-même,àisotopieprès
(ce qui correspond à l’idée que deux homéomorphismes isotopes sont les mêmes). Par exemple,
2le disqueD est une surface très contrainte, et le lemme suivant stipule qu’il n’y a qu’une classe
d’homéomorphismes sur le disque :
[1.D] Théorème (Lemme d’Alexander)
2Le groupe MCG(D ) est trivial, en d’autres termes tout homéomorphisme valant
l’identité sur le bord d’un disque est isotope à l’identité.
Preuve de [1.D].
2 2Soit :D !D un homéomorphisme égal à l’identité sur le bord. On définit :

x(1 t) ( ) 0jxj 1 t
1 tF (x;t) =
x 1 tjxj 1
2pour 0t< 1, et on définit F (x; 1) comme étant l’identité surD . Cela fournit une isotopie F
de vers l’identité.
Un premier exemple de surface ayant un mapping class group non trivial (et le seul dont
nous aurons besoin dans ce rapport) est l’anneau A, ou cylindre, on renvoie à [14] proposition
2.4 pour la preuve.
[1.E] Proposition (Mapping class group du cyclindre)
MCG(A) =Z
Un générateur du groupeMCG(A) est illustré par la figure 3, on appelle
un tel homéomorphisme un twist de Dehn, ou simplement twist autour du
1bord. Dans le cas d’une paramétrisation du cylindre par A = S [0; 1],
l’homéomorphisme a une expression très simple : il s’agit juste deT :A!A
défini par T (;t) = ( + 2t;t). De la même façon, on peut définir un
twist autour d’un cycle simple sur une surfaceS quelconque : le voisinage
tubulaire de est un cylindre, et il suffit donc de définir l’homéomorphisme
Figure 3 – Twistcomme valant un twist sur ce cylindre et l’identité sur le reste de la surface,
sur un cylindrevoir la figure 4.
Figure 4 – Twist de la courbe en pointillés autour de la courbe en traits pleins.
L’étude des twists de Dehn est fondamentale dans l’étude du mapping
A. de Mesmay 7 Rapport de stage MPRI2. Présentation de l’algorithme 8
class group d’une surface, et représente l’objet de nombreux travaux (il n’est déjà pas évident
de montrer qu’un twist correspond à un élément du mapping class group non trivial), nous
renvoyons le lecteur à [14][chapitre 3] pour des propriétés et des preuves détaillées. Le résultat
7qui nous intéresse est le suivant :
[1.F] Théorème (Générateurs du mapping class group, théorème de Dehn-Lickorish
[9,24])
Pour toute surface S, le groupe MCG(S) est engendré par un nombre fini de
twists de Dehn autour de courbe simples non séparatrices.
Les premières preuves de ce théorème montrent qu’il suffit pour une surface de genre g
d’utiliser 3g 1 courbes pour générer le mapping class group, mais une amélioration subséquente
due à Humphries [17] montre que l’on peut même se contenter de 2g 1 cycles. La famille de
cycles utilisée ultérieurement pour décomposer une surfaces en octogones aura également la
propriété qu’elle génère le mapping class group (ce qui n’est pas un hasard!).
L’intérêt de ce théorème est qu’il permet d’avoir une vision assez intuitive du mapping class
group d’une surface : c’est le groupe qu’on obtient en composant les twists autour de certaines
courbes de cette surface. En particulier, si l’on réussit d’une certaine manière à montrer qu’un
homéomorphisme h n’est pas composé de twists autour de ces courbes, on peut en déduire
immédiatement que cet homéomorphisme h est isotope à l’identité. C’est l’idée qui sous-tend la
preuve du test d’isotopie que nous présentons par la suite.
2 Présentation de l’algorithme
2.1 Présentation du problème
Les définitions étant posées, le problème algorithmique auquel nous nous intéressons dans ce
rapport de stage est le suivant :
Entrée : Un graphe G, une surface S orientable décrite par un graphe de métrique de
croisements H, et deux plongements G et G du graphe G sur (S;H).1 2
Question : Lests G et G sont-ils isotopes?1 2
Nous n’imposons pas de conditions particulières sur le graphe G, on le supposera juste non
vide,enautorisantlesbouclesetlesarêtesmultiples.Danstoutelasuite,lesnotationsintroduites
en entrée seront maintenues, la complexité de la surface S sera notéem, celles des plongements
G et G seront notées k et k (rappelons qu’il s’agit de la complexité de G plus le nombre de1 2 1 2
8croisements de G avec H), on notera g le genre d’un voisinage tubulaire de G et G dansi 1 2
0S, et enfin g le genre de S. On peut supposer S connexe puisqu’il suffit de tester le problème
séparément sur toutes ses composantes connexes sinon. Rappelons qu’une des définitions du
genre d’une surface est le nombre maximal de cycles simples sans points communs pouvant être
tracés à l’intérieur de cette surface sans la déconnecter. Une telle famille de cycles dans un
voisinage tubulaire de G fournissant immédiatement une famille non séparatrice de S, on a1
0gg .
Remarquons tout d’abord que l’approche naïve consistant à tester l’homotopie de tous les
cyclesconstituantdesfacesdugraphenemarchepas,commeonpeutlevoirsurlecontre-exemple
exposé en figure 5.
7. Stricto sensu on ne l’utilise pas par la suite mais il fournit une clé importante de compréhension des
différents raisonnements utilisés.
8. Comme on le verra juste après, on peut supposer que ce sont les mêmes sinon la réponse à la question est
trivialement non.
A. de Mesmay 8 Rapport de stage MPRI