Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for subject:(Graphes chenilles). Showing records 1 – 3 of 3 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Université du Québec à Montréal

1. Porrier, Carole. Arbres de Penrose pleinement feuillus.

Degree: 2019, Université du Québec à Montréal

En théorie des graphes, la question des arbres pleinement feuillus, c'est-à-dire ayant le plus grand nombre de feuilles possible pour un nombre de sommets fixé, a récemment été étudiée dans des pavages réguliers du plan et de l'espace par Blondin Massé et al., et on peut se demander ce qu 'il en est dans d'autres pavages. On s'intéresse ici plus particulièrement à l'étude de cette question dans les pavages de Penrose, qui ont la particularité d'être apériodiques. La question que l'on se pose ici est donc la suivante : dans les pavages de Penrose, parmi les sous-arbres induits par le graphe sous-jacent, combien les arbres pleinement feuillus ont-ils de feuilles en fonction de leur taille n? La question étant déjà complexe dans certaines grilles régulières, nous présentons pour l'instant des résultats expérimentaux et théoriques partiels ainsi que des pistes de recherche. En subdivisant le problème, on obtient d'abord une majoration de la fonction feuille, puis l'étude de chenilles suivant les worms nous donne une minoration. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : graphe, arbre, pavage, pavage de Penrose, sous-arbre induit pleinement feuillu, chenille, suite musicale, mot de Fibonacci

Subjects/Keywords: Arbres; Théorie des graphes; Pavages apériodiques; Sous-arbre induit pleinement feuillu; Graphes chenilles

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Porrier, C. (2019). Arbres de Penrose pleinement feuillus. (Thesis). Université du Québec à Montréal. Retrieved from http://archipel.uqam.ca/12996/1/M16182.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Porrier, Carole. “Arbres de Penrose pleinement feuillus.” 2019. Thesis, Université du Québec à Montréal. Accessed February 25, 2021. http://archipel.uqam.ca/12996/1/M16182.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Porrier, Carole. “Arbres de Penrose pleinement feuillus.” 2019. Web. 25 Feb 2021.

Vancouver:

Porrier C. Arbres de Penrose pleinement feuillus. [Internet] [Thesis]. Université du Québec à Montréal; 2019. [cited 2021 Feb 25]. Available from: http://archipel.uqam.ca/12996/1/M16182.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Porrier C. Arbres de Penrose pleinement feuillus. [Thesis]. Université du Québec à Montréal; 2019. Available from: http://archipel.uqam.ca/12996/1/M16182.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation


Université du Québec à Montréal

2. Nadeau, Émile. Sous-arbres induits pleinement feuillus.

Degree: 2018, Université du Québec à Montréal

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

Subjects/Keywords: Théorie des graphes; Arbres; Problèmes NP-complets; Graphes chenilles; Sous-graphes induits; Sous-arbre induit pleinement feuillu

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Nadeau, . (2018). Sous-arbres induits pleinement feuillus. (Thesis). Université du Québec à Montréal. Retrieved from http://archipel.uqam.ca/12310/1/M15895.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Nadeau, Émile. “Sous-arbres induits pleinement feuillus.” 2018. Thesis, Université du Québec à Montréal. Accessed February 25, 2021. http://archipel.uqam.ca/12310/1/M15895.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Nadeau, Émile. “Sous-arbres induits pleinement feuillus.” 2018. Web. 25 Feb 2021.

Vancouver:

Nadeau . Sous-arbres induits pleinement feuillus. [Internet] [Thesis]. Université du Québec à Montréal; 2018. [cited 2021 Feb 25]. Available from: http://archipel.uqam.ca/12310/1/M15895.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Nadeau . Sous-arbres induits pleinement feuillus. [Thesis]. Université du Québec à Montréal; 2018. Available from: http://archipel.uqam.ca/12310/1/M15895.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation


Université de Bordeaux I

3. Guignard, Adrien. Jeux de coloration de graphes : Graphs coloring games.

Degree: Docteur es, Informatique, 2011, Université de Bordeaux I

