Le petit village de Saint-Santin est l’une de ces anomalies qui régale les amateurs d’insolites. La frontière entre le Cantal et l’Aveyron le traverse en plein cœur, si bien qu’il s’agit administrativement de deux communes distinctes mais juxtaposées : d’un côté Saint-Santin en Aveyron, de l’autre Saint-Santin-de-Maurs dans le Cantal. La ligne de démarcation découpe la place du village (des villages ?) en son milieu, ce qui donne lieu à une illustration frappante de cette scission. De part et d’autre de cette place, le village comporte deux églises, deux mairies, et le monument aux morts, sis exactement sur la ligne, dispose de deux faces pour les nécrologies respectives.

Au-delà du casse-tête quotidien que cette situation cause [1], nous nous intéresserons plutôt dans cet article à une difficulté cartographique. Pour expliquer au mieux la géographie du village, une bonne carte se doit de retranscrire précisément la position de la frontière, sinon le lecteur circonspect ne comprendrait pas la duplication systématique de toutes les administrations. Comparons à ce sujet la précision de deux cartes couramment utilisées :

À gauche, l’IGN place correctement la frontière Cantal-Aveyron (en orange) en travers de la place du village. À droite, Google maps manque la cible : sa frontière en traits blancs pointillés coupe le village un peu trop au sud et place donc les deux églises dans la même commune.

Cela permet d’identifier une difficulté pratique : lorsque l’on dessine une carte, il est nécessaire pour la lisibilité de simplifier des tracés trop sinueux en des lignes plus droites. Un système cartographique doit également, en fonction de l’échelle choisie, afficher ces lignes avec un niveau de détail plus ou moins grand. Il convient cependant de ne pas faire de simplifications abusives, qui peuvent résulter en des erreurs comme dans le cas ci-dessus. Comment s’apercevoir qu’un tracé a été trop simplifié ? Et comment peut-on faire ce test de façon informatique, de telle sorte qu’il puisse (éventuellement) être incorporé dans des logiciels cartographiques ?

Un peu d’abstraction

Comment modéliser un tel problème en termes mathématiques ? Commençons par mettre le sujet de la carte, par exemple la France, dans un rectangle. Chaque point de ce rectangle peut alors être représenté par ses coordonnées, et on peut ainsi noter les coordonnées de tous les points d’intérêt de la zone à cartographier (par exemple les églises, mairies, etc.). La frontière que l’on veut tracer, par exemple ici celle du Cantal, est une succession de segments qui part d’un point et y revient : on appellera cela une courbe fermée. Là encore, on peut noter toutes les coordonnées des extrémités des segments pour stocker informatiquement cette frontière.

Maintenant, rappelons-nous que l’on veut décider si une frontière n’a pas été trop simplifiée. Le problème est donc le suivant : on dispose d’une carte, de points d’intérêt repérés par leurs coordonnées, et du tracé de deux courbes fermées (une originale et une simplifiée), et l’on veut certifier que les deux courbes passent du même côté de chaque point. Pour le rendre plus rigoureux, nous allons modéliser ce critère par une notion de déformation, en considérant que les points d’intérêt sont des obstacles : Demandons-nous si l’on peut « déformer » une courbe fermée en l’autre sans franchir aucun point d’intérêt. Assurément, si la réponse est oui, les deux courbes sépareront identiquement les points d’intérêt, et si c’est non, il y aura eu une erreur en passant d’une courbe à l’autre.

Déformations de courbes fermées

Nous avons donc identifié dans notre problème de tracé de cartes le problème mathématique suivant :

Déformation n’est pas un concept très rigoureux, et le bon terme mathématique est celui d’homotopie. Une homotopie entre deux courbes fermées est une famille continue de courbes fermées passant de l’une en l’autre, ne traversant aucun point d’intérêt. Nous mettons une définition précise de ce concept dans le bloc dépliable ci-après, mais celle-ci n’est pas indispensable : l’idée intuitive ainsi que l’animation ci-dessus suffisent à comprendre de quoi l’on parle.

