Date : 2001
Editeur / Publisher : [S.l.] : [s.n.] , 2001
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Cartes -- Reconnaissance optique des formes (informatique)
Résumé / Abstract : La première partie de cette thèse est développée dans le cadre planaire. Par des décompositions topologiques nous construisons deux bijections. La première est une bijection entre les cartes planaires pointées d'ordre un dont l'arête pointée est un isthme d'un côté et les partitions de polygones pointés en pentagones de l'autre côté. La deuxième bijection est en fait un codage des hypercartes planaires par un langage généralisant le langage de Lukaciewicz.Les limites imposées par le cadre planaire peuvent devenir très contraignantes lorsque l'on applique sur des cartes des opérations topologiques. La deuxième partie de cette thèse traite donc des cartes de genre quelconque. Nous donnons une énumération des cartes n-coloriées sous forme d'une fraction multicontinue qui fait apparaître une équation généralisant aux cartes n-coloriées l'équation de Dyck sur les arbres. De nouvelles opérations topologiques sont alors introduites afin de nous permettre de retrouver cette équation de Dyck généralisée, par des méthodes topologiques et bijectives de décomposition des cartes. Nous commençons par retrouver l'équation de Dyck généralisée aux cartes de genre quelconque donnée par D. Arquès et J.F. Béraud, puis nous établissons l'équation souhaitée. En appliquant plusieurs fois les opérations qui nous ont permis de retrouver l'équation de Dyck généralisée aux cartes successives obtenues, on obtient une bijection entre cartes de genre quelconque et des arborescences où les sommets peuvent être coloriés de plusieurs couleurs suivant des règles que nous définirons. Cette bijection ainsi que celle obtenue pour les cartes n-coloriées, nous fournissent un codage de ces cartes par un langage algébrique. Dans la troisième partie, la bijection entre cartes de genre quelconque et arborescences multicouleurs obtenue dans la partie précédente est restreinte au cas planaire, ce qui nous permet de retrouver l'équation de Tutte vérifiée par la série génératrice des cartes planaires
Résumé / Abstract : Combinatorics on maps of any genus and multicolored planar trees First part of this thesis deals with planar maps. Two bijections are build using topological decompositions. The first one is a one-to-one correspondence between rooted planar maps of order one with a bridge root edge on one side and rooted polygons partitions into pentagons on the other side. Second bijection is in fact a coding of planar hypermaps with words of a language that generalized Lukaciewicz language. Planar studies limit us in the application of topological operations on maps. Second part is about maps studied independently of genus. An enumeration of n-colored rooted maps is given as a multi-continued fraction which reveals an equation that generalized the Dyck equation on planar trees. New topological operations are introduced. They permit us to dig up in another way this generalized Dyck equation by decomposing maps topologically and bijectively. The equation, presented by D. Arquès and J.F. Béraud, for the generating function of maps, is recovered previously to the other one in an analogous way. Applying repeatedly the operations which permitted to reveal the generalized Dyck equations to the successive transformed maps, a one-to-one correspondence is obtained between maps on any surface and planar trees with multicolored vertices. The repartitions rules for colors will be defined. This bijection and also the one got for n-colored maps, give us a coding of these maps with words of a context free language. The third part characterize the one-to-one correspondence between planar maps and a subset of multicolored planar trees, which leads to the recovering of the Tutte equation for the generating function of planar maps