La thèse porte sur les deux thèmes des Jeux combinatoires et de la théorie des graphes. Elle est divisée en deux parties.1) Le jeu de Domination et ses variantes: Il s'agit d'un jeu combinatoire qui consiste à marquer les sommets d'un graphe de telle sorte qu'un sommet marqué n'ait aucun voisin marqué. Le joueur marquant le dernier sommet est déclaré gagnant. Le calcul des stratégies gagnantes étant NP-difficile pour un graphe quelconque, nous avons étudié des familles particulières de graphes comme les chemins, les scies ou les chenilles. Pour ces familles on peut savoir en temps polynomial si un graphe est perdant. Nous avons également étudié 28 variantes du jeu de domination, dont les 12 variantes définies par J. Conway sur un jeu combinatoire quelconque. 2) Le nombre chromatique ludique des arbres: Ce paramètre est calculé à partir d'un jeu de coloration où Alice et Bob colorient alternativement et proprement un sommet d'un graphe G avec l'une des k couleurs. L'objectif d'Alice est de colorier complètement le graphe alors que Bob doit l'en empêcher. Nous nous sommes intéressés au jeu avec 3 couleurs sur un arbre T. Nous souhaitons déterminer les arbres ayant un nombre chromatique ludique 3, soit ceux pour lesquels Alice a une stratégie gagnante avec 3 couleurs. Ce problème semblant difficile à résoudre sur les arbres, nous avons résolu des sous-familles: les 1-chenilles puis les chenilles sans trous.

Part 1: Domination Game and its variantsDomination game is a combinatorial game that consists in marking vertices of a graph so that a marked vertex has no marked neighbors. The first player unable to mark a vertex loses the game.Since the computing of winning strategies is an NP-hard problem for any graphs, we examine some specific families of graphs such as complete k-partite graphs, paths or saws. For these families, we establish the set of losing elements. For other families, such as caterpillars, we prove that exists a polynomial algorithm for the computation of outcome and winning strategies. No polynomial algorithm has been found to date for more general families, such as trees.We also study 28 variants of Domination game, including the 12 variants defined by J. Conway for any combinatorial game. Using game functions, we find the set of losing paths for 10 of these 12 variants. We also investigate 16 variants called diameter, for instance when rules require to play on the component that has the largest diameter.Part 2: The game chromatic number of treesThis parameter is computed from a coloring game: Alice and Bob alternatively color the vertices of a graph G, using one of the k colors in the color set. Alice has to achieve the coloring of the entire graph whereas Bob has to prevent this. Faigle and al. proved that the game chromatic number of a tree is at most 4. We undertake characterization of trees with a game chromatic number of 3. Since this problem seems difficult for general trees, we focus on sub-families: 1-caterpillars and caterpillars without holes.For these families we provide the…

Advisors/Committee Members: Sopena, Eric (thesis director).

Subjects/Keywords: Jeux combinatoires; Nombre chromatique ludique; Jeux de coloration de graphes; Jeu de Domination; Arbres; Chenilles; Combinatorial games; Game chromatic number; Graph coloring games; Domination game; Trees; Caterpillars

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Guignard, A. (2011). Jeux de coloration de graphes : Graphs coloring games. (Doctoral Dissertation). Université de Bordeaux I. Retrieved from http://www.theses.fr/2011BOR14391

Chicago Manual of Style (16th Edition):

Guignard, Adrien. “Jeux de coloration de graphes : Graphs coloring games.” 2011. Doctoral Dissertation, Université de Bordeaux I. Accessed February 25, 2021. http://www.theses.fr/2011BOR14391.

MLA Handbook (7th Edition):

Guignard, Adrien. “Jeux de coloration de graphes : Graphs coloring games.” 2011. Web. 25 Feb 2021.

Vancouver:

Guignard A. Jeux de coloration de graphes : Graphs coloring games. [Internet] [Doctoral dissertation]. Université de Bordeaux I; 2011. [cited 2021 Feb 25]. Available from: http://www.theses.fr/2011BOR14391.

Council of Science Editors:

Guignard A. Jeux de coloration de graphes : Graphs coloring games. [Doctoral Dissertation]. Université de Bordeaux I; 2011. Available from: http://www.theses.fr/2011BOR14391

.