Comment encoder efficacement la trajectoire d’une courbe fermée ? Numérotons les points d’intérêt de $1$ à $n$. Supposons pour simplifier que les ordonnées de tous les points d’intérêt soient différentes, et associons à chaque point d’intérêt une demi-droite horizontale issue de celui-ci et allant vers la droite. Les demi-droites sont donc naturellement numérotées entre $1$ et $n$. Le mot des croisements d’une courbe fermée est obtenue en marchant le long de cette courbe jusqu’à revenir à son point de départ, et en écrivant le numéro de chaque demi-droite croisée lors de notre parcours, en mettant une barre au-dessus de l’indice si la demi-droite est franchie de haut en bas, et pas de barre sinon. Par exemple, le mot des croisements de la courbe ci-contre (en partant du point $D$) est $3\bar{3}\bar{4}\bar{5}\bar{6}6$.

Si ce mot des croisements contient un motif constitué de deux symboles consécutifs de la forme $a\bar{a}$ ou $\bar{a}a$, il est clair que nous pouvons déformer la courbe fermée pour supprimer ces deux symboles dans le mot des croisements. C’est illustré dans la figure suivante, où le motif $1\bar{1}$ est supprimé.

Nous obtenons ainsi une condition suffisante pour que deux courbes fermées soient homotopes : il suffit que les mots des croisements correspondants soient équivalents, au sens où l’on peut passer de l’un à l’autre par une succession d’insertions ou de suppressions de motifs comme ci-dessus. (Les courbes étant fermées, les mots des croisements doivent être considérés à permutation cyclique près ; par exemple, l’on peut aussi simplifier $12\bar{3}\bar{1}$ en $2\bar{3}$.) On peut en fait se convaincre que cette condition est aussi nécessaire : intuitivement, en déplaçant continûment la courbe fermée, on ne peut pas modifier le mot des croisements autrement qu’en insérant ou supprimant des motifs.

Étant donné un mot des croisements, il y a un choix naturel de mot équivalent : c’est celui que l’on obtient en supprimant itérativement autant que possible des motifs. Ainsi, pour déterminer si deux courbes fermées sont homotopes, il suffit de calculer leur mot des croisements, de supprimer autant que possible les motifs dans ces mots, et de comparer (à permutation cyclique près) les deux mots obtenus.

Dans la figure ci-contre, le mot des croisements est $1\bar{1}31\bar{1}\bar{3}\bar{4}\bar{5}\bar{6}6$. En supprimant itérativement tous les motifs, on obtient $\bar{4}\bar{5}$, de même que dans la figure ci-dessus. Les deux courbes sont donc homotopes, comme l’avait illustré l’animation un peu plus haut.

Concluons cette section un peu technique par une note historique. Nous y sommes arrivés par un problème cartographique, mais le problème d’homotopie de courbes que nous avons considéré ici a des racines bien plus vieilles qu’on pourrait le croire : on le retrouve en effet parmi les problèmes de Dehn, trois questions formulées par Max Dehn en 1911 qui ont fortement contribué à façonner la théorie des groupes et la topologie. En fait, Dehn s’est intéressé à ces questions algorithmiques d’homotopie de courbes non seulement dans le cas du plan, mais aussi dans le cas de surfaces plus générales comme le tore (la surface d’une bouée) ; les problèmes étudiés dans cet article se posent (et se résolvent !) aussi pour ces surfaces.

Déformations de graphes

Nous savons maintenant déterminer si la déformation d’une frontière (courbe fermée) a respecté les points d’intérêt. Mais les objets que l’on manipule en cartographie sont généralement plus compliqués : en effet, il serait plus intéressant de pouvoir étudier le même problème avec les frontières de tous les départements français simultanément. L’objet mathématique qui correspond n’est alors plus une courbe fermée mais un graphe. Cet objet central des mathématiques discrètes a déjà été présenté plusieurs fois dans d’autres contextes sur Images des Mathématiques, par exemple ici, ici ou ici, rappelons-en tout de même la définition élémentaire.

