Colloque

Une théorie de l'énumération des structures connexes en fonction de la distance

Ivan Constantineau

Membre a labase

Ivan Constantineau

Résumé du colloque

Soit G une graphe (fini) connexe et x un sommet fixé de G. Tout sommet y de G est à une certaine distance (non-orientée) d(x,y) de x. Appelons G_i(x) le sous-graphe de G constitué de l'ensemble S_i de sommets de G qui sont à distance i de x et des flèches induites de G. Le graphe G est entièrement caractérisé par le choix du sommet x, de la famille {G_i} et par les graphes bipartis B(S_i, S_{i+1}) qui joignent S_i à S_{i+1}. On obtient ainsi un processus de "dissection" des graphes connexes qui a des propriétés énumératives remarquables. En effet, il est possible, pour certaines familles F de graphes G, de retrouver la structure des {G_i} et B(S_i, S_{i+1}) correspondants. Lorsque les nombres de ces derniers sont connus, on obtient une formule explicite pour la cardinalité de F. De plus, ce processus s'étend de manière naturelle à l'énumération des structures laissées fixes par une permutation donnée. Dans cet exposé nous présentons des formules générales pour cette énumération en fonction de la distance, à la fois pour les structures étiquetées et celles fixes par une permutation. Nous les illustrons avec de nombreux exemples.

Contexte

Section :

Mathématiques et statistiques

Thème du colloque :

Mathématiques et statistiques

Hôte : Université du Québec à Montréal

Découvrez d'autres communications scientifiques

Dans le même colloque
Du même congressiste

Titre du colloque :

Mathématiques et statistiques

Introduction à la représentation géométrique uniforme des B-splines: le cas cubique

Michel Fleury

Fonctions multivoques différentiables et théorème de la moyenne

Danielle Cormier

Une théorie de l'énumération des structures connexes en fonction de la distance

Ivan Constantineau

Voir tous les contenus de ce colloque

Autres communications du même congressiste :

Thème du colloque :

Mathématiques et statistiques

Une théorie de l'énumération des structures connexes en fonction de la distance

Ivan Constantineau