Langage de Programmation : C
Environnement de Développement :
UNIX, LinuX
Résumé du Projet : Dans un premier temps on fera l'implémentation
d'une bijection géométrique entre une famille de cartes planaires pointées et les partitions
d'un polygone en pentagones. Les cartes planaires sont des projections de graphes sur la
sphere de R3.
Le but est ensuite d'implémenter la génération aléatoire de partitions
d'un polygone en pentagones.
Le Sujet du projet :
Une carte planaire est une partition de la sphere de R3
en trois ensembles de cellules, l'ensemble des sommets qui sont des points sur la sphere,
l'ensemble des arêtes qui sont des arcs simples de Jordan et l'ensemble des faces qui sont des
domaines simplement connexes. Chacun de ces ensembles peut etre représenté par une permutation
. Cette représentation permet de coder simplement les cartes.
Il faudrait donc implémenter une bijection entre la famille des cartes
planaires d'ordre 1 (chaque arête possède au moins une extrémité incidente à la face
exterieure) à n arêtes et l'ensemble des partitions en pentagone d'un polygone pointé à 3n+2 arêtes.
Une implémentation de la génération aléatoire de partitions d'un polygone en pentagones
permettra alors d'obtenir la génération aléatoire des cartes planaires pointées d'ordre 1.