Event
脡mile Nadeau, Universit茅 du Qu茅bec 脿 Montr茅al
R茅alisation de la fonction feuille, graphe chenille et mots pr茅fixes normaux.
Soit $G$ un graphe. La fonction feuille $L_G(i)$, pour $i$ un entier entre 0 et $|G|$, retourne le nombre maximal de feuilles r茅alis茅 par un sous-arbres induit de taille $i$ dans $G$. Je pr茅senterai le probl猫me de r茅alisation de la fonction feuille qui consiste 脿 d茅terminer s'il existe un graphe poss茅dant une fonction donn茅e comme fonction feuille ainsi que certains r茅sultats g茅n茅raux sur celui-ci. Je pr茅senterai, par la suite, une solution 脿 ce probl猫me pour les graphes chenilles. Cette solution m'am猫nera 脿 introduire deux outils de la combinatoire des mots: la d茅riv茅e discr猫te et les mots pr茅fixes normaux.