Sous-arbres induits pleinement feuillus

Nadeau, Émile (2018). « Sous-arbres induits pleinement feuillus » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en mathématiques.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (10MB)

Résumé

L'étude des sous-arbres induits pleinement feuillus est un nouveau sujet d'intérêt en théorie des graphes. Un sous-graphe induit est un sous-graphe constitué d'un ensemble de sommets et de toutes les arêtes qui les relient. Un sous-graphe induit qui est un arbre est appelé sous-arbre induit. On dit, de plus, qu'il est pleinement feuillu, s'il maximise son nombre de feuilles parmi tous les sous-arbres induits de même taille dans le graphe. L'objectif de ce travail est d'étudier ces objets d'un point de vue algorithmique et de tenter de les caractériser. Dans un premier temps, on introduit la fonction feuille d'un graphe qui à chaque entier n, associe le nombre maximal de feuilles qu'un sous-arbre induit de taille n peut réaliser, c'est-à-dire le nombre de feuilles d'un sous-arbre induit pleinement feuillu de taille n. On montre que le calcul de la fonction feuille est un problème difficile, puis on introduit une structure de données que l'on utilise dans un algorithme de type séparation et évaluation progressive, pour le calcul de la fonction feuille. La démonstration de l'exactitude de l'algorithme est présentée et des données empiriques sur sa performance sont analysées. Dans un deuxième temps, on introduit le problème de réalisation de la fonction feuille, qui consiste à décider si une fonction donnée est la fonction feuille d'un certain graphe. On utilise des outils de la combinatoire des mots pour donner des conditions nécessaires afin qu'une fonction soit réalisable. On présente, ensuite, un outil supplémentaire, les mots préfixes normaux. Ces derniers se définissent ainsi : il s'agit des mots binaires dont chaque préfixe contient plus de 1 que tous les facteurs de la même longueur que ce préfixe. Finalement, à l'aide de cet ensemble de mots, on décrit les fonctions feuilles qui peuvent être réalisées par un graphe chenille et on donne une caractérisation des graphes chenilles ayant la même fonction feuille. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Théorie des graphes, arbres, NP-complet, chenilles, graphes induits

Type:	Mémoire accepté
Informations complémentaires:	Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse:	Saliola, Franco
Mots-clés ou Sujets:	Théorie des graphes / Arbres / Problèmes NP-complets / Graphes chenilles / Sous-graphes induits / Sous-arbre induit pleinement feuillu
Unité d'appartenance:	Faculté des sciences > Département de mathématiques
Déposé par:	Service des bibliothèques
Date de dépôt:	04 mars 2019 16:08
Dernière modification:	21 nov. 2019 09:28
Adresse URL :	http://archipel.uqam.ca/id/eprint/12310

Modifier les métadonnées (propriétaire du document)

Statistiques