Threes problems on cycles in simple graphs

Zare, Ebrahim (2017). « Threes problems on cycles in simple graphs » 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 (4MB)

Résumé

Le présent mémoire a pour sujet trois concepts différents concernant les cycles dans des graphes simples : indice de décyclage (la taille minimum d'un transversal de cycles), le nombre cyclomatique (la taille d'une base de l'espace des cycles) et la base minimum de l'espace des cycles. Ils ont tous de nombreuses applications en informatique ainsi que dans d'autres sciences appliquées. Nous nous intéressons à ce qui arrive à ces paramètres quand de nouveaux graphes sont construits comme produits divers à partir de graphes donnés. Nous survolons la littérature et nous présentons quelques nouveaux résultats dans ces trois directions. Nous donnons également un contre-exemple à l'algorithme de Kaveh et Mizrai pour trouver une base minimum de l'espace des cycles du produit lexicographique et nous en présentons une version correcte. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Produits de graphes, jointure de graphes, indice de décyclage, nombre cyclomatique, base minimum de cycles

Type:	Mémoire accepté
Informations complémentaires:	Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse:	Laforest, Louise
Mots-clés ou Sujets:	Théorie des graphes / Cycles / Chemins et cycles
Unité d'appartenance:	Faculté des sciences > Département de mathématiques
Déposé par:	Service des bibliothèques
Date de dépôt:	16 févr. 2018 15:36
Dernière modification:	16 févr. 2018 15:36
Adresse URL :	https://archipel.uqam.ca/secure/id/eprint/10919

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

Statistiques