Un graphe est constitué de sommets et d’arêtes, chaque arête reliant deux sommets. Nous ne considérerons ici que des graphes dessinés sans croisements dans le plan [2]. Pour une carte, l’idée est qu’un sommet représente l’intersection entre plusieurs frontières (le point de rencontre du Cantal, de l’Aveyron et du Lot par exemple), et les arêtes séparent deux départements en reliant ces points. Chaque sommet peut être représenté à l’aide de ses coordonnées ; chaque arête n’est pas nécessairement rectiligne, mais on peut choisir de la représenter par une succession de segments, déterminés par les coordonnées de leurs extrémités. Nous arrivons alors au second problème, qui nous occupera jusqu’à la fin de l’article.

À nouveau, le concept de « déformation » peut être défini plus précisément par le concept d’isotopie : une isotopie entre deux graphes est une famille continue de graphes permettant de passer de l’un à l’autre sans traverser aucun point d’intérêt. Une définition plus formelle est cachée ci-dessous.

Une approche naïve

Profitons de ce problème pour illustrer comment s’attaquer à une question mathématique. Pour arriver à la solution, on commence nécessairement par une phase de tâtonnement, où il s’agit juste dans un premier temps de dire quelque chose sur le problème que l’on étudie. Ces balbutiements permettent ensuite d’aboutir à une certaine compréhension du problème, que l’on peut mettre en œuvre pour en déduire une solution générale. Ici, un peu de réflexion nous amène rapidement à dire deux quelque chose.

D’abord, le fait qu’un graphe puisse se déformer en l’autre implique nécessairement que ceux-ci ont de nombreux points communs. Par exemple, si l’on se place au point qui est à l’intersection du Cantal, de l’Aveyron et du Lot et que l’on tourne sur soi-même dans le sens des aiguilles d’une montre, ces trois départements apparaissent dans cet ordre. Il doit en être aussi le cas dans toute carte obtenue par déformation de la première. On dit que l’ordre circulaire autour des sommets est respecté par une isotopie. Dans le même ordre d’idées, si deux graphes sont isotopes, alors chacun de leurs départements contient exactement les mêmes points d’intérêt. Du coup, un premier test, rudimentaire, d’isotopie de graphes serait de se contenter de vérifier que les ordres circulaires sont maintenus, et que les départements contiennent les mêmes points d’intérêt de chaque côté. On dit alors que les deux graphes ont les mêmes cartes combinatoires. La figure suivante montre deux graphes avec des cartes combinatoires différentes : le triangle du haut ne contient pas les mêmes points d’intérêt dans les deux dessins (et certains ordres circulaires sont chamboulés). On peut donc immédiatement en déduire que ces deux graphes ne sont pas isotopes !

Ajoutons à cela une deuxième idée. Un des adages essentiels en mathématiques [3] est que pour résoudre un problème, il s’agit toujours de le ramener au problème précédent, et l’on peut essayer de l’appliquer ici. Nous avons vu comment décider si deux courbes fermées pouvaient être déformées l’une en l’autre ; il est tentant de réutiliser ce procédé pour les graphes. Mais quelles courbes tester ? Les frontières individuelles de chaque département fournissent un bon point de départ. En effet, si l’on peut déformer toute une carte des départements en une autre, on peut bien déformer la frontière du Cantal de la première carte en la frontière du Cantal de la seconde.

Nous avons donc identifié deux conditions nécessaires pour que deux graphes soient isotopes :

• (C1) Les cartes combinatoires sont les mêmes, c’est-à-dire que les ordres circulaires autour de chaque sommet et les points d’intérêt dans chaque département doivent être les mêmes dans chaque graphe.
• (C2) Chaque frontière d’un département dans un graphe doit être homotope à la frontière du même département dans l’autre graphe.

