1 |
Codes et jeux de soustraction et de poursuite dans les graphes / Codes and subtraction and pursuit games in graphsCoupechoux, Pierre 15 June 2018 (has links)
Les codes identifiants ont été introduits en 1998 par Karpovsky, Chakrabarty et Levitin. Un code identifiant est un sous-graphe tel que chaque sommet est identifié de manière unique par les sommets du code qui l'entourent. Il existe plusieurs variantes de ces codes, dont notamment une version colorée dans laquelle les sommets sont identifiés par les couleurs dans leur voisinage. Dans cette thèse, nous cherchons en particulier à construire un cycle le plus grand possible qui admette une coloration identifiante, étant donné un nombre de couleurs fixé. Nous avons aussi étudié le problème des codes identifiants sur une classe particulière de graphes orientés : les tournois. Dans une seconde partie, nous avons aussi étudié deux jeux particuliers. Le premier est une généralisation des jeux octaux - qui se jouent normalement sur un tas - aux graphes. Plus précisemment, le jeu 0.33 ; chaque joueur peut retirer un ou deux sommets voisins d'un graphe, sans déconnecter ce dernier. Le premier qui ne peut plus jouer perd. Nous avons été capable de caractériser les issues de ce jeu dans des classes de graphes particulières, les étoiles subdivisées et les bi-étoiles subdivisées. Le second jeu est appelé le jeu du Pompier (Firefighter). Il consiste à arrêter un feu qui se propage dans un graphe en protégeant des sommets à chaque tour. Nous avons résolu une conjecture sur ce jeu, et introduit la version online, pour laquelle nous avons pu donner des résultats d'approximation. / Identifying codes were introduced in 1998 by Karpovsky, Chakrabarty and Levitin. An identifying code is a subgraph such that each vertex is uniquely identified by the vertices in its neighborhood. There are several variants of these codes, including a colored version where the vertices are identified by the colors in their neighborhood. In this phd, we want to build an identifying coloring of a large cycle, given a fixed number of colors. We also studied identified codes in a certain class of oriented graphs: tournaments. We have also studied some topics in the game theory. The first one is a generalization of octal games, where we play on a graph instead of a heap. More precisely, the 0.33 game; each player can remove one or two vertices in a graph, with no disconnection allowed. The first player who cannot play loses. We studied this game in some graph classes: subdivided stars and subdivided bistars. The other game is called the Firefighter game. It's a one player game, where this one wants to contain a spreading fire in a graph. We solved a conjecture about this game, and introduced the online version of the game, for which we found some approximation results.
|
2 |
Étude par dynamique moléculaire ab-initio des verres de chalcogénures GeS2 et (M2S)0.33(GeS2)0.66 M=Na, AgLe Roux, Sébastien 11 July 2008 (has links) (PDF)
La dynamique moléculaire ab-initio est utilisée pour étudier les verres de chalcogénures GeS2 et GeS2 dopés de formule (M2S)0.33(GeS2)0.66 M=Na,Ag. Une nouvelle méthode théorique d'analyse de la connectivité des matériaux amorphes est proposée en utilisant les recherches d'anneaux. L'effet de la vitesse de trempe sur les propriétés physiques des verres GeS2 est analysé. L'analyse de l'ordre à moyenne et courte portée révèle l'existence d'une vitesse de trempe maximale au dessus de laquelle la structure du matériau est trop proche de celle du liquide. Ceci est confirmé par les résultats des recherches d'anneaux qui permettent également de mettre en avant des différences fondamentales entre les connectivités des phases liquides et vitreuses du GeS2. Enfin la présence de zones chargées est confirmée dans les matrices vitreuses de GeS2, même aux plus basses vitesses de trempe. Les conditions nécessaires à la diffusion des atomes de sodium dans les matrices vitreuses (Na2S)0.33(GeS2)0.66 sont étudiées. Lorsque la diffusion apparaît le déplacement des atomes de sodium semble devenir coopératif. Des essais de paramétrisation sont réalisés pour tenter de modéliser les verres de chalcogénures (Ag2S)0.33(GeS2)0.66 et GeS2 à l'aide du code SIESTA.
|
Page generated in 0.0129 seconds