Event
Émile Nadeau, Université du Québec à Montréal
Friday, February 2, 2018 13:30to14:30
Room PK-4323, Pavillon President-Kennedy, CA
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.