Nous aimerions que ces deux conditions soient également suffisantes, ce qui nous réduirait le problème 2 à tester ces deux conditions. La deuxième, nous savons déjà la résoudre, et le premier test est assez élémentaire d’un point de vue informatique.

Hélas, l’exemple suivant nous montre que ce n’est pas le cas, et qu’il existe des graphes vérifiant les deux conditions mais n’étant pas isotopes. En effet, le lecteur peut vérifier que les cartes combinatoires sont les mêmes, et que tous les départements sont homotopes — pour aider, nous avons colorié les frontières de chaque département d’une couleur différente sur chaque carte. Mais il aura bien du mal à déplacer un graphe dans l’autre puisqu’une telle déformation n’existe pas. (C’est évident à vue de nez, mais le montrer requiert un peu d’astuce — en fait, une solution est donnée à la fin de cet article.) [4]

Une caractérisation de l’isotopie de graphes

Nous avons identifié un sérieux obstacle à notre approche. Cependant, la solution n’est pas loin, et pour nous guider, nous allons nous intéresser au théorème suivant, découvert par Yves Ladegaillerie en 1984 [5] :

La première condition de ce graphe a déjà été rencontrée, et la deuxième ressemble un peu à celle que nous avions proposée, mais, au lieu de considérer seulement les frontières, il s’agit maintenant de considérer tous les cycles, c’est-à-dire tous les chemins fermés dans le graphe (possiblement avec répétitions de sommets ou d’arêtes). Il est donc clair que les conditions (C’1) et (C’2) sont nécessaires pour que les graphes soient isotopes, et le théorème dit essentiellement que ces conditions sont suffisantes.

Comme mentionné plus haut, nous savons tester chacune de ces deux conditions, mais le problème est que le théorème ci-dessus requiert de tester l’homotopie entre tous les cycles du graphe, et il y en a (en général) une infinité ! Partant de ce constat, il serait naturel de fouiller dans la démonstration de Ladegaillerie pour en extraire une famille finie, et effectivement on en trouverait une, mais celle-ci se révèle être assez compliquée. Nous proposons ci-dessous une approche alternative, qui s’avère plus efficace informatiquement.

Squelette

Dans la tentative précédente, nous avions créé une courbe fermée par frontière de département, et voulions tester si la courbe entourant un département dans le premier dessin de graphe était homotope à la courbe entourant le même département dans le second dessin. Cela ne fonctionne pas ; en d’autres termes, dans la condition (C’2) du théorème de Ladegaillerie, il ne suffit pas de tester les cycles qui sont des frontières. Est-ce qu’une autre construction ne pourrait cependant pas fonctionner ?

Reprenons les courbes des frontières du graphe $G$, comme dans la première tentative, et ajoutons également la frontière extérieure, qui fait tout le tour du graphe. Pinçons certaines paires de courbes longeant une même arête de $G$ à des endroits bien choisis (nous ne détaillerons pas la construction ici). Emmêlons les courbes aux endroits pincés : au lieu que les courbes se touchent sans se croiser réellement à l’endroit des pincements, échangeons les connexions en décrétant qu’elles se croisent. Ce procédé un peu curieux a pour effet de fusionner toutes les courbes en une seule, qui bien sûr s’auto-intersecte, le squelette de $G$ ; dans la figure suivante, on montre comment passer de $G$ (en bleu) à son squelette (en vert). Nous pouvons appliquer la même construction à $G'$, obtenant aussi son squelette.

Pourquoi ces courbes sont-elles intéressantes ? D’abord, tout comme les frontières des départements dans notre première tentative, ces courbes sont peu complexes : chaque arête de $G$ est longée par exactement deux morceaux de courbes de son squelette, et de même pour $G'$. Sans rentrer dans les détails, cela permet d’avoir un algorithme efficace.

Ces courbes ont-elles des chances d’être utiles à notre problème ? En d’autres termes, est-ce que le théorème de Ladegaillerie a des chances de rester vrai si, dans la condition (C’2), on ne teste que l’homotopie des deux squelettes correspondants ? Comme on le voit sur l’illustration, le squelette sépare le graphe $G$ des points d’intérêt et le découpe en zones qui n’ont pas de « trous ». Cela implique que, si la condition (C’1) est satisfaite et s’il existe une isotopie entre le graphe formé par le squelette de G et celui de G′, alors il existera une isotopie entre G et G′ (on peut voir le squelette de $G$ ou de $G'$ comme un graphe ayant pour sommets les points d’auto-intersection et pour arêtes les morceaux de squelette entre deux auto-intersections).

Il semblerait que nous n’ayons pas vraiment avancé. Au lieu de tester l’isotopie entre deux graphes, nous devons maintenant tester l’isotopie entre les graphes formés par les squelettes. Mais l’idée derrière cette construction est que ceux-ci ont une certaine structure, qui nous permet de prouver le résultat suivant : s’il existe une homotopie entre les deux squelettes, alors il existe une isotopie entre les deux graphes formés par les squelettes. Ensuite, comme on sait tester l’homotopie de deux courbes, ce résultat suffira à résoudre notre problème. Néanmoins, ce point, qui pourrait sembler intuitivement évident, repose en fait sur des outils nettement plus complexes de topologie algébrique et de géométrie hyperbolique dont nous ne dirons pas plus ici.

Tout cela nous permet donc de résoudre notre problème : pour tester l’isotopie de deux graphes, il suffit de tester s’ils ont les mêmes cartes combinatoires et si leurs squelettes sont homotopes. Nous laissons en exercice au lecteur le soin de vérifier que les squelettes suivants, correspondants au contre-exemple décrit deux paragraphes plus haut, ne sont en effet pas homotopes, ce qui se fait aisément avec l’algorithme que nous avons décrit en première partie. Solution dans le bloc dépliant !

Solution de l’exercice

Commençons par numéroter les points d’intérêt et tracer les demi-droites (par souci de visibilité,nous avons un peu tout décalé, sans rien changer au problème). En partant du point de départ D, on observe alors les mots de croisement suivants :

• $\bar{1}\bar{2}\bar{3}\bar{4}32\bar{2}\bar{3}\bar{4}\bar{3}\bar{1}\bar{3}32$ pour la première figure, qui se simplifie en $\bar{1}\bar{2}\bar{3}\bar{4}\bar{4}\bar{3}\bar{1}2$.
• Pour la deuxième, il faut s’accrocher un peu plus. On obtient : $\bar{1}\bar{2}\bar{3}532\bar{2}\bar{3}\bar{4}\bar{5}32\bar{2}\bar{3}532\bar{2}\bar{3}\bar{4}\bar{5}\bar{3}\bar{1}\bar{3}32$, qui se simplifie en
  $\bar{1}\bar{2}\bar{3}5\bar{4}\bar{4}\bar{5}\bar{3}\bar{1}2$.

Les deux mots sont différents, donc les courbes ne sont pas homotopes, donc les graphes ne sont pas isotopes : le tour est joué.

Conclusion

Grâce aux techniques présentées ici, le village de Saint-Santin sera peut-être un jour sauvé de l’imprécision cartographique. Mais pour le lecteur qui trouverait cette motivation un peu trop anecdotique, prenons un peu de recul. Le sujet de cet article, c’est avant tout les formes, leurs déformations et les outils pour calculer avec celles-ci ; cette étude en général forme la topologie algorithmique [6]. Le champ d’application de ce domaine est loin de se restreindre à la cartographie, et le monde fourmille de problèmes auxquels ces techniques s’appliquent. Par exemple, notons que déformer des graphes, cela permet de déformer des photos, ce qui est à la base des techniques de morphing, sujet qui a (bien sûr !) déjà été traité dans un autre article d’Images des Mathématiques.