Sujet 1 : les complexes simpliciaux

Encadrant

Phil. REITZ.

Objectif

Les complexes simpliciaux (cf annexe) sont des objets algébriques qui généralisent le concept de graphe ; ils font partie des objets abstraits candidats au traitement des problèmes de description à des niveaux d'échelles multiples. Ils ont donc beaucoup d'application en analyse d'image ou en modélisation, par exemple.

Concevoir une bibliothèque de classes (Java, C++, autres) permettant de manipuler des complexes simpliciaux. Les opérations applicables sur ces complexes sont (liste non exhaustive) :

• initialisation d'un complexe à partir d'un ensemble prédéfini de sommets
• calcul de la dimension d'un complexe simplicial ou de l'un de ses simplexes
• vérifier qu'un objet prétendument un complexe simplicial l'est effectivement (cf annexe)
• ajouter, enlever ou modifier un simplexe à un complexe simplicial
• énumérer tous les simplexes d'un complexe simplicial (ceux ayant une dimension égale à un entier n, ou inférieure ou égale à un entier)
• énumérer certains simplexes d'un complexe simplicial à partir d'un de ses simplexes, dit simplexe de référence (tous les simplexes qui le contiennent, tous les simplexes qu'il contient, etc).
• toute opération consitutant une généralisation d'une opération applicable aux graphes (exemple : connexité, vérifier qu'un graphe est un graphe partiel ou sous-graphe d'un autre, qu'il est isomorphe à un autre, etc).

Annexe : les complexes simpliciaux

Un complexe simplicial K est un couple (S, R) où S est un ensemble fini de sommets et R un sous-ensemble de l'ensemble des parties de S (R inclus dans P(S)), clos par intersection (si a et b sont deux éléments de R, alors a inter b l'est aussi). Les éléments de R autres que l'ensemble vide sont appelés les simplexes de K.

La dimension d'un simplexe est simplement son cardinal moins 1 ; un n-simplexe est un simplexe de dimension n. La dimension d'un complexe est la plus grande dimension des simplexes qui le constituent.

Un graphe (S, A) est un complexe simplicial (S, P₀(S) union P₁(S) union A), de dimension 1 ; P_k(X) dénote l'ensemble de toutes les parties de X qui ont un cardinal égal à k ; P₁(S) est donc l'ensemble des singletons de S, et P₀(S) l'ensemble composé du seul ensemble vide.