Browsing Thèses et mémoires électroniques de l’Université de Montréal by Advisor "Hahn, Gena"
Now showing items 1-17 of 17
-
Complexité des homomorphismes de graphes avec listes
(2012-09-04)Les problèmes de satisfaction de contraintes, qui consistent à attribuer des valeurs à des variables en respectant un ensemble de contraintes, constituent une large classe de problèmes naturels. Pour étudier la complexité de ces problèmes, il est commode ... -
Domination éternelle dans les graphes
(2019-03-13)Le présent mémoire traite du problème de domination éternelle dans les graphes. Nous considérons trois modèles différents du problème, à savoir le modèle du garde, de l’anglais one-guard moves model, le modèle des gardes, de l’anglais all-guards move ... -
Droites sur les hypergraphes
(2015-02-18)Le Théorème de Sylvester-Gallai affirme que dans un ensemble fini S de points dans le plan, où les points ne sont pas tous sur une même droite, il y a une droite qui passe par exactement deux points de S. Chvátal [14] a étendu la notion de droites ... -
Une étude des graphes jumeaux via l'auto-abritement
(2022-05-04)On étudie la conjecture des graphes jumeaux dénombrables, cas spécifique d’une conjecture de Thomassé, qui dit que le nombre de jumeaux d’un graphe dénombrable ( ses sous-graphes propres desquels il est aussi un sous-graphe propre) est soit nul, soit ... -
Le filtrage du protocole SMB
(2001) -
Le jeu de policiers-voleur sur différentes classes de graphes
(2021-07-14)Ce mémoire étudie le jeu de policiers-voleur et contient trois articles, chacun portant sur une classe de graphes spécifique. Dans le premier chapitre, la notation et les définitions de base de la théorie de graphe qui nous serons utiles sont introduites. ... -
Trois résultats en théorie des graphes
(2023-02-22)Cette thèse réunit en trois articles mon intérêt éclectique pour la théorie des graphes. Le premier problème étudié est la conjecture de Erdos-Faber-Lovász: La réunion de k graphes complets distincts, ayant chacun k sommets, qui ont deux-à-deux au ...