Carte combinatoire

Une carte combinatoire est un objet combinatoire qui intervient dans la modélisation de structures topologiques subdivisées en objets. La version la plus simple en est la carte planaire, structure combinatoire pour la représentation de graphes planaires dans le plan.

Historique[modifier | modifier le code]

Le concept de carte combinatoire a été introduit de manière informelle au début des années 1960 par Jack Edmonds pour la modélisation de surfaces polyédriques^[1]. La première expression formelle des cartes a été donnée par Alain Jacques sous le nom de constellation^[2]^,^[3] mais le concept a déjà été utilisé auparavant de manière intensive, sous le nom de rotation, par Gerhard Ringel^[4] et John William Theodore Youngs dans leur célèbre solution au problème de coloration de cartes de Heawood^[5]. C'est la dénomination carte combinatoire (« combinatorial map » en anglais) qui est utilisée couramment. Le concept a été étendu pour pouvoir représenter des objets subdivisés orientables en dimension supérieure.

Structure générale[modifier | modifier le code]

Les cartes combinatoires sont utilisées en tant que structures de données efficaces pour la représentation et le traitement d'images, et en modélisation géométrique. En infographie, ce modèle est appelé B-Rep puisqu'il représente les objets par leur "bord". Le modèle est lié aux complexes simpliciaux et à la topologie combinatoire. On peut étendre les cartes combinatoires à des cartes dites généralisées qui permettent aussi de représenter des objets non orientables comme le ruban de Möbius ou la bouteille de Klein.

Diverses applications requièrent une structure de données qui permet de représenter les subdivisions d'un objet. Par exemple, un objet en 2 dimensions peut être décomposé en sommets (cellules de dimension 0), arêtes (cellules de dimension 1), et faces (cellules de dimension 2). De plus, il est souvent nécessaire de représenter les relations de voisinage entre ces cellules.

L'objectif est décrire toutes les cellules de la subdivision, et de plus toutes les relations d'incidence et d'adjacence entre ces cellules. Lorsque toutes les cellules représentées sont des simplexes, un complexe simplicial peut être employé, mais dans le cas général on utilise des modèles de topologique cellulaire comme les cartes combinatoires ou les cartes généralisées.

Cartes planaires[modifier | modifier le code]

Les premiers travaux sur les cartes combinatoires^[3]^,^[6] développent une représentation de graphes sur des surfaces qui comprennent en particulier les graphes planaires : Une carte combinatoire de dimension 2 est une structure $(B,\sigma ,\alpha )$ , où

$B$ est un ensemble fini dont les éléments sont appelés les brins
$\sigma$ est une permutation sur $B$ ;
$\alpha$ est une involution sans point fixe sur $B$ .

Intuitivement, une telle carte correspond à un graphe dessiné sur une surface, où chaque arête est subdivisée en deux brins (parfois aussi appelées « demi-arêtes »). La permutation $\sigma$ donne, pour chaque brin, le brin suivant en tournant autour du sommet dans le sens positif ; l'autre permutation $\alpha$ donne, pour chaque brin, le brin opposé de la même arête. Les cycles de la permutation $\alpha$ permettent de retrouver les arêtes, et les cycles de $\sigma$ les sommets du graphe. On définit une troisième permutation $\varphi$ par

\varphi =\sigma \circ \alpha

.

Cette permutation donne, pour chaque brin, le brin suivant sur la même face ; ainsi, les cycles de $\varphi$ s'identifient aux faces de la représentation. Selon les cas, on peut utiliser la représentation $(B,\sigma ,\alpha )$ ou $(B,\varphi ,\alpha )$ qui sont équivalentes puisque $\sigma =\varphi \circ \alpha$ . Les deux représentations sont duales au sens qu'elles échangent sommets et faces.

Une carte est planaire si et seulement si la somme du nombre de sommets et du nombre de faces est égale au nombre d'arêtes plus 2.

Exemple[modifier | modifier le code]

Une carte planaire est un plongement d’un graphe connexe et planaire sur la sphère, considéré à déformation continue près. Bien que définies sur la sphère, on préfère dessiner les cartes dans le plan. Une des faces se trouve alors privilégiée, la face externe. Dans l'exemple ci-dessous, la face externe est (1 3 18 16 14 12 10).

Exemple de carte planaire
Graphe planaire
Carte planaire $(B,\sigma ,\alpha )$ par sommets et arêtes
Carte planaire $(B,\varphi ,\alpha )$ par faces et arêtes

Les trois permutations
$B$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
$\alpha$	2	1	4	3	6	5	8	7	10	9	12	11	14	13	16	15	18	17
$\sigma$	7	3	2	18	4	15	9	6	1	11	10	13	12	8	14	17	16	5
$\varphi$	3	7	18	2	15	4	6	9	11	1	13	10	8	12	17	14	5	16

Énumération des cartes planaires[modifier | modifier le code]

Le comptage des cartes planaires remonte à des travaux de Tutte^[7]^,^[8]. L'approche par la combinatoire bijective a commencé au début des années 1980, développée surtout par l'école bordelaise de combinatoire^[9]^,^[10]. Une illustration en est le dénombrement de cartes planaires « tétravalentes » (où chaque sommet est de degré 4) à n sommets : ce nombre est^[11]

m_{n}=2{\frac {3^{n}}{(n+1)(n+2)}}{\binom {2n}{n}}

Cette formule suggère une bijection avec une famille d'arbres ; c'est ce genre de bijections qui est établie, pour montrer aussi que les séries génératrices de ces suites de nombres sont algébriques. D'autres applications ont été données^[12].

Généralisation[modifier | modifier le code]

La définition d'une carte combinatoire s'étend à toute dimension^[13]^,^[14] : Une carte combinatoire de dimension $n$ est une structure $(B,\beta _{1},\dots ,\beta _{n})$ , où

$B$ est un ensemble fini de brins;
$\beta _{1}$ est une permutation sur $B$ ;
$\beta _{2},\ldots ,\beta _{n}$ sont des involutions sur $B$ ;
$\beta _{i}\circ \beta _{j}$ est une involution pour tout $i,j$ vérifiant $2\leq i+2\leq j$ .

Une carte combinatoire de dimension n représente une subdivision d'un espace fermé orientable de dimension n. Un brin est un élément abstrait qui sert à définir les bijections. Les contraintes de la dernière condition garantissent la cohérence topologique de l'objet représenté : une carte combinatoire représente une quasi-variété.

Notes et références[modifier | modifier le code]

↑ Jack Edmonds, « A Combinatorial Representation for Polyhedral Surfaces », Notices Amer. Math. Soc., vol. 7,‎ 1960, p. 646-650.
↑ Alain Jacques, « Constellations et Graphes Topologiques », dans Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), Amsterdam, North-Holland, 1970 (MR 297622), p. 657–673
↑ ^{a et b} Alain Jacques, Constellations et propriétés algébriques des graphes topologiques (thèse de doctorat), Faculté des Sciences, Université de Paris, 1969 (HAL hal-01591126).
↑ Gerhard Ringel, Map Color Theorem, Berlin, Springer-Verlag, coll. « Grundlehren der mathematischen Wussenschaften » (n^o 209), 1974, xii+194 (ISBN 978-3-642-65761-0 et 978-3-642-65759-7, DOI 10.1007/978-3-642-65759-7, présentation en ligne).
↑ Jean-Claude Fournier, « Le théorème du coloriage des cartes (ex-conjecture de Heawood et conjecture des quatre couleurs) », Séminaire N. Bourbaki,‎ 1977-1978, exposé n° 509, p. 41-64 (lire en ligne).
↑ Robert Cori, Un code pour les graphes planaires et ses applications, Société mathématique de France, coll. « Astérisque » (n^o 27), 1975, 169 p. (ISSN 0303-1179, SUDOC 017449685).
↑ William Thomas Tutte, « A census of planar triangulations », Canadian Journal of Mathematics, vol. 14,‎ 1962, p. 21-39.
↑ William Thomas Tutte, « A census of planar maps », Canadian Journal of Mathematics, vol. 15,‎ 1963, p. 249-271.
↑ Robert Cori et Bernard Vauquelin, « Planar maps are well labelled trees », Canad, J. Math, vol. 33, n^o 5,‎ 1981, p. 1023-1042.
↑ J. Bouttier, Philippe Di Francesco et E. Guitter, « Census of planar maps : from the one-matrix model solution to a combinatorial proof », Nuclear Physics B, vol. 645, n^o 3,‎ 2002, p. 477-499.
↑ Julien Courtiel, Combinatoire du polynôme de Tutte et des cartes planaires (thèse de doctorat en informatique), Université de Bordeaux I, Labri, octobre 2014 (arXiv 1411.0737, lire en ligne).
↑ Alexander Ekart, « The Cori-Vauquelin-Schaeffer Bijection and its Applications in the Theory of Scaling Limits of Random Labelled Quadrangulations and Trees », Diploma Thesis, TU Wien, 7 septembre 2015 (consulté le 5 janvier 2018).
↑ Pascal Lienhardt, « Topological models for Boundary Representation : a comparison with n-dimensional generalized maps », Computer-Aided Design, vol. 23, n^o 1,‎ 1991, p. 59-82.
↑ Pascal Lienhardt, « N-dimensional generalized combinatorial maps and cellular quasi-manifolds », International Journal on Computational Geometry and Applications, vol. 4, n^o 3,‎ 1994, p. 275-324.

Articles liés[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Combinatorial maps in CGAL, the Computational Geometry Algorithms Library:
« Combinatorial maps », CGAL, the Computational Geometry Algorithms Library (consulté en octobre 2011)
Combinatorial maps in CGoGN, Combinatorial and Geometric modeling with Generic N-dimensional Maps

[1] Jack Edmonds, « A Combinatorial Representation for Polyhedral Surfaces », Notices Amer. Math. Soc., vol. 7,‎ 1960, p. 646-650.

[2] Alain Jacques, « Constellations et Graphes Topologiques », dans Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), Amsterdam, North-Holland, 1970 (MR 297622), p. 657–673

[th-3] {a et b} Alain Jacques, Constellations et propriétés algébriques des graphes topologiques (thèse de doctorat), Faculté des Sciences, Université de Paris, 1969 (HAL hal-01591126).

[4] Gerhard Ringel, Map Color Theorem, Berlin, Springer-Verlag, coll. « Grundlehren der mathematischen Wussenschaften » (n^o 209), 1974, xii+194 (ISBN 978-3-642-65761-0 et 978-3-642-65759-7, DOI 10.1007/978-3-642-65759-7, présentation en ligne).

[5] Jean-Claude Fournier, « Le théorème du coloriage des cartes (ex-conjecture de Heawood et conjecture des quatre couleurs) », Séminaire N. Bourbaki,‎ 1977-1978, exposé n° 509, p. 41-64 (lire en ligne).

[6] Robert Cori, Un code pour les graphes planaires et ses applications, Société mathématique de France, coll. « Astérisque » (n^o 27), 1975, 169 p. (ISSN 0303-1179, SUDOC 017449685).

[7] William Thomas Tutte, « A census of planar triangulations », Canadian Journal of Mathematics, vol. 14,‎ 1962, p. 21-39.

[8] William Thomas Tutte, « A census of planar maps », Canadian Journal of Mathematics, vol. 15,‎ 1963, p. 249-271.

[9] Robert Cori et Bernard Vauquelin, « Planar maps are well labelled trees », Canad, J. Math, vol. 33, n^o 5,‎ 1981, p. 1023-1042.

[10] J. Bouttier, Philippe Di Francesco et E. Guitter, « Census of planar maps : from the one-matrix model solution to a combinatorial proof », Nuclear Physics B, vol. 645, n^o 3,‎ 2002, p. 477-499.

[11] Julien Courtiel, Combinatoire du polynôme de Tutte et des cartes planaires (thèse de doctorat en informatique), Université de Bordeaux I, Labri, octobre 2014 (arXiv 1411.0737, lire en ligne).

[12] Alexander Ekart, « The Cori-Vauquelin-Schaeffer Bijection and its Applications in the Theory of Scaling Limits of Random Labelled Quadrangulations and Trees », Diploma Thesis, TU Wien, 7 septembre 2015 (consulté le 5 janvier 2018).

[13] Pascal Lienhardt, « Topological models for Boundary Representation : a comparison with n-dimensional generalized maps », Computer-Aided Design, vol. 23, n^o 1,‎ 1991, p. 59-82.

[14] Pascal Lienhardt, « N-dimensional generalized combinatorial maps and cellular quasi-manifolds », International Journal on Computational Geometry and Applications, vol. 4, n^o 3,‎ 1994, p. 275-324.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]