Afficher la notice abrégée

dc.contributor.advisorSopena, Eric
dc.contributor.authorGUIGNARD, Adrien
dc.contributor.otherDoberc, Paul
dc.contributor.otherDuchêne, Eric
dc.contributor.otherRaspaud, André
dc.date2011-12-06
dc.date.accessioned2020-12-14T21:10:12Z
dc.date.available2020-12-14T21:10:12Z
dc.identifier.urihttp://ori-oai.u-bordeaux1.fr/pdf/2011/GUIGNARD_ADRIEN_2011.pdf
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/21565
dc.identifier.nnt2011BOR14391
dc.description.abstractLa 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.
dc.description.abstractEnPart 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 characterization and also compute winning strategies for Alice and Bob. In order to do so, we are led to define a new notion, the bitype, that for a partially-colored graph G associates two letters indicating who has a winning strategy respectively on G and G with an isolated vertex. Bitypes allow us to demonstrate several properties, in particular to compute the game chromatic number of a graph from the bitypes of its connected components.
dc.language.isofr
dc.subjectJeux combinatoires
dc.subjectNombre chromatique ludique
dc.subjectJeux de coloration de graphes
dc.subjectJeu de Domination
dc.subjectArbres
dc.subjectChenilles
dc.subject.enCombinatorial games
dc.subject.enGame chromatic number
dc.subject.enGraph coloring games
dc.subject.enDomination game
dc.subject.enTrees
dc.subject.enCaterpillars
dc.titleJeux de coloration de graphes
dc.title.enGraphs coloring games
dc.typeThèses de doctorat
bordeaux.hal.laboratoriesThèses de l'Université de Bordeaux avant 2014*
bordeaux.hal.laboratoriesLaboratoire bordelais de recherche en informatique
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.type.institutionBordeaux 1
bordeaux.thesis.disciplineInformatique
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde)
star.origin.linkhttps://www.theses.fr/2011BOR14391
dc.contributor.rapporteurGravier, Sylvain
dc.contributor.rapporteurKheddouci, Hamamache
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Jeux%20de%20coloration%20de%20graphes&rft.atitle=Jeux%20de%20coloration%20de%20graphes&rft.au=GUIGNARD,%20Adrien&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée