Sous-arbres induits dans les graphes séries-parallèles

Abdenbi, Moussa (2019). « Sous-arbres induits dans les graphes séries-parallèles » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en informatique.

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

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

Résumé

Dans ce mémoire nous nous intéressons au problème qui, étant donné un graphe simple G, interroge l'existence de sous-arbres induits de taille i ayant le plus grand nombre de feuilles. Un tel sous-arbre induit s'il existe est dit pleinement feuillu. Ce problème d'optimisation que nous nommons SAIPF pour sous-arbres induits pleinement feuillus, est associé au problème de décision SAIF, pour sous-arbres induits feuillus, que nous pouvons énoncer ainsi : étant donné un graphe simple G et deux entiers positifs i et f, est-ce qu'il existe un sous-arbre induit dans G avec i sommets et f, feuilles? Nous démontrons que ce problème est NP-complet dans le cas général, ce qui fait du problème SAIPF un problème NP-difficile. Ces problèmes n'étant probablement pas résolubles avec des algorithmes en temps polynomial, comme alternative, nous nous intéressons plutôt à des familles de graphes spécifiques où de tels algorithmes ont plus de chance d'exister. Nous considérons donc une sous-famille de graphes planaires, la famille particulière des graphes séries-parallèles, où le problème est "facile". Cette famille est définie récursivement par une succession de compositions en série ou en parallèle. Cette définition qui nous a permis, entre autres, de suivre la construction d'un graphe série-parallèle, nous a aussi permis d'énoncer un résultat essentiel de préservation d'optimalité dans ce processus de construction. Résultat qui a motivé et a inspiré la formulation d'équations récursives qui couvrent tous les cas possibles de construction de sous-arbres induits pleinement feuillus. Il s'avère que ces équations cachent des algorithmes de complexité temporelle polynomiale. Nous avons donc traduit ces équations en algorithmes qui prennent en paramètre d 'entrée la représentation arborescente d 'un graphe série-parallèle, appelée arbre de construction, et qui fournissent en sortie le nombre maximal de feuilles qu'un sous-arbre induit, s'il existe, peut réaliser pour un nombre de sommets donné. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Graphe série-parallèle, sous-arbre induit, feuille, pleinement feuillu, arbre de construction, graphe planaire

Type:	Mémoire accepté
Informations complémentaires:	Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse:	Blondin Massé, Alexandre
Mots-clés ou Sujets:	Théorie des graphes / Arbres / Sous-graphes induits / Graphes séries-parallèles / Algorithmes
Unité d'appartenance:	Faculté des sciences > Département d'informatique
Déposé par:	Service des bibliothèques
Date de dépôt:	09 oct. 2019 08:25
Dernière modification:	09 oct. 2019 08:25
Adresse URL :	http://archipel.uqam.ca/id/eprint/12833

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

Statistiques