Dissertations / Theses on the topic 'Jeux sur les graphes'

Chacun d'entre nous s'est déjà essayé à un jeu combinatoire, tel que les dames ou les échecs. Les jeux les plus connus présentent le double avantage de mêler plaisir ludique et réflexion. L'intérêt que les mathématiciens leur porte réside souvent autour de la recherche d'une stratégie gagnante pour l'un des deux joueurs. Du jeu de Nim jusqu'aux échecs, la complexité de cette recherche est très variable. Dans cette thèse, nous donnons tout d'abord un aperçu des principales étapes du développement de ce domaine, qui a commencé au début des années 1900, et soulignons son étroite corrélation avec des domaines connexes tels que la théorie des nombres, des codes correcteurs d'erreur ou des graphes. Nous nous intéressons ensuite à des variantes de jeux bien connus : le Wythoff's game et le Dots and Boxes. Nous présentons et expliquons les stratégies et positions de jeu favorables au premier et au second joueur. Enfin, nous regardons une version solitaire d'un jeu récent à deux joueurs : le Clobber. Il s'agit d'un casse-tête qui se joue en posant des pierres sur les sommets d'un graphe, et dont le but est de détruire le plus de pierres possibles. Nous donnons des résultats structurels et algorithmiques sur les grilles, les arbres, ou encore les hypercubes
Everyone has ever played a combinatorial game, such as chess or checkers. The interest of mathematicians about this subject is often related to the search of a winning strategy for one of both players. From the game of Nim to chess, the complexity of this search is very variable. In this manuscript, we firstly give a short view of the main stages of the topic, who really started in the beginning of the XXth century. Besides, we emphasize the correlation between combinatorial games and number theory, error-correcting codes, or graph theory. We then investigate some variations of « classical » combinatorial games : Wythoff's game and Dots and Boxes. We detail the strategy and « good » game positions for the first and the second player. We then consider a solitaire variation of a recent two-player game : Clobber. It is a one-player game, where stones are placed on the vertices of a given graph. A move consisting in removing a stone (under some conditions), the goal is to minimize the number of remaining stones at the end. We give structural and algorithmic results about this game played on grids, trees or hypercubes

Dans cette thèse nous étudions trois jeux à objectif compétitif sur les graphes. Les jeux à objectif compétitif proposent une approche dynamique des problèmes d'optimisation discrètes. L'idée générale consiste à associer à un problème d'optimisation (coloration, domination, etc.) un jeu combinatoire partisan de la façon suivante. Deux joueurs construisent tour à tour la structure reliée au problème d'optimisation. L'un d'eux cherche à ce que cette structure soit le plus optimale possible, tandis que l'autre essaye de l'en empêcher. Sous l'hypothèse que les deux joueurs jouent optimalement, la taille de la structure obtenue définit un invariant ludique.Nous commençons par étudier une variante 1-impropre du jeu de coloration, qui est le premier et le plus étudié des jeux à objectif compétitif. Dans ce jeu, les joueurs colorient les sommets d'un graphe de sorte que deux sommets adjacents ne partagent jamais la même couleur. Dans la version 1-impropre, un sommet peut avoir au plus un voisin ayant la même couleur que lui. Nous considérons ensuite le jeu de domination, dans lequel les deux joueurs doivent construire un ensemble dominant, c'est-à-dire un ensemble de sommets du graphe tel que tout autre sommet est adjacent à l'un des membres de cet ensemble. Finalement, nous définissons un nouveau jeu à objectif compétitif, relié au problème de coloration distinguante. Dans ce jeu, il s'agit de construire une coloration qui n'est invariante par aucun des automorphismes du graphe. Nous soulevons plusieurs interrogations stimulantes concernant ce nouveau jeu, notamment sur la caractérisation des graphes ayant un invariant ludique infini, par l'existence d'automorphismes d'ordre deux
In this thesis, we study three competitive optimization graph games. These games allow a dynamic approach to discrete optimization problems, which is an advantageous alternative way to consider these questions. The global idea consists in defining a combinatorial partisan game, associated to the original optimization problem, like coloring, domination, etc. Two players alternatively build the structure related to the optimization problem. One of them tries to obtain a structure as optimal as possible, whereas his opponent wants to prevent him from doing it. Under the hypothesis that both players play optimally, the size of the obtained structure defines a game invariant of the graph.We start by studying a 1-improper variation of the coloring game, which is the first and the most studied competitive optimization graph game. In this game, the players colors the vertices of a graph, such that two adjacent vertices do not share the same color. In the 1-improper version, we allow a vertex to have at most one neighbor with the same color as it. Then, we study the domination game, in which the players have to build a domination set, that is a sub-set of vertices such that any other vertex is adjacent to one of the vertex in this set. Finally, we define a new game, related to the distinguishing coloring problem. This game is about building a vertex-coloring which is preserved by none of the graph automorphisms. We raise some challenging open questions about this new game, especially concerning the characterization of graphs with infinite game invariant, by the existence of order two automorphisms

On considère des jeux à deux joueurs sur des familles de graphes infinis. Notre but est de déterminer le gagnant et de calculer une stratégie gagnante. Nous avons considéré différentes conditions de gain : accessibilité, Büchi (récurrence), Sigma3, parité, et différentes classes de graphes depuis les graphes de transition des automates à pile jusqu'aux graphes de la hiérarchie de Caucal et aux automates à pile d'ordre supérieur. Deux types de méthodes ont été proposées : une approche symbolique fondée sur des automates finis, et des techniques de jeu-simulation. L'approche symbolique permet de représenter et de manipuler des ensembles infinis de configurations. La jeu-simulation consiste à réduire un jeu donné à un autre jeu plus simple que l'on sait résoudre, puis d'en déduire le gagnant et une stratégie gagnante dans le jeu initial. À chaque fois des algorithmes ont été donnés pour calculer le gagnant et une stratégie gagnante (à coup sûr).

Les jeux à deux joueurs sur des graphes finis ou infinis permettent de modéliser de nombreux problèmes liés à la vérification des systèmes. Le système spécifié dépend de la nature du graphe de jeu considéré tandis que la propriété à vérifier est décrite par la condition de gain. Le premier joueur, Eve, représente un programme qui évolue dans un environnement hostile représenté par le second joueur, Adam. Dans ce formalisme, Eve possède une stratégie gagnante si et seulement si le programme peut être contrôlé de sorte à satisfaire la propriété spécifiée par la condition de gain. On souhaite alors décider si Eve possède une stratégie gagnante et si oui la déterminer, afin de synthétiser ensuite un contrôleur.

Dans cette thèse, les graphes de jeu considérés sont des graphes de processus à pile qui offrent une représentation finie simple de systèmes infinis relativement complexes. Sur de tels graphes, on peut considérer des conditions de gain classiques (accessibilité, Büchi ou parité) mais aussi des conditions plus spécifiques au modèle comme celles portant sur le bornage de la pile. On peut également combiner ces dernières entre elles.

Une première contribution a été de fournir une représentation des ensembles de positions gagnantes pour les jeux de parité ainsi qu'une nouvelle présentation des résultats connus pour ces derniers. On a alors pu étendre de façon naturelle les techniques de preuves à d'autres conditions de gain, notamment à celles portant sur le bornage de la pile.

Une autre contribution a été la description d'une famille de conditions de gain de complexité borélienne arbitraire finie pour lesquelles les jeux (sur des graphes finis ou sur des graphes de processus à pile) restent décidables.

L'étude des jeux sur les graphes de BPA et sur les graphes de processus à compteur a permis de proposer des techniques propres à ces modèles qui fournissent alors des bornes de complexité meilleures que celles obtenues dans le cas général des graphes de processus à pile.

Enfin, une dernière contribution a été de proposer une solution pour les jeux sur des graphes de processus à pile munis de conditions combinant des conditions régulières et des conditions sur la hauteur de pile et pour des conditions décrites par des automates à pile avec visibilité.

Au sein de la communauté scientifique, l’étude des réseaux d’énergie suscite un vif intérêt puisque ces infrastructures deviennent de plus en plus importantes dans notre monde moderne. Des outils mathématiques avancés et complexes sont nécessaires afin de bien concevoir et mettre en œuvre ces réseaux. La précision et l’optimalité sont deux caractéristiques essentielles pour leur conception. Bien que ces deux aspects soient au cœur des méthodes formelles, leur application effective reste largement inexplorée aux réseaux d’énergie. Cela motive fortement le travail développé dans cette thèse. Un accent particulier est placé sur le problème général de planification de la consommation d'énergie. Il s'agit d'un scénario dans lequel les consommateurs ont besoin d’une certaine quantité d’énergie et souhaitent que cette demande soit satisfaite dans une période spécifique (e.g., un Véhicule Électrique (VE) doit être rechargé dans une fenêtre de temps définie par son propriétaire). Par conséquent, chaque consommateur doit choisir une puissance de consommation à chaque instant (par un système informatisé), afin que l'énergie finale accumulée atteigne un niveau souhaité. La manière dont les puissances sont choisies est obtenue par l’application d’une « stratégie » qui prend en compte à chaque instant les informations pertinentes d'un consommateur afin de choisir un niveau de consommation approprié (e.g., l’énergie accumulée pour recharge le VE). Les stratégies peuvent être conçues selon une approche centralisée (dans laquelle il n'y a qu'un seul décideur qui contrôle toutes les stratégies des consommateurs) ou décentralisée (dans laquelle il y a plusieurs contrôleurs, chacun représentant un consommateur). Nous analysons ces deux scénarios dans cette thèse en utilisant des méthodes formelles, la théorie des jeux et l’optimisation. Plus précisément, nous modélisons le problème de planification de la consommation d'énergie à l'aide des processus de décision de Markov et des jeux stochastiques. Par exemple, l’environnement du système électrique, à savoir : la partie non contrôlable de la consommation totale (e.g., la consommation hors VEs), peut être représentée par un modèle stochastique. La partie contrôlable de la consommation totale peut s’adapter aux contraintes du réseau de distribution (e.g., pour ne pas dépasser la température maximale d'arrêt du transformateur électrique) et à leurs objectifs (e.g., tous les VEs soient rechargés). Cela peut être vu comme un système stochastique avec des multi-objectifs sous contraintes. Par conséquent, cette thèse concerne également une contribution aux modèles avec des objectives multicritères, ce qui permet de poursuivre plusieurs objectifs à la fois et une conception des stratégies qui sont fonctionnellement correctes et robustes aux changements de l'environnement
Within the research community, there is a great interest in exploring many applications of energy grids since these become more and more important in our modern world. To properly design and implement these networks, advanced and complex mathematical tools are necessary. Two key features for their design are correctness and optimality. While these last two properties are in the core of formal methods, their effective application to energy networks remains largely unexploited. This constitutes one strong motivation for the work developed in this thesis. A special emphasis is made on the generic problem of scheduling power consumption. This is a scenario in which the consumers have a certain energy demand and want to have this demand fulfilled before a set deadline (e.g., an Electric Vehicle (EV) has to be recharged within a given time window set by the EV owner). Therefore, each consumer has to choose at each time the consumption power (by a computerized system) so that the final accumulated energy reaches a desired level. The way in which the power levels are chosen is according to a ``strategy’’ mapping at any time the relevant information of a consumer (e.g., the current accumulated energy for EV-charging) to a suitable power consumption level. The design of such strategies may be either centralized (in which there is a single decision-maker controlling all strategies of consumers), or decentralized (in which there are several decision-makers, each of them representing a consumer). We analyze both scenarios by exploiting ideas originating from formal methods, game theory and optimization. More specifically, the power consumption scheduling problem can be modelled using Markov decision processes and stochastic games. For instance, probabilities provide a way to model the environment of the electrical system, namely: the noncontrollable part of the total consumption (e.g., the non-EV consumption). The controllable consumption can be adapted to the constraints of the distribution network (e.g., to the maximum shutdown temperature of the electrical transformer), and to their objectives (e.g., all EVs are recharged). At first glance, this can be seen as a stochastic system with multi-constraints objectives. Therefore, the contributions of this thesis also concern the area of multi-criteria objective models, which allows one to pursue several objectives at a time such as having strategy designs functionally correct and robust against changes of the environment

Cette thèse porte sur un certain nombre de problèmes algorithmiques motivés par la planification temporelle automatisée et la vérification formelle des systèmes réactifs et finis. Nous nous sommes concentrés sur les méthodes théoriques des jeux pour obtenir de nouvelles connaissances, des limites de complexité améliorées et des algorithmes plus rapides pour les modèles suivants: réseaux temporels hyper, réseaux conditionnels Simples / Hyper temporels, jeux de mise à jour, jeux Muller McNaughton et jeux Mean Payoff
This dissertation deals with a number of algorithmic problems motivated by automated temporal planning and formal verification of reactive and finite state systems. We focused on game theoretical methods to obtain novel insights, improved complexity bounds, and faster algorithms for the following models: Hyper Temporal Networks, Conditional Simple/Hyper Temporal Networks, Update Games, Muller McNaughton Games, and Mean Payoff Games

Les problèmes de recherche sur un graphe peuvent être exprimés sous la forme d’un jeu où un ensemble de chercheurs tentent de capturer un ensemble de fugitifs. Lorsqu’un tel jeu est joué en alternance par les deux ensembles de joueurs, nous parlons alors de jeux des policiers et des voleurs (« Cops and Robbers games ») ou plus simplement de jeux policiers-voleurs. Nowakowski et Winkler [28], et indépendamment Quilliot [45], ont introduit la première version des jeux policiers-voleurs dans laquelle un seul policier tente de capturer un seul voleur, les deux se déplaçant à tour de rôle vers des sommets adjacents de leurs positions courantes. Ils ont notamment proposé une jolie caractérisation des graphes gagnants pour le policier qui est basée sur l’existence d’un démantèlement particulier des sommets du graphe ; un démantèlement consistant à retirer un à un les sommets du graphe suivant une certaine règle. Cette caractérisation par démantèlement est par ailleurs intéressante puisqu’elle donne directement un algorithme polynomial de type diminuer pour régner pour résoudre le problème du policier et du voleur. Dans ce mémoire, nous proposons une nouvelle version d’un jeu policier-voleur dans laquelle le voleur se déplace arbitrairement vite dans le graphe et dans laquelle le policier possède une zone de surveillance qui limite le voleur dans ses déplacements. Nous caractérisons les graphes gagnants pour le policier dans ce nouveau jeu en utilisant un concept de démantèlement d’un graphe, similaire à celui de Nowakowski et Winkler [28], Quilliot [45], mais adapté aux conditions de notre nouveau jeu. Nous devons notamment généraliser la définition d’un graphe classique à celle d’un graphe clandestin, qui possède un ensemble de sommets clairs et un ensemble de sommets sombres, afin d’obtenir notre caractérisation par démantèlement. Nous donnons par ailleurs un algorithme qui permet de bâtir une stratégie monotone gagnante pour le policier en nous assurant que le policier sécurise de plus en plus de sommets à chaque tour.
Graph searching problems can be expressed as a game where a group of searchers is trying to capture a group of fugitives on a graph. When players move alternately in such a game, we are then referring to games of Cops and Robbers. Nowakowski and Winkler [28], and independently Quilliot [45], introduced the very first version of cops and robbers games in which a single cop tries to capture a single robber, both players moving alternately from their current positions to neighboring vertices. They notably proposed a very nice characterization of graphs that are winning for the cop, which is based on a particular dismantling scheme of the graph’s vertices; a dismantling scheme consisting in removing one by one each vertex of the graph by following a given rule. This dismantling-like characterization is furthermore interesting since it directly yields a divide-and-conquer algorithm that is polynomial, to solve the cop and robber problem. In this master thesis, we propose a new version of cops and robbers games in which the robber is able to move arbitrarily fast in the graph and in which the cop has a watching area that limits the robber’s moving capabilities. We characterize the cop-winning graphs for this new game by using some dismantling scheme similar to the one given by Nowakowski and Winkler [28], Quilliot [45], but that better fits our new game’s conditions. To obtain this dismantling-like characterization, we particularly need to generalize the definition of a classical graph to an undergrounded graph, whose vertices are split in a set of light vertices and a set of dark vertices. We also give an algorithm that provides a monotonous cop-winning strategy by making sure the cop is securing more and more vertices at each turn.

Nous considérons des graphes orientés pondérés dont l’énergie est paramétrée. Nous proposons dans un premier temps un algorithme qui, étant donné un graphe et un de ses sommets, renvoie des arbres, chaque arbre représentant les plus courtschemins depuis la source vers tous les autres sommets du graphe pour une zone particulière de l’espace des paramètres. De plus l’union de ces zones couvre l’espace des paramètres. Nous considérons ensuite l’accessibilité dans les graphes à énergie multidimensionnelle, avec un type de contraintes plus absolues qui imposent que l’énergie reste entre des bornes. Nous montrons la décidabilité et la complexité du problème quel que soit le nombre de paramètres et de dimensions lorsque les paramètres prennent des valeurs entières. Nous montrons également l’indécidabilité de ce problème avec au moins un paramètre lorsque la dimension est supérieure ou égale à deux. Nous étudions enfin des jeux de parité à un et deux joueurs sur les graphes paramétrés dont l’objectif est la conjonction d’une condition qualitative sur la parité et d’une condition quantitative : l’énergiedoit rester positive. Nous montrons la décidabilité et prouvons des bornes de la complexité du problème de la recherche d’une stratégie gagnante dans les cas à un et à deux joueurs
We are considering weighted oriented graphs with parametrized energy. Firstly we propose an algorithm that, given a graph and one of its vertices, returns trees, every tree representing shortest-paths from the source to every other vertex for a particular zone of the parameter space. Moreover, union of these zones is a covering of the parameter space. Then we consider reachability in graphs with multi-dimensional energy, with stricter constraints that enforce the energy to stay between bounds. We prove decidabilty and complexity of this problem regardless of the dimension and the number of parameters when parameters take integer values. We alsoprove the undecidability of this problem when there is at least one parameter and the dimension is at least two. Finally we study paritygames on parametrized graphs with one and two players whose objective is the conjunction of a qualitative condition on the parity andquantitative one : energy must stay positive. We show the decidability and prove bounds on the complexity of the problem of searchinga winning strategy in both cases with one and two players

Depuis une dizaine d'années, l'étude des réseaux est une branche très active de la recherche en économie. Il est désormais largement admis que ceux-ci jouent un rôle central dans la transmission décentralisée des informations entre les individus. Les informations communiquées par ces derniers concernent aussi bien les opportunités d'emplois que l'état du marché dans lequel une équipe de travailleurs évolue. Cette thèse propose une nouvelle approche du lien entre la manière dont les agents transmettent stratégiquement leurs informations privées et la structure du réseau dont ils font partie. La théorie des jeux non coopérative a été appliquée à l'étude des réseaux sociaux et économiques dans les deux branches suivantes: d'une part, les Jeux en Réseaux considèrent que les joueurs sont les membres d'un réseau donné et analysent la manière dont les comportements stratégiques et les résultats économiques sont influencés par l'architecture de ce réseau ; d'autre part, les Jeux de Formation de Réseaux modélisent la construction stratégique des connections entre les individus. Ce travail apporte une contribution µa ces deux domaines de recherche. Dans la première partie de ma thèse, que forme le Chapitre 1 intitulé Centralisation des Informations dans les Réseaux, les joueurs appartiennent à un réseau qui affectent leur manière de transmettre leurs informations. Dans la seconde partie, constituée des Chapitres 2 et 3 et intitulée Réseaux de Communication Stratégique, la structure des liens entre les agents découle de leur communication stratégique.

Cette thèse présente un modèle de traitement parallèle pour la mise en œuvre d'algorithmes de raisonnement dans le cadre d'un système temps-réel intelligent, et s'inscrit dans l'étude SATURNE menée au CERT-ONERA. Ce projet se fonde sur l'hypothèse que les tâches de traitement ont la capacité de s'adapter aux échéances temporelles. Pour satisfaire ce modèle, les solutions proposées sont la réduction de l'espace de recherche et l'accélération des traitements grâce au parallélisme. Ces changements devant intervenir durant l'exécution du processus, la gestion du parallélisme devient alors dynamique. Par ailleurs, les arbres de décision représentent une méthode fondamentale pour résoudre de nombreux problèmes d'intelligence artificielle, tels que la théorie des jeux à un joueur, les problèmes d'optimisation, la théorie des jeux à deux joueurs, les graphes Et/Ou et beaucoup d'autres problèmes NP-complets. Aussi, à partir de l'exemple de l'algorithme du minimax sur des arbres de jeux réels, une implémentation est réalisée sur Modulor, une machine à architecture distribuée à base de transputers développée au CERT-ONERA. La méthode de parallélisation se fonde sur une suppression du contrôle entre les processus de recherche, au profit d'un parallélisme spéculatif et du partage complet de l'information réalisé grâce à une mémoire physiquement distribuée mais virtuellement partagée. L’apport de notre approche pour les systèmes temps-réel distribués et tolérants aux fautes est évalué grâce aux résultats expérimentaux obtenus.

Ce manuscrit d'Habilitation à diriger des recherches décrit mes travaux de recherche récents en théorie des graphes et en théorie des jeux combinatoires. Une première partie est consacrée à l'étude de paramètres de graphes en s'intéressant particulièrement aux contraintes structurelles qui permettent d'améliorer les bornes connues. Dans cette partie, nous traitons notamment la paire-domination, la domination indépendante mais aussi les partitions en cographes et les colorations quasi propres. Une deuxième partie traite de la domination de puissance, une forme itérative de la domination au sujet de laquelle nous proposons un début de synthèse des résultats existants. Enfin, une troisème partie parle de jeux. Nous y traitons d'abord le travail réalisé sur quelques conjectures portant sur un jeu de domino, puis au sujet des jeux en version misère. Nous y parlons enfin du jeu de domination, qui est à l'interface entre le paramètre de graphe et le jeu combinatoire.

Dans cette thèse, nous étudions les jeux combinatoires sousdifférentes contraintes. Un jeu combinatoire est un jeu à deux joueurs, sanshasard, avec information complète et fini acyclique. D'abord, nous regardonsles jeux impartiaux en version normale, en particulier les jeux VertexNimet Timber. Puis nous considérons les jeux partisans en version normale, oùnous prouvons des résultats sur les jeux Timbush, Toppling Dominoeset Col. Ensuite, nous examinons ces jeux en version misère, et étudionsles jeux misères modulo l'univers des jeux dicots et modulo l'univers desjeux dead-endings. Enfin, nous parlons du jeu de domination qui, s'il n'estpas combinatoire, peut être étudié en utilisant des outils de théorie des jeuxcombinatoires.

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 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

Nous étudions plusieurs problèmes de coloration dans les graphes, pour certains avec une composante ludique. La coloration à distance 2 d'un graphe est une coloration de ses sommets telle que deux sommets à distance au plus 2 ont des couleurs différentes. Le L(p; q)-étiquetage est une généralisation de ce problème ou les contraintes à distance 1 et 2 sont différentes. Nous donnons des résultats pour ces deux problèmes dans plusieurs classes de graphes peu denses (ayant un faible degré moyen maximum).Le jeu de coloration sur un graphe est un jeu ou deux joueurs, Alice et Bob, colorent tour à tour un des sommets non coloriés d'un graphe, construisant ainsi une coloration propre partielle de plus en plus étendue de ce graphe. Alice tente d'étendre la coloration à l'ensemble du graphe, et Bob tente de l'en empêcher. Nous travaillons sur un invariant de graphe, le degré minmax, dont l'étude permet de déduire des résultats pour le jeu de coloration via l'étude d'un problème structurel, la (1; k)-décomposition d'un graphe, c'est-à-dire la partition de ses arêtes en une forêt et un sous-graphe de degré inférieur ou égal à k.Nous travaillons enfin sur une variante du jeu de coloration nommée jeu de coloration d'incidences, ou Alice et Bob colorient les incidences d'un graphe, pour lequel nous donnons une stratégie efficace pour Alice.Enfin, tout au long de notre mémoire, nous étudions les liens entre la notion de coloration est celle de marquage. Un marquage est un ordre sur les sommets (ou arêtes, ou incidences...) d'un graphe possédant des caractéristiques utiles pour le colorer. Pour nos différents problèmes, nous questionnons l'utilité ou les limites de l'usage de cette notion
We study several problems of graph coloring, some of them with a game component.A 2-distance coloring of a graph is a vertex coloring where two vertices at distanceat most two have different colors. A L(p; q)-labeling is a generalisation of the distance-2coloring where constraints are different at distance 1 and 2. We give results for thesetwo problems in several classes of sparse graphs (with a low maximal average degree).The coloring game on a graph is a game where two players, Alice and Bob, taketurns coloring an uncolored vertex of the graph, constructing together a proper partialcoloring of the graph extending as time moves on. Alice try to extend the coloringto the whole graph, and Bob try to prevent her to win. We study a graph invariant,the minmax degree, who has consequences on the coloring game through the notion of(1; k)-decomposition of a graph, which is the partition of its edge set into a forest and asubgraph of degree bounded by k.We finally study a variant of the coloring game named incidence coloring game, whereAlice and Bob are coloring the incidences of a graph, and for which we give an efficientstrategy for Alice.Finally, during our thesis, we study the connections between coloring and marking,which is an order on the vertices of a graph (or its edges, or its incidences) havingproperties usefull for its coloring. For our problems, we try to determine the utility andthe limits of a marking-based approach of coloring problems

Dans cette thèse, les jeux à 2 joueurs dans les graphes et leurs aspects algorithmiques et structurels sont étudiés. Nous explorons tout d'abord le jeu de domination éternelle ainsi que sa généralisation, le jeu de l'espion, deux jeux qui reposent sur les ensembles dominants dynamiques. Dans ces deux jeux, une équipe de gardes poursuit un attaquant ou espion rapide dans un graphe, avec l'objectif de rester près de lui éternellement. Le but est de calculer le nombre de domination éternelle (nombre de gardes pour le jeu de l'espion) qui est le nombre minimum de gardes nécessaires pour réaliser l'objectif. La dimension métrique des digraphes et une version séquentielle de la dimension métrique des graphes sont aussi étudiées. Ces deux problèmes ont pour objectif de trouver un sous-ensemble de sommets de taille minimum tel que tous les sommets du graphe sont identifiés uniquement par leurs distances aux sommets du sous-ensemble. En particulier, dans ce dernier problème, on peut "interroger" un certain nombre de sommets par tour. Les sommets interrogés retournent leurs distances à une cible cachée. Le but est de minimiser le nombre de tours nécessaires pour localiser la cible. Ces jeux et problèmes sont étudiés pour des classes de graphe particulières et leurs complexités temporelles sont aussi étudiées. Précisément, dans le Chapitre 3, il est démontré que le jeu de l'espion est NP-difficile et les nombres de gardes des chemins et des cycles sont présentés. Ensuite, des résultats sur le jeu de l'espion dans les arbres et les grilles sont présentés. Notamment, nous démontrons une équivalence entre la variante fractionnaire et la variante "intégrale" du jeu de l'espion dans les arbres qui nous a permis d'utiliser la programmation linéaire pour concevoir ce que nous pensons être le premier algorithme exact qui utilise la variante fractionnaire d'un jeu pour résoudre sa variante "intégrale". Dans le Chapitre 4, des bornes asymptotiques sur le nombre de domination éternelle de la grille du roi sont présentées. Dans le Chapitre 5, des résultats sur la NP-complétude du jeu de Localisation sous différentes conditions (et une variante de ce jeu) sont présentés. Notamment, nous démontrons que le problème est NP-complet dans les arbres. Malgré cela, nous concevons un (+1)-algorithme d'approximation qui résout le problème en temps polynomial. Autant que nous sachions, il n'existe pas d'autres telles approximations pour les jeux dans les graphes. Finalement, dans le Chapitre 6, des résultats sur la dimension métrique des graphes orientés sont présentés. En particulier, les orientations qui maximisent la dimension métrique sont explorées pour les graphes de degré borné, les tores et les grilles
In this thesis, 2-player games on graphs and their algorithmic and structural aspects are studied. First, we investigate two dynamic dominating set games: the eternal domination game and its generalization, the spy game. In these two games, a team of guards pursue a fast attacker or spy in a graph with the objective of staying close to him eternally and one wants to calculate the eternal domination number (guard number in the spy game) which is the minimum number of guards needed to do this. Secondly, the metric dimension of digraphs and a sequential version of the metric dimension of graphs are then studied. These two problems are those of finding a minimum subset of vertices that uniquely identify all the vertices of the graph by their distances from the vertices in the subset. In particular, in the latter, one can probe a certain number of vertices per turn which return their distances to a hidden target and the goal is to minimize the number of turns in order to ensure locating the target. These games and problems are studied in particular graph classes and their computational complexities are also studied. Precisely, in Chapter 3, the NP-hardness of the spy game and the guard numbers of paths and cycles are first presented. Then, results for the spy game on trees and grids are presented. Notably, we show an equivalence between the fractional variant and the "integral" version of the spy game in trees which allowed us to use Linear Programming to come up with what we believe to be the first exact algorithm using the fractional variant of a game to solve the "integral" version. In Chapter 4, asymptotic bounds on the eternal domination number of strong grids are presented. In Chapter 5, results on the NP-completeness of the Localization game under different conditions (and a variant of it) and the game in trees are presented. Notably, we show that the problem is NP-complete in trees, but despite this, we come up with a polynomial-time (+1)-approximation algorithm in trees. We consider such an approximation to be rare as we are not aware of any other such approximation in games on graphs. Lastly, in Chapter 6, results on the metric dimension of oriented graphs are presented. In particular, the orientations which maximize the metric dimension are investigated for graphs of bounded degree, tori, and grids

Dans cette thèse, nous étudions des problématiques de graphes et de jeux combinatoires. Il existe de nombreux liens entre ces deux domaines : ainsi, les jeux sont un bon moyen de modéliser une opposition dans un problème d'optimisation, et dans l'autre sens plusieurs jeux classiques sont définis sur les graphes. Nous allons étudier deux problèmes de graphes et adapter des jeux combinatoires classiques pour y jouer sur des graphes. Dans un premier temps, nous étudions un problème de criticalité. Un graphe qui vérifie une certaine propriété, mais tel qu'une simple modification (ajout ou suppression d'arête ou de sommet) la lui fait perdre est appelé critique pour cette propriété. Nous nous intéressons au problème des graphes critiques pour la propriété ≪ avoir un diamètre égal à 2 ≫, appelés graphes D2C. La conjecture de Murty-Simon donne une borne supérieure sur le nombre d'arêtes d'un graphe D2C en fonction de son nombre de sommets. Or, des recherches récentes laissent supposer que cette borne peut être améliorée pour les graphes D2C non-bipartis. Nous démontrons donc une borne amoindrie pour une sous-famille de graphes D2C. Dans un deuxième temps, nous considérons un problème d'identification, laquelle consiste à assigner une étiquette à toutes les arêtes ou à tous les sommets d'un graphe, cette assignation devant engendrer une étiquette différente pour chaque sommet. Nous définissons une coloration d'arêtes par des ensembles d'entiers induisant une identification des sommets, et démontrons que cette coloration nécessite au plus un nombre logarithmique d'entiers par rapport à l'ordre du graphe pour l'identifier. Ce résultat est mis en comparaison avec d'autres types de colorations identifiantes, qui nécessitent dans le pire des cas un nombre linéaire d'entiers pour identifier tous les sommets. Dans un troisième temps, nous étudions des jeux de suppression de sommets, qui sont des jeux dans lesquels deux joueurs suppriment d'un graphe des sommets en respectant certaines règles prédéfinies, le premier joueur incapable de jouer perdant la partie. Nous proposons un cadre global pour l'étude de nombreux jeux de suppression de sommets dans les graphes, qui inclut plusieurs jeux classiques comme Arc-Kayles et permet une généralisation des jeux de soustraction et des jeux octaux sur les graphes. Dans leur définition classique, ces jeux ont généralement des comportements réguliers : tous les jeux de soustraction finis sont ultimement périodiques et il est conjecture que c'est également le cas des jeux octaux. Nous étudions plus spécifiquement les jeux de soustraction connexes CSG(S), dans lesquels les joueurs peuvent supprimer k sommets induisant un sous-graphe connexe sans déconnecter le graphe si k ∈ S (avec S fini). Nous démontrons que tous ces jeux sont ultimement périodiques, dans le sens ou pour un graphe et un sommet donnés, un chemin attaché à ce sommet peut être réduit à partir d'un certain rang sans modifier la valeur de Grundy du graphe pour le jeu. Nous trouvons également des résultats de périodicité pure, en particulier sur les étoiles subdivisées : pour certains ensembles S, les chemins des étoiles peuvent être réduits à leur longueur modulo une certaine période sans changer l'issue du jeu. Enfin, nous définissons une variante pondérée de Arc-Kayles, appelée Weighted Arc-Kayles (ou WAK), dans laquelle les joueurs doivent sélectionner une arête pour réduire le poids de ses extrémités, les sommets ayant un poids nul étant supprimés du graphe. Nous montrons une réduction entre WAK et Arc-Kayles, puis que les valeurs de Grundy de WAK sont non-bornées, ce qui répond à une question ouverte sur Arc-Kayles. Nous montrons également que les valeurs de Grundy de WAK sont ultimement périodiques lorsque tous les poids du graphe sauf un sont fixes
In this thesis, we study both graphs and combinatorial games. There are several links betweenthose two domains : games are useful for modeling an opponent in optimization problems on graphs,and in the other direction several classical games are played on graphs. We will study two graphproblems and adapt some classical combinatorial games to be played on graphs.In a first chapter, we study a criticality problem. A graph that verifies some property, and suchthat any modification (vertex or edge addition or deletion) breaks the property is called critical forthis property. We focus on the critical graphs for the property "having diameter 2", called D2Cgraphs. The Murty-Simon conjecture gives an upper bound on the number of edges in a D2C graphwith a given number of vertices. However, recent research suggests that this bound can be improvedfor non-bipartite D2C graphs. We show the validity of this approach by proving a smaller upperbound for a subfamily of non-bipartite D2C graphs.In a second chapter, we consider an identification problem. Identification consists in assigningsome data to every edge or vertex of a graph, such that this assignment induces a label to everyvertex with the added condition that two distinct vertices must have a different label. We definean edge-coloring using sets of integers inducing an identification of the vertices, and prove that thiscoloring requires at most a logarithmic number of integers (with respect to the order of the graph)in order to successfully identify the vertices. This result is compared with other identifying colorings,for which the number of colors required to successfully identify the vertices can be linear with respectto the order of the graph.In order to show the link between graphs and games, we adapt a well-known family of games tobe played on graphs. We propose a general framework for the study of many vertex deletion games(which are games in which the players delete vertices from a graph under predefined rules) such asArc-Kayles. This framework is a generalization of subtraction and octal games on graphs. In theirclassical definition, those games exhibit a high regularity : all finite subtraction games are ultimatelyperiodic, and Guy conjectured that this is also true for all finite octal games.We specifically study the connected subtraction games CSG(S) (with S being a finite set). Inthose games, the players can remove k vertices from a graph if and only if they induce a connectedsubgraph, the graph remains connected after their deletion, and k ∈ S. We prove that those gamesare all ultimately periodic, in the sense that for a given graph and vertex, a path attached to thisvertex can be reduced (after a certain preperiod) without changing the Grundy value of the graph forthe game. We also prove pure periodicity results, mostly on subdivided stars : for some sets S, thepaths of a subdivided star can be reduced to their length modulo a certain period without changingthe outcome of the game.Finally, we define a weighted version of Arc-Kayles, called Weighted Arc-Kayles (WAKfor short). In this game, the players select an edge and reduce the weight of its endpoints. Verticeswith weight 0 are removed from the graph. We show a reduction between WAK and Arc-Kayles,then we prove that the Grundy values of WAK are unbounded, which answers an open question onArc-Kayles. We also prove that the Grundy values of WAK are ultimately periodic if we fix allbut one of the weights in the graph

Cette thèse porte sur l'étude des propriétés structurelles de graphes dont la compréhension permet de concevoir des algorithmes efficaces pour résoudre des problèmes d'optimisation. Nous nous intéressons plus particulièrement aux méthodes de décomposition des graphes, aux jeux de poursuites et à la notion de convexité. Le jeu de Processus a été défini comme un modèle de la reconfiguration de routage. Souvent, ces jeux où une équipe de chercheurs doit effacer un graphe non orienté sont reliés aux décompositions de graphes. Dans les digraphes, nous montrons que le jeu de Processus est monotone et nous définissons une nouvelle décomposition de graphes que lui est équivalente. Ensuite, nous étudions d'autres décompositions de graphes. Nous proposons un algorithme FPT-unifiée pour calculer plusieurs paramètres de largeur de graphes. En particulier, ceci est le premier FPT-algorithme pour la largeur arborescente q-branché et spéciale d'un graphe. Nous étudions ensuite un autre jeu qui modélise les problèmes de pré-chargement. Nous introduisons la variante en ligne du jeu de surveillance. Nous étudions l'écart entre le jeu de surveillance classique et ses versions connecté et en ligne, en fournissant de nouvelles bornes. Nous définissons ensuite un cadre général pour l'étude des jeux poursuite-évasion. Cette méthode nous permet de donner les premiers résultats d'approximation pour certains de ces jeux. Finalement, nous étudions un autre paramètre lié à la convexité des graphes et à la propagation d'infection dans les réseaux, le nombre enveloppe. Nous fournissons plusieurs résultats de complexité en fonction des structures des graphes et en utilisant des décompositions de graphes.

Les jeux des gendarmes et du voleur dans les graphes traitent de la
capture d'un voleur qui se déplace dans un réseau par une équipe de
gendarmes. Ces jeux trouvent leurs motivations en informatique
fondamentale, notamment dans le cadre de la théorie de la complexité
et dans celui de la théorie des mineurs de graphes. Ces jeux ont
également des applications en intelligence artificielle et en
robotique. Quel que soit le contexte, le nombre de gendarmes utilisés
a un coût et doit être minimisé. Dans cette thèse, nous étudions
diverses contraintes auxquelles les stratégies de capture sont
soumises, ainsi que le coût de ces contraintes en terme de nombre de
gendarmes. Nous distinguons principalement trois cadres d'étude.

Dans la première partie de cette thèse, nous définissons une variante
de stratégie de capture qui établit un pont entre la largeur
arborescente et la largeur linéaire des graphes. En particulier, nous
prouvons la monotonie de cette variante générale et donnons un
algorithme exponentiel exact pour calculer de telles stratégies.

Dans la seconde partie de cette thèse, nous nous intéressons aux
stratégies dites connexes qui doivent assurer que la partie propre du
réseau est constamment connexe. Nous prouvons plusieurs bornes
supérieures et inférieures du coût de cette contrainte en terme de
nombre de gendarmes. Nous étudions également la propriété de monotonie
des stratégies de capture connexe.

Dans la troisième partie de cette thèse, nous étudions les stratégies
de capture dans un contexte décentralisé. Nous proposons plusieurs
algorithmes décentralisés qui permettent aux gendarmes de calculer
eux-mêmes la stratégie qu'ils doivent réaliser.

Les jeux des gendarmes et du voleur dans les graphes traitent de la capture d'un voleur qui se déplace dans un réseau par une équipe de gendarmes. Ces jeux trouvent leurs motivations en informatique fondamentale, notamment dans le cadre de la théorie de la complexité et dans celui de la théorie des mineurs de graphes. Ces jeux ont également des applications en intelligence artificielle et en robotique. Quel que soit le contexte, le nombre de gendarmes utilisés a un coût et doit être minimisé. Dans cette thèse, nous étudions diverses contraintes auxquelles les stratégies de capture sont soumises, ainsi que le coût de ces contraintes en terme de nombre de gendarmes. Nous distinguons principalement trois cadres d'étude. Dans la première partie de cette thèse, nous définissons une variante de stratégie de capture qui établit un pont entre la largeur arborescente et la largeur linaire des graphes. En particulier, nous prouvons la monotonie de cette variante générale et donnons un algorithme exponentiel exact pour calculer de telles stratégies. Dans la seconde partie de cette thèse, nous nous intéressons aux stratégies dites connexes qui doivent assurer que la partie propre du réseau est constamment connexe. Nous prouvons plusieurs bornes supérieures et inférieures du coût de cette contrainte en terme de nombre de gendarmes. Nous étudions également la propriété de monotonie des stratégies de capture connexe. Dans la troisième partie de cette thèse, nous étudions les stratégies de capture dans un contexte décentralisé. Nous proposons plusieurs algorithmes décentralisés qui permettent aux gendarmes de calculer eux-mêmes la stratégie qu'ils doivent réaliser
In graph searching problems, a team of searchers is aiming at catching a fugitive running in a network. These problems are motivated by several aspects of theoretical computer science, including computational complexity and minor graph theory. They have also numerous practical applications in artificial intelligence and robotics. In all these contexts, the number of searchers implied in the capture of the fugitive has a cost and must be minimized. In this thesis, we study several constraints of search strategie and their cost in terms of number of searchers. The thesis is divided in three parts. In the first part of the thesis, we introduce a new variant of search strategy that establishs a link between the treewidth and the pathwidth of a graph. In particular, we prove that this kind of strategy satisfies the monotonicity property, and we propose a exponential exact algorithm computing such a strategy. In the second part of the thesis, we focus on the so-called connected search strategy that must insure that the clear part of the network remains permanently connected. We prove several upper and lower bounds related to the cost of this constraint in terms of number of searchers. We also study the monotonicity property of the connected search strategies. In the third part of the thesis, we study the search strategy in a decentralized context. We propose several decentralized algorithms allowing searchers to compute by themselves the strategy that must be performed

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

Les jeux de parité sont la représentation combinatoire de la théorie des infimums, suprimum, et du plus petit point fixe et du plus grand point fixe sur les treillis complets. En gros, le formalisme des jeux de parité peut être considéré comme un mu-calcul sur les treillis complets. Les hiérarchies et le pouvoir expressif sont un thème central dans la théorie des points fixes. La première partie de cette thèse est consacrée à l’étude du problème de la hiérarchie des variables sur le mu-calcul des treillis. Des travaux antérieurs sur ce problème dans le cas du mu-calcul propositionnel modal ont dégagé une mesure de complexité des graphes : c’est l’enchevêtrement. Le dernier est la partie combinatoire de la hiérarchie des variables. La deuxième partie de cette thèse est consacrée à l’étude de l’enchevêtrement dans le contexte de la théorie des graphes, indépendamment de son origine dans la théorie des points fixes. Plusieurs résultats seront démontrés dans cette direction, tels que la reconnaissance des graphes d’enchevêtrement borné, la décomposition arborescente de tels graphes, et la fermeture par mineurs.

Dans cette thèse, nous étudions divers modèles de jeux dynamiques. Ceux-ci modélisent des processus de décisions prises par des agents rationnels en interactions stratégiques et dont la situation évolue au cours du temps. Le premier chapitre est consacré aux jeux stochastiques. Dans ces derniers, le jeu courant dépend d’un état de la nature, qui évolue d’une étape à la suivante de manière aléatoire en fonction de l’état courant ainsi que des actions des joueurs, qui observent ces éléments. On étudie des propriétés de communication entre les états, lorsque l’espace d’états est sous la forme d’un produit X ×Y, et que les joueurs contrôlent la dynamique sur leur composante de l’espace d’états. On montre l’existence de stratégies optimales dans tout jeu répété un nombre suffisant d’étapes, c’est-à-dire l’existence de la valeur uniforme, sous hypothèse de communication forte d’un côté. On montre en revanche la non converge de la valeur du jeu escompté, qui implique la non existence de la valeur asymptotique, sous hypothèse de communication faible des deux côtés. Les deux chapitres suivants sont consacrés à des modèles de jeux de recherche-dissimulation. Un chercheur et un dissimulateur agissent sur un espace de recherche. L’objectif du chercheur est typiquement de retrouver le dissimulateur le plus rapidement possible, ou alors de maximiser la probabilité de le trouver en un temps imparti. L’enjeu est alors de calculer la valeur et les stratégies optimales des joueurs en fonction de la géométrie de l’espace de recherche. Dans un jeu de patrouille, un attaquant choisit un temps et un lieu à attaquer, tandis qu’un patrouilleur marche continûment. Lorsque l’attaque survient, le patrouilleur a un certain délai pour repérer l’attaquant. Dans un jeu de recherche-dissimulation stochastique, les joueurs se trouvent sur un graphe. La nouveauté du modèle est qu’en raison de divers évènements, à chaque étape, certaines arêtes peuvent ne pas être disponibles, de sorte que le graphe évolue de façon aléatoire dans le temps. Enfin, le dernier chapitre est consacré à un modèle de jeux répétés à information incomplète dit de contrôle dynamique de l’information. Un conseiller a une connaissance privée de l’état de la nature, qui évolue aléatoirement avec le temps. Chaque jour le conseiller choisit la quantité d’information qu’il dévoile à un investisseur au travers de messages. À son tour, l’investisseur choisit d’investir ou non afin de maximiser son paiement quotidien espéré. En cas d’investissement, le conseiller reçoit une commission fixe de la part de l’investisseur. Son objectif est alors de maximiser la fréquence escomptée de jours où a lieu l’investissement. On s’intéresse à une stratégie de dévoilement d’information particulière du conseiller dite stratégie gloutonne. C’est une stratégie stationnaire ayant la propriété de minimiser la quantité d’information dévoilée sous contrainte de maximiser le paiement courant du conseiller
In this thesis, we study various models of dynamic games. These model decision-making processes taken by rational agents in strategic interactions and whose situation changes over time. The first chapter is devoted to stochastic games. In these, the current game depends on a state of nature, which evolves randomly from one stage to the next depending on the current state as well as the actions of the players, who observe these elements. We study communication properties between states, when the state space is in the form of a product X × Y, and players control the dynamics on their components of the state space. The existence of optimal strategies in any long enough repeated game, i.e., the existence of the uniform value, is proved under the assumption of strong communication on one side. We prove the non-convergence of the value of the discounted game, which implies the non-existence of the asymptotic value, under the assumption of weak communication on both sides. The next two chapters are devoted to models of search games. A searcher and a hider act on a search space. The searcher’s objective is typically to find the hider as quickly as possible, or to maximize the probability of finding him in a given time. The challenge is then to calculate the value and optimal strategies of the players according to the geometry of the search space. In a patrolling game, an attacker chooses a time and place to attack, while a patroller walks continuously. When the attack occurs, the patroller has a fixed amount of time to locate the attacker. In a stochastic search game, players act on a graph. The novelty of the model is that due to various events, at each stage, some edges may not be available, so the graph evolves randomly over time. Finally, the last chapter is devoted to a model of repeated games with incomplete information called dynamic control of information. An advisor has a private knowledge of the state of nature, which changes randomly over time. Every day, the advisor chooses the amount of information he discloses to an investor through messages. In turn, the investor chooses whether or not to invest in order to maximize her daily expected payoff. In the event of an investment, the advisor receives a fixed commission from the investor. His objective is then to maximize the discounted frequency of days on which investment takes place. We are interested in a specific information disclosure strategy of the advisor called the greedy strategy. It is a stationary strategy with the property of minimizing the amount of information disclosed under the constraint of maximizing the advisor’s current payoff

Dans cette thèse nous étudions des équations différentielles stochastiques sur quelques graphes simples dont les solutions sont des flots de noyaux au sens de Le Jan et Raimond. Dans une première partie, nous définissons une extension de l'équation de Tanaka sur un nombre fini de demi-droites orientées et issues de l'origine. Utilisant certaines propriétés de régularité du flot associé au mouvement brownien biaisé, nous donnons une description complète de toutes les solutions. S'appuyant sur une transformation discrète introduite par Csaki et Vincze, nous donnons dans un cas d'orientation particulière (qui couvre déjà l'équation de Tanaka usuelle) une approche discrète à quelques solutions. La dernière partie de ce travail est effectuée avec O. Raimond. Par une méthode de couplage des flots, nous classifions les solutions de l'équation de Tanaka sur le cercle. Nous établissons aussi que ces flots sont coalescents.

Les problemes traites dans cette these sont tres divers, de nature combinatoire et algebrique, et portent sur quatre themes de theorie des graphes developpes chacun dans une partie. La premiere partie, la plus importante, traite essentiellement de l'etude de relations entre plusieurs parametres classiques d'un graphe. Elle porte l'accent en particulier sur les rapports de ces parametres avec les valeurs propres de la matrice d'adjacence du graphe considere. La deuxieme partie, dans le cadre des reseaux d'interconnexion, presente des resultats d'abord sur la diffusion, puis sur la distance moyenne dans ces reseaux. Dans la troisieme partie, apres des rappels sur les graphes de cayley, sont donnes, d'une part des resultats sur la structure de certains graphes circulants, d'autre part sur la decomposition en deux cycles hamiltoniens de graphes de cayley reguliers de degre quatre, connexes, definis sur un groupe abelien fini. La derniere partie porte sur la numerotation gracieuse des graphes et contient trois articles publies sur ce sujet

Cette thèse s'inscrit dans les domaines de la statistique non-paramétrique et de la théorie statistique de l'apprentissage non-supervisé. Son objet est la compréhension et la mise en œuvre de méthodes d'estimation et de décision pour des modèles de graphes aléatoires à espace latent. Ces outils probabilistes rencontrent un succès grandissant pour la modélisation de grands réseaux dans des domaines aussi différents que la biologie, le marketing ou les sciences sociales. Dans un premier temps, nous définissons un indice identifiable de la dimension de l'espace latent puis un estimateur consistant de cet indice. Plus généralement, ces quantités identifiables et interprétables permettent de palier l'absence d'identifiabilité de l'espace latent lui-même. Dans la suite, nous introduisons le problème de `pair-matching'. En partant d'un graphe non-observé, une stratégie choisit de façon séquentielle des paires de nœuds et observe la présence/absence d'arêtes. Son objectif est de découvrir le plus grand nombre possible d'arêtes avec un budget fixé. Pour ce problème de type bandit, nous étudions les regrets optimaux dans un modèle à blocs stochastiques puis dans un graphe aléatoire géométrique. Enfin, nous estimons les positions des nœuds dans l'espace latent, dans le cas particulier où l'espace est un cercle dans le plan euclidien. Pour chacun des trois problèmes, nous obtenons des procédures optimales au sens minimax, ainsi que des procédures efficaces satisfaisant certaines garanties théoriques. Ces algorithmes sont analysés d'un point de vue non-asymptotique en s'appuyant, entre autres, sur des inégalités de concentration
This thesis lies at the intersection of the theories of non-parametric statistics and statistical learning. Its goal is to provide an understanding of statistical problems in latent space random graphs. Latent space models have emerged as useful probabilistic tools for modeling large networks in various fields such as biology, marketing or social sciences. We first define an identifiable index of the dimension of the latent space and then a consistent estimator of this index. More generally, such identifiable and interpretable quantities alleviate the absence of identifiability of the latent space itself. We then introduce the pair-matching problem. From a non-observed graph, a strategy sequentially queries pairs of nodes and observes the presence/absence of edges. Its goal is to discover as many edges as possible with a fixed budget of queries. For this bandit type problem, we study optimal regrets in stochastic block models and random geometric graphs. Finally, we are interested in estimating the positions of the nodes in the latent space, in the particular situation where the space is a circle in the Euclidean plane. For each of the three problems, we obtain procedures that achieve the statistical optimal performance, as well as efficient procedures with theoretical guarantees. These algorithms are analysed from a non-asymptotic viewpoint, relying in particular on concentration inequalities

Le premier volet de cette thèse porte sur l'étude de graphes dont les sommets sont colorés. Nous étudions comment la recherche d'ensembles particuliers de sommets est affectée lorsqu'on ajoute la contrainte qu'ils soient tropicaux, c'est à dire contiennent au moins un sommet de chacune des couleurs.Cette contrainte additionnelle tend à fortement augmenter la complexité des problèmes. Par exemple, la recherche d'un plus petit ensemble dominant tropical, et celle d'une plus petite couverture par sommet tropicale, sont APX-complets même restreints aux chemins. La recherche du plus petit sous-graphe connexe tropical d'un graphe est elle NP-complète, même restreinte aux arbres. Cependant, ajouter un contrainte sur le nombre de couleurs permet souvent de réduire la complexité. Par exemple, sans restrictions sur le type de graphes en entrée, la recherche d'un sous-graphe connexe tropical s'effectue en temps polynomial pourvu que le nombre de couleurs reste logarithmique en la taille du graphe. De plus, nous montrons divers résultats structurels qui lient la taille d'un sous-graphe connexe tropical minimum à des paramètres du graphe tels que le nombre de couleurs, le nombre d'arêtes, le degré minimum, ... Dans le second volet, nous étudions des jeux sur des graphes, appelés jeux de défense, où des attaquants ciblent des sommets et des défenseurs protègent des sous-graphes. On s'intéresse à l'existence d'un équilibre de Nash lorsque les défenseurs protègent des chemins de taille au plus p. Lorsque chaque défenseur protège exactement une arête, nous montron
The first pane of this thesis is on the study of vertex-colored graphs. We look at the tractability of asserting the existence of particular sets of vertices on a graph with the added constraint that the sets must be tropical, i.e. they must contain at least one vertex of each of the colors in the graph.This additional constraint tends to make the problems way less tractable. For instance, finding a minimum tropical dominating set, or a minimum tropical vertex cover, are APX-complete problems even when restricted to paths. Finding the smallest tropical connected subgraph is also NP-complete even when restricted to trees. However, restricting the number of colors will usually make problems more tractable. For instance, finding a connected tropical subgraph (on any graph) can be done in polynomial time as long as the number of colors is logarithmic in the size of the graph. Moreover, we show some structural results that links the size of a minimum connected subgraph to parameters such as the number of colors, the number of edges, the minimum degree…The second pane is on the study of some games on graphs, called defense games, in which multiple attackers target vertices and multiple defenders protect subgraphs.We focus on the existence of a Nash equilibrium when defenders protect paths of size at most p.When each defender protects exactly one edge, we show among other results that the game on a graph G with n defenders and k attackers admits a Nash equilibrium if and only if there exists a dominating set of size at most k in G, which is NP-complete in the general case.Similarly, when each defender protects a path of size at most p, the existence of a Nash equilibrium is linked to the notion of p-independent, i.e. a set of vertices such that every pair of elements of the set is at distance greater than p.Determining the existence of a maximal p-independent of size at most k is NP-complete, but our Min2stablemax algorithm can compute the minimum size of a maximal 2-independent set in a tree

Cette thèse aborde des sujets liés à la théorie des automates, à la logique et à la théorie des jeux. Ces thèmes sont au cœur de l'informatique théorique depuis de nombreuses décennies. Les travaux de recherche dans ces domaines sont motivés entre autres par des questions de modélisation et de vérification de systèmes. La première partie de la thèse considère les automates finis et la logique temporelle sur des ordres linéaires arbitraires. On y donne une procédure (doublement exponentielle en espace) pour décider la satisfaisabilité d'une formule LTL, utilisant une étape de transformation d'une formule logique en un transducteur synchrone. La seconde partie s'intéresse à des jeux de longueur ordinale. On propose un modèle de jeux à deux joueurs sur des graphes finis, et on montre que la question du vainqueur pour ces jeux peut être résolue en espace polynomial. De plus, on montre qu'il existe des stratégies gagnantes à mémoire finie.

Un jeu stratégique de marché (JSM) est une modélisation des échanges qui se caractérise par une institution monétaire et une règle de formation des prix. Notre objectif est de montrer la pertinence de cette approche dans l'étude de la monnaie et dans l'analyse de la concurrence imparfaite. Les jeux stratégiques de marche se situent à l'articulation de la théorie de la monnaie, de la théorie de la concurrence imparfaite et de la recherche des fondements non coopératifs de l'équilibre concurrentiel. Le premier chapitre est une revue de la littérature et permet de présenter les différents modèles de jeux stratégiques de marché. Nous précisons les relations entre l'institution monétaire et les propriétés de l'équilibre. Nous situons l'équilibre d'un JSM dans l'univers de la concurrence imparfaite en le comparant à l'équilibre de Cournot-Walras. Les chapitres 2 et 3 considèrent l'extension de l'étude des JSM à une économie dynamique. La difficulté essentielle provient de la nature de l'instrument monétaire nécessaire aux relations intertemporelles. Le modèle à générations imbriquées présente alors un terrain d'étude adéquat dans la mesure où il est possible de séparer les relations intra-générationnelles des relations inter-générationnelles. Nous traitons d'abord des problèmes conceptuels dans une économie simple avec un bien et une monnaie-signal. Nous poursuivons l'étude en considérant une économie avec plusieurs biens et un bien-monnaie. Ce cadre nous permet d'analyser les relations entre l'équilibre de concurrence imparfaite et l'équilibre concurrentiel. L'objet du chapitre 4 est la concurrence imparfaite. L'utilisation de la règle de formation des prix des JSM permet l'étude de l'arbitrage prix-quantité dans une économie avec stocks et demande aléatoire. Nous mettons en évidence une motivation stratégique à la détention de stocks qui est une originalité par rapport à la littérature sur les stocks.

Cette thèse se concentre sur les propriétés de routages ou navigations sur les graphes aléatoires associés à des processus ponctuels et la théorie des fonctionnelles ponctuelles et des mesures de Palm. Les deux premiers chapitres se concentrent sur des définitions et des résultats préliminaires. Dans le chapitre 3, nous analysons des navigations sur une nouvelle classe de graphes aléatoires SINR. Nous considérons à la fois une dimension spatiale et une dimension temporelle. Nous étudions les chemins optimaux dans ces graphes. Le principal résultat négatif est que cette constante de temps est infinie sur le graphe aléatoire associé à un processus de Poisson sous des hypothèses naturelles sur les caractéristiques des canaux sans fil. Le principal résultat positif est que l'ajout d'une infrastructure de noeud périodique de densité arbitrairement petite rend la constante de temps positive et finie. Dans la deuxième partie, nous développons un cadre pour l'étude des mesures laissées invariantes par des fonctionnelles ponctuelles. Nous introduisons la notion mesure de Palm de fonctionnelle ponctuelle du processus ponctuel Φ, qui satisfait, quand elle existe, la propriété d'invariance désirée. Le dernier chapitre généralise la notion de mesures Palm de fonctionnelle ponctuelle au cas de fonctionnelles stochastiques et de fonctionnelles dépendant du temps. Les chemins optimaux du graphe SINR spatio-temporel ne sont pas calculables. Les algorithmes de routage de la littérature sont donc fondés sur de algorithme locaux. Les mesures de Palm associées à ces fonctionnelles décrivent donc le paysage ponctuel "vu" par une navigation en temps long sur le processus ponctuel
The two first chapters are focused on preliminaries. In Chapter 3 of this thesis, we analyze a class of “Signal to Interference and Noise Ratio” (SINR) random graphs. These random graphs arise in the modeling of packet transmissions in wireless networks. In contrast to previous studies on SINR graphs, we consider both a space and a time dimension. We study optimal paths in such wireless networks in terms of first passage percolation on this random graph. We establish both positive and negative results on the associated time constant. The main negative result states that this time constant is infinite on the random graph associated with a Poisson point process under natural assumptions on the wireless channels. The main positive result states that when adding a periodic node infrastructure of arbitrarily small intensity to the Poisson point process, the time constant is positive and finite. In the second part, we develop a framework for studying point-map invariant measures. We focus on the case of a not necessarily bijective point-map f. We introduce the notion of Point-map Palm version of the point process Φ, which satisfies the desired invariance property when it exists and we give sufficient conditions for it to exist. Chapter 5, explains the connection between Chapters 3 and 4. It generalizes the notion of point-map Palm measures for stochastic point-maps and time dependent point-maps. As we will see in the end of the Chapter 3, the optimal path in the time- space SINR graph is not computable locally in time. This fact leads us to considering suboptimal local algorithms

Ce travail porte sur l'étude des relations entre la microstructure et paramètres d'élaboration des rubans de l'alliage binaire Al-8% Fe. Les paramètres étudiés sont entre autres : - pression d'éjection et vitesse du substrat, -nature et rugosité du substrat,- température d'éjection. La microstructure des rubans élaborés en jet libre est classée en trois familles : structure de solidification micro-cellulaire, dendritique et équiaxe contenant des précipités. Nous montrons qu'il est possible d'éviter la formation de la structure dendritique grossière correspondant aux conditions de refroidissement les plus lentes : toutefois, les caractéristiques morphologiques des rubans ainsi qu'un bon contact thermique entre celui-ci et le substrat sont à rechercher. Nous en déduisons que la mouillabilité de l'alliage liquide sur le substrat est le critère le plus important et l'influence des paramètres d'élaboration est discuté en termes de distance de collage des rubans sur le substrat. L'élaboration de rubans en jet confiné est également étudiée et leur microstructure est comparée à celle de leurs homologues élaborés en jet libre
This work describes the dependence of microstructural features on rapid solidification processing for the melt spun Al-8% Fe alloy. The inspected parameters are: - ejection pressure and substrate velocity, - nature and rugosity of susbtrate, - ejection temperature. The resultant microstructures of the chill block melt spun ribbons is classified into three families: micro-cellular and dendritic structures, and equiaxed grains containing precipitates. It is possible to avoid the occurrence of the coarse dendritic structure corresponding to the slowest cooling conditions however, uniformity of the ribbon morphologic characteristics and good thermal contact between the ribbon and the weel have to be insured. So, improvement of wetting is the major point. The influence of process parameters on wetting is discussed and particular attention is paid to the sticking distance between the ribbon and the substrate. The planar flow casting method has been developed and microstructural results are compared to those given by the C. B. M. S. Technique

Deux notions de réseaux d'automates apparaissent souvent dans la littérature. Les automates cellulaires, automates finis placés sur les sommets de z, z#2,, z#n, et qui communiquent suivant les directions principales de l'espace. La seconde notion est celle de graphe d'automates ou, aux sommets d'un graphe quelconque de degré borne, on place des automates finis qui communiquent par les arêtes. La première notion ne fonctionne que sur des graphes très pauvres, la seconde pose le problème suivant : les cellules ne connaissent pas l'allure du graphe autour d'elles. Voila pourquoi nous avons décidé d'étudier les automates cellulaires définis sur des graphes de Cayley qui sont des graphes modulaires régulièrement coloriés par des générateurs d'un groupe de présentation finie. Notre thèse comporte trois parties: dans la première, nous généralisons la notion d'automates cellulaires unidirectionnels sur les graphes de Cayley. Nous donnons des résultats sur la vitesse de simulation d'un automate cellulaire par un automate cellulaire unidirectionnel dans le cas de graphes usuels, en particulier, les graphes hexagonaux et triangulaires. Nous donnons dans le cas général des conditions nécessaires et des conditions suffisantes pour que de telles simulations soient possibles sur des graphes de Cayley quelconques. Dans la seconde partie, nous étudions la notion de simulation d'un réseau d'automates par un autre. Cette notion est relativement difficile à cerner, nous l'étudions pour les automates cellulaires définis sur les graphes de Cayley correspondants aux pavages archimédiens. Cela nous amène à montrer que tous ces graphes sont équivalents à la grille dans le plan. Nous donnons aussi des conditions suffisantes pour l'existence de telles simulations en terme de morphismes à noyau fini et de morphismes presque surjectifs. Nous étudions aussi les cas de structures finies et périodiques comme les tores d'automates généralisés. Dans la dernière partie, nous montrons comment synchroniser des chemins de longueur minimale entre deux points d'un graphe de Cayley. Pour cela, une difficulté algorithmique apparaît, elle est due à l'apparition de culs-de-sac dans le graphe de Cayley, c'est-à-dire de points à distance n de l'origine dont aucun des voisins n'est à distance n + 1

Pour l’apprentissage automatisé de données régulières comme des images ou des signaux sonores, les réseaux convolutifs profonds s’imposent comme le modèle de deep learning le plus performant. En revanche, lorsque les jeux de données sont irréguliers (par example : réseaux de capteurs, de citations, IRMs), ces réseaux ne peuvent pas être utilisés. Dans cette thèse, nous développons une théorie algébrique permettant de définir des convolutions sur des domaines irréguliers, à l’aide d’actions de groupe (ou, plus généralement, de groupoïde) agissant sur les sommets d’un graphe, et possédant des propriétés liées aux arrêtes. A l’aide de ces convolutions, nous proposons des extensions des réseaux convolutifs à des structures de graphes. Nos recherches nous conduisent à proposer une formulation générique de la propagation entre deux couches de neurones que nous appelons la contraction neurale. De cette formule, nous dérivons plusieurs nouveaux modèles de réseaux de neurones, applicables sur des domaines irréguliers, et qui font preuve de résultats au même niveau que l’état de l’art voire meilleurs pour certains
Convolutional neural networks have proven to be the deep learning model that performs best on regularly structured datasets like images or sounds. However, they cannot be applied on datasets with an irregular structure (e.g. sensor networks, citation networks, MRIs). In this thesis, we develop an algebraic theory of convolutions on irregular domains. We construct a family of convolutions that are based on group actions (or, more generally, groupoid actions) that acts on the vertex domain and that have properties that depend on the edges. With the help of these convolutions, we propose extensions of convolutional neural netowrks to graph domains. Our researches lead us to propose a generic formulation of the propagation between layers, that we call the neural contraction. From this formulation, we derive many novel neural network models that can be applied on irregular domains. Through benchmarks and experiments, we show that they attain state-of-the-art performances, and beat them in some cases

Dans cette these on s'interesse a la propriete (t) pour les groupes discrets et aux spectres des operateurs associes aux marches aleatoires sur ces groupes. On etudie aussi le rayon spectral de ces operateurs sur certains graphes

Tout d'abord, nous traitons des jeux d'oligopole de Cournot sous forme caractéristique gamma. Nous montrons que ces jeux sont balancés lorsque les fonctions de profit individuel sont concave. Ensuite, lorsque les fonctions de coût individuel sont linéaires, la "valeur au prorata de Nash" appartient au cœur. Par la suite, nous étudions les jeux d'oligopole de Cournot sous forme d'intervalle gamma. Nous prouvons que le cœur intervalle (standard) est non-vide si et seulement si le jeu d'oligopole de Cournot sous forme caractéristique gamma associé à la meilleure (plus faible) capacité qu'obtient chaque coalition admet un cœur non vide. Ensuite, nous analysons les jeux d'oligopole de Stackelberg sous forme caractéristique gamma. Nous montrons que le cœur est égal à l'ensemble des imputations. Ensuite, nous donnons une condition nécessaire et suffisante, qui dépend de l'hétérogénéité des coûts marginaux, assurant la non-vacuité du cœur. Enfin, nous considérons les jeux d'oligopole de Bertrand. Nous prouvons que les jeux sous les formes caractéristiques alpha ou bêta satisfont à la propriété de convexité. Ensuite, nous prouvons que la valeur de partage égalitaire appartient au cœur des jeux sous forme caractéristique gamma et nous donnons une condition suffisante qui assure que ces jeux satisfont à la propriété de convexité. Nous prolongeons cette analyse en supposant que les coûts marginaux sont distincts. Si la constante de la demande est suffisamment petite, alors les jeux sous forme caractéristique bêta satisfont à la propriété de balancement total. Autrement, ces jeux satisfont à la propriété de convexité.

Cette these presente diverses contributions a la theorie des jeux stochastiques et des jeux repetes a information incomplete, a deux joueurs et a somme nulle. On s'interesse a l'existence et a la caracterisation de strategies optimales et des valeurs quand la duree de l'interaction tend vers l'infini. Ces travaux s'inscrivent dans le cadre de la theorie des jeux repetes a information incomplete (aumann-maschler, mertens-zamir), des jeux stochastiques (shapley, kohlberg, bewley-kohlberg, everett, mertens-neyman), et des jeux stochastiques a information incomplete (sorin, sorin-zamir). Ces etudes sont consacrees a la convergence des valeurs des jeux finis et escomptes (quand la duree du jeu tend vers l'infini), et a l'existence de la valeur, du maxmin et du minmax uniforme du jeu infiniment repete. La premiere partie reprend l'etude des jeux a information incomplete finis et l'approche duale introduite par de meyer : cette approche est fondee sur l'etude de la conjuguee de fenchel de la fonction valeur et sur son interpretation comme la valeur d'un jeu, dit jeu dual, dont les strategies optimales sont etroitement liees a celles du jeu initial (collaboration avec b. De meyer). La deuxieme partie est consacree a des preuves d'existence de la limite des valeurs des jeux escomptes par une approche fonctionnelle : il s'agit d'une etude locale de l'operateur de recurrence. On s'inspire de la preuve de kohlberg pour les jeux absorbants, qu'on etend aux jeux a information incomplete des deux cotes et aux jeux absorbants a information incomplete d'un cote. Enfin, la troisieme partie est consacree a differents resultats les jeux infiniment repetes. Elle generalise un resultat de forges sur l'existence de la valeur des jeux a information incomplete symetrique, et contient une preuve d'existence du maxmin des jeux recursifs a information incomplete (travail commun avec n. Vieille).

Cette thèse concerne l'étude des graphes quantiques, c'est à dire, des systèmes quantiques dans lesquels une particule non relativiste est confinée sur un graphe. Nous proposons une nouvelle voie pour représenter des conditions aux limites, et à l'aide de ce résultat nous résolvons le problème, resté longtemps ouvert, d'approximation par des graphes réguliers de tous les couplages singuliers aux sommets dans un graphe quantique. Nous présentons une construction dans laquelle les arêtes sont disjointes et les paires d'extrémités ainsi obtenues sont raccordés par des arêtes additionnelles de longueur 2d. Chacune de ces arêtes porte un potentiel delta et un potentiel vectoriel . Nous montrons que lorsque d tend vers zéro et les potentiels dépendent convenablement de d, la limite peut produire tout couplage singulier de sommets requis. Ce type de conditions aux limites est utilisé pour examiner les propriétés de diffusion par des sommets singuliers de degré 3. Nous montrons que les couplages entre chaque paire de lignes issues du sommet sont réglables individuellement ce qui pourrait permettre la conception de filtre quantique de type "aiguillage spectral". Nous étudions aussi les opérateurs de Schrödinger sur un graphe infini en forme de chaîne composée de cercles identiques couplés aux points de contact par les interactions. delta Si le graphe est périodique, l'hamiltonien a un spectre de bande. Nous considérons une déformation "courbée" de la chaîne qui consiste en un changement de la position du point de contact entre deux cercles. On montre que cette déformation a pour conséquence la naissance de valeurs propres et analyse leur dépendance par rapport à l"angle de courbature".

Le processus de contact est l'un des systèmes de particules en interaction les plus étudiés. Il peut s'interpréter comme un modèlepour la propagation d'un virus dans une population ou sur un réseau. L'objectif de cette thèse est d'étudier la relation entre la structure locale du réseau et le comportement global du processus sur le réseau tout entier.Le cadre typique dans lequel on se place est celui d’une suite de graphes aléatoires $(G_n)$ convergeant localement vers un graphe limite $G$.On étudie alors le comportement asymptotique du temps d’extinction $tau_n$ du processussur $G_n$; lorsqu’initialement tous les individus sont infectés. Nous montrons sur plusieurs exemples qu’il existe unetransition de phase lorsque $lambda$ - le taux d'infection du processus - traverse une valeur critique $ lambda_c (G)$, qui ne dépend que de $G$.Plus précisément, pour certains modèles de graphes aléatoires comme le modèle de configuration, le graphe d'attachement préférentiel, le graphe géométrique aléatoire, le graphe inhomogène, nous montrons que $ tau_n $ est d'ordre soit logarithmique soit exponentiel; selon que $ lambda$ est soit inférieur ou supérieur à $lambda_c (G) $.De plus, dans certains cas, nous montrons des résultats de métastablité: en régime sur-critique, $ tau_n $ divisé par son espérance converge en loi vers une variable aléatoire exponentielle de moyenne $1$, et la densité des sites infectés reste stable (et non nulle) sur une période de temps d’ordre typiquement $tau_n$
The contact process is one of the most studied interacting particle systems and is also often interpreted as a model for the spread of a virus in a population or a network. The aim of this thesis is to study the relationship of the local structure of the network and the global behavior of the contact process (the virus) on the whole network. Let $(G_n)$ be a sequence of random graphs converging weakly to a graph $G$. Then we study $tau_n$, the extinction time of the contact process on $G_n$ starting from full occupancy. We prove in some examples that there is a phase transition of $tau_n$ when $lambda$ - the infection rate of the contact process crosses a critical value $lambda_c(G)$ depending only on $G$. More precisely, for some models of random graphs, such as the configuration model, preferential attachment graph, random geometric graph, inhomogeneous graph, we show that $tau_n$ is of logarithmic (resp. exponential) order when $lambda < lambda_c(G)$ (resp. $lambda < lambda_c(G)$). Moreover, in some cases we also prove metastable results: in the super-critical regime, $tau_n$ divided by its expectation converges in law to an exponential random variable with mean $1$, and the density of the infected sites is stable for a long time

En matiere de graphes, la mise en uvre du precepte diviser pour mieux regner prend souvent la forme d'une decomposition fondee sur une partition de l'ensemble des sommets. Nous presentons une methode de ce genre, la decomposition modulaire deja intensivement etudiee et montrons son utilite dans le cadre de l'etude de classes particulieres de graphes incluant les cographes. La recherche d'analogies avec les cographes ou les split graphes dans le cas des graphes bipartis nous conduit a definir les bicographes ainsi que les graphes bisplit etendus et debouche sur une methode de decomposition generale des graphes bipartis : la decomposition canonique. Les graphes bisplit etendus que nous caracterisons par des configurations exclues sont totalement decomposables par decomposition canonique. Nous proposons un algorithme optimal de reconnaissance de ces graphes. Enfin presentons pour differentes familles des solutions efficaces pour un nombre important de problemes d'optimisation.

Partant de travaux sur la structure des graphes premiers (ou indecomposables), nous presentons dans le cas des graphes non-orientes un algorithme de reconnaissance des graphes premiers (complexite de l'ordre de o(n+m log n)). Nous en deduisons en utilisant les proprietes d'une classe particuliere de graphes (les cographes) un algorithme de decomposition par substitution des graphes non orientes (complexite quadratique). Ce travail est ensuite generalise aux deux cas des graphes orientes et des graphes etiquetes

Cette thèse concerne l'étude des graphes quantiques, c'est à dire, des systèmes quantiques dans lesquels une particule non relativiste est confinée sur un graphe. Nous proposons une nouvelle voie pour représenter des conditions aux limites, et à l'aide de ce résultat nous résolvons le problème, resté longtemps ouvert, d'approximation par des graphes réguliers de tous les couplages singuliers aux sommets dans un graphe quantique. Nous présentons une construction dans laquelle les arêtes sont disjointes et les paires d'extrémités ainsi obtenues sont raccordés par des arêtes additionnelles de longueur 2d. Chacune de ces arêtes porte un potentiel delta et un potentiel vectoriel. Nous montrons que lorsque d tend vers zéro et les potentiels dépendent convenablement de d, la limite peut produire tout couplage singulier de sommets requis. Ce type de conditions aux limites est utilisé pour examiner les propriétés de diffusion par des sommets singuliers de degré 3. Nous montrons que les couplages entre chaque paire de lignes issues du sommet sont réglables individuellement ce qui pourrait permettre la conception de filtre quantique de type "aiguillage spectral". Nous étudions aussi les opérateurs de Schrödinger sur un graphe infini en forme de chaîne composée de cercles identiques couplés aux points de contact par les interactions. Delta Si le graphe est périodique, l'hamiltonien a un spectre de bande. Nous considérons une déformation "courbée" de la chaîne qui consiste en un changement de la position du point de contact entre deux cercles. On montre que cette déformation a pour conséquence la naissance de valeurs propres et analyse leur dépendance par rapport à l"angle de courbature"
This thesis is devoted to investigation of quantum graphs, in other words, quantum systems in which a nonrelativistic particle is confined to a graph. We propose a new way to represent the boundary conditions, and with the help of this result we solve the longstanding open problemof approximating by regular graphs all singular vertex couplings in quantum graph vertices. We present a construction in which the edges are disjunct and the pairs of the so obtained endpoints are joined by additional connecting edges of lengths 2d. Each connecting edge carries a delta potential and a vector potential. It is shown that when the lengths 2d of the connecting edges shrink to zero and the added potentials properly depend on d, the limit can yield any requested singular vertex coupling. This type of boundary conditions is used to examine scattering properties of singular vertices of degrees 2 and 3. We show thar the couplings between each pair of the outgoing edges are individually tunable, which could enable the design of quantum spectral junctions filters. We also study Schrödinger operators on an infinite quantum graph of a chain form which consists of identical rings connected at the touching points by delta-couplings. If the graph is periodic, the Hamiltonian has a band spectrum. We consid a "bending" deformation of the chain consisting in changing the position of the point of contact between two rings. We show that this deformation gives rive to eigenvalues and analyze their dependence on the "bending angle"

Le Web sémantique propose des représentations de connaissances, qui permettent d'intégrer facilement des données hétérogènes issues de plusieurs sources en une base de connaissances unifiée. Dans cette thèse, nous étudions des techniques d'interrogation de telles bases de connaissances.La première partie est dédiée à des techniques de réponse à des requêtes sur une base de connaissances représentée par un graphe RDF sous des contraintes ontologiques. Les connaissances implicites produites par le raisonnement, à partir des règles de déduction RDFS, doivent être prises en compte pour répondre correctement à de telles requêtes.Pour commencer, nous présentons un algorithme de reformulation de requêtes dites Basic Graph Pattern (BGP), qui exploite une partition des règles de déduction en des règles sur les assertions et sur les contraintes. Puis nous introduisons une nouvelle disposition du stockage des graphes RDF, qui combine deux dispositions connues. Pour ces deux contributions, des expérimentations permettent de valider nos résultats théoriques et algorithmiques.Dans la deuxième partie, nous considérons le problème d'interrogation, par des requêtes BGP, de sources de données hétérogènes intégrées en un graphe RDF. Nous introduisons un cadre d'intégration de données sous des contraintes ontologiques RDFS, utilisant une spécification d'intégration basée sur des mappings Global-Local-As-View, rarement considérée jusqu'ici dans la littérature. Nous présentons plusieurs stratégies de réponse à des requêtes, qui, soit matérialisent les données en un graphe RDF, soit laissent ce graphe virtuel. Ces stratégies diffèrent sur quand et comment le raisonnement RDFS est supporté. Nous avons implémenté ces stratégies dans une plate-forme et mené des expérimentations qui démontrent l'intérêt particulier d'une des stratégies basée sur la saturation des mappings. Finalement, nous montrons que cette dernière technique peut être étendue au delà des règles de déduction RDFS au raisonnement défini par un sous-ensemble des règles existentielles
The Semantic Web offers knowledge representations, which allow to integrate heterogeneous data from several sources into a unified knowledge base. In this thesis, we investigate techniques for querying such knowledge bases.The first part is devoted to query answering techniques on a knowledge base, represented by an RDF graph subject to ontological constraints. Implicit information entailed by the reasoning, enabled by the set of RDFS entailment rules, has to be taken into account to correctly answer such queries. First, we present a sound and complete query reformulation algorithm for Basic Graph Pattern queries, which exploits a partition of RDFS entailment rules into assertion and constraint rules. Second, we introduce a novel RDF storage layout, which combines two well-known layouts. For both contributions, our experiments assess our theoretical and algorithmic results.The second part considers the issue of querying heterogeneous data sources integrated into an RDF graph, using BGP queries. Following the Ontology-Based Data Access paradigm, we introduce a framework of data integration under an RDFS ontology, using the Global-Local-As-View mappings, rarely considered in the literature.We present several query answering strategies, which may materialize the integrated RDF graph or leave it virtual, and differ on how and when RDFS reasoning is handled. We implement these strategies in a platform, in order to conduct experiments, which demonstrate the particular interest of one of the strategies based on mapping saturation. Finally, we show that mapping saturation can be extended to reasoning defined by a subset of existential rules

Cette thèse explore des problématiques liées aux jeux. Les jeux qui nous intéressent sont ceux pour lesquels il n'y a pas d'information cachée: tout les joueurs ont accès à toute l'information relative au jeu; il n'y a pas non plus d'aléa. Certains jeux de société (comme les échecs ou le go) satisfont ces propriétés et sont représentatifs des jeux que nous considérons ici. La notion de stratégie est au centre de l'étude de ces jeux. En termes simples, une stratégie est une façon de jouer qui permet de s'assurer un certain résultat. La question centrale, à la fois quand on joue à un jeu et quand on l'étudie, est le problème de trouver la 'meilleure' stratégie, qui assure la victoire du joueur qui l'applique. Dans cette thèse, nous considérons à la fois des jeux à un joueurs, appelés puzzles combinatoires, et des jeux à deux joueurs. Le Rubik's cube, Rush-Hour, et le taquin sont des exemples biens connus de puzzles combinatoires. Récemment, un certain nombre de jeux -- des jeux à un joueur notamment -- ont connu un regain d'intérêt en tant qu'objets d'étude dans un domaine plus grand appelé reconfiguration. Les puzzles que l'on vient de mentionner peuvent tous être décrit de la façon suivante: il y a un ensemble de configurations, qui représente tous les états possibles du jeu; et le joueur est autorisé à transformer une configuration en une autre à via un certain nombre de règles. Le but est d'atteindre une certaine configuration cible à partir d'une configuration initiale. Le domaine de la reconfiguration étend cette définition à des problèmes de recherche: l'ensemble des configurations devient l'ensemble des solutions à une instance d'un problème donné, et l'on se demande si l'on peut transformer une solution donnée en une autre en utilisant uniquement un ensemble de règles de transformation précises. La recherche sur ce type de problèmes a été guidée par des motivations algorithmiques: ce processus peut être vu comme un moyen d'adapter une solution déjà en place en une nouvelle solution à l'aide de petits changements locaux; et des connections avec d'autres problèmes comme la génération aléatoire, ainsi que des problèmes de physique statistique. Les jeux à deux joueurs, qui sont aussi appelés jeux combinatoires, ont été étudiés depuis le début du XXème siècle avec les travaux de Bouton, continués par Berlekamp, Conway et Guy avec le développement d'une théorie unifiant un certain nombre de jeux classiques. Ce travail se focalise sur des joueurs parfaits, c'est à dire qui choisissent toujours le coup optimal. Notre but est de caractériser lequel des deux joueurs possède une stratégie qui lui assure la victoire, quelque soient les coups de son adversaire. Cette approche est au coeur de ce qui est appelé la Théorie des Jeux Combinatoires. Une grande parties des recherche est focalisée sur des 'jeux mathématiques', qui sont des jeux inventés par des mathématiciens, souvent avec des règles très simples, et rarement connus en dehors de la recherche. La motivation principale pour étudier ces jeux est la présence de liens parfois surprenant entre ces jeux et d'autres domaines des mathématiques comme entre autre la théorie des nombres, les automates ou les systèmes dynamiques. Dans cette thèse, nous étudions ainsi des jeux à un et deux joueurs. Nous nous intéressons tout particulièrement à la complexité de ces jeux, c'est à dire évaluer à quel point il est difficile (d'un point de vue algorithmique) de calculer une stratégie gagnante. Nous nous intéressons aussi à leur structure et à certaines propriétés qu'ils peuve satisfaire. Finalement, un des outils principaux dans cette étude est la notion de graphe, et nous utilisons notamment des méthodes et des techniques provenant de théorie des graphes pour résoudre ces problèmes
This thesis explores problems related to games. The games that we consider in this study are games for which there is no hidden information: all the players have access to all the information related to the game; there is also no randomness and everything is deterministic. A few well-known board games (such as chess or go) fall in this category and are representative of the kinds of games that we consider here. Central to the study of these games is the notion of strategy, which roughly speaking, is a way of playing which ensures a certain objective. The main question of interest, when both playing and studying a game, is the problem of finding the 'best' strategy, which secures the victory for the player following it. In this thesis, we consider both one-player games, also called combinatorial puzzles, and two-player games. Examples of combinatorial puzzles include Rubik's cube, Rush-Hour, Sokoban, the 15 puzzle, or peg solitaire. Recently, some types of one-player games in particular have received a strong regain of interest as part of the larger area of reconfiguration problems. The puzzles we described above can all be described in the following way: there is a set of configurations, which represents all the possible states of the game; and the player is allowed to transform a configuration using a prescribed set of moves. Starting from an initial configuration, the goal is to reach a target configuration by a succession of valid moves. Reconfiguration extends this definition to any search problem: the set of configuration becomes the set of solutions to an instance of a given problem, and we ask whether we can transform one given solution to another using only a prescribed set of moves. Hence, in addition to the combinatorial puzzles, reconfiguration problems also include many `games' which are not played by humans anymore but are instead mathematical problems sharing a lot of similarities with combinatorial puzzles. The study of reconfiguration problems has been driven by many different motivations. It has algorithmic applications: it can be seen as a way to adapt a current solution already in place to reach a new one by only making small local changes. It is also connected to other problems such as random sampling, approximate counting or problems coming from statistical physics. It can also be used as a tool for understanding the performance of some heuristic algorithms based on local modifications of solutions such as local search. Two-player games, which are also called combinatorial games, have been studied since the beginning of the twentieth century, with the works of Bouton which were continued with the development of a nice theory by Berlekamp, Conway, and Guy, unifying a certain number of classical games. We focus in this study on perfect strategies (i.e., players always choosing the best possible move), and try to characterize who wins under perfect play for various games. This approach is at the heart of what is called Combinatorial Game Theory. Most of the research in this area is focused on `math games' which are games invented by mathematicians, often with simple rules and almost never played by humans. The main motivation for studying these games comes from the nice, and sometimes unexpected connections these games have with other areas of mathematics, such as for example number theory, automatons, or dynamical systems. In this thesis, we study one- and two-player games. The questions we consider are often related to complexity. Complexity theory consists in trying to classify problems depending on their hardness. By hardness we mean to quantify how much time it would take for a computer to solve the problem. An other aspect of this research consists in investigating structural properties that these games can satisfy. Finally, one of our main tools is the notion of graph, and we use in particular methods and techniques from graph theory to answer the different questions we just mentioned

Le domaine de la théorie des jeux coopératifs s'est enrichi récemment de plusieurs nouveaux types de jeux, essayant de modéliser plus précisément le comportement des joueurs dans une situation réelle. Au sens classique, pour un ensemble N de n joueurs, un jeu coopératif a chaque coalition de joueurs. A un nombre v(A) représentant le résultat (somme d'argent, bénéfice au sens général, etc. ) qu'aura cette coalition si le jeu est joué. Pour un jeu coopératif, un problème central est si tous les joueurs de N d'accords de jouer ensemble. Donc on doit trouver une façon équitable de partager la somme v(N) entre tous les joueurs, une des solutions s'appelle le coeur du jeu. Un jeu coopératif au sens classique est défini sur l'ensemble de toutes le coalitions. Si on impose quelques restrictions sur les coalitions, on peut obtenir un jeu sur une collection de certains sous-ensembles de N, dites coalitions réalisables. On retrouve ainsi bon nombre de cas particuliers (jeux classiques, jeux distributifs, jeux k-réguliers). Cette thèse a essentiellement porté sur des propriétés du cœur des jeux sur des ensembles ordonnés. On considère des jeux multi-choix, jeux bipolaires, jeux distributifs et jeux k-réguliers. Nous avons étudié en particulier la structure géométrique du coeur, ainsi que les conditions nécessaires et suffisantes de non vacuité du coeur. Dans beaucoup de cas, les résultats obtenus ont généralisé de manière naturelle les grands résultats classiques.

Les jeux et paris ont toujours constitué une activité controversée. Attrayante et ludique pour les uns, elle est dangereuse et déviante pour les autres. Ce paradoxe a conduit l’État à encadrer cette activité. Pour cela, il a instauré un système d’autorisations administratives conférant des droits exclusifs aux trois piliers du secteur : le Pari Mutuel Urbain, la Française des Jeux et les casinos. Ce système a contribué à faire de la France un pays monopoliste en matière de jeux. Considérant les jeux et paris comme une activité spécifique, le Gouvernement a fait le choix de limiter les actions en justice qui s’y rapportent par un droit civil restreint et de réprimer sévèrement les infractions instituées par un droit pénal contraignant. Conscient de l’évolution des jeux, notamment par l’émergence d’Internet, et étant confronté à la pression de la Commission européenne, le législateur est intervenu afin de renouveler la matière. Soucieux aussi de mettre un terme à l’illégalité des sites de jeux et de paris pullulant sur Internet, il a ouvert le marché des jeux et paris à la concurrence et ainsi, tranché avec son antique politique des jeux. La loi n°2010-476 du 12 mai 2010 est venue rénover un droit ancien composé de règles inadaptées aux temps modernes. Prenant en compte à la fois les souhaits des joueurs et les intérêts de l’État, cette loi a un double objectif : promouvoir une offre légale diversifiée mais sécurisée et lutter contre l’offre illégale d’opérateurs hors la loi. Si la loi n°2010-476 du 12 mai 2010 relative à l’ouverture à la concurrence et à la régulation du secteur des jeux d’argent et de hasard en ligne semble allier nouveautés et respect des acquis, elle nous donne l’occasion, deux ans après sa mise en application, d’analyser ce secteur aussi bien dans sa situation initiale que dans celle postérieure à cette loi afin d’en relever les apports et d’en critiquer les limites
Gambling has always been a controversial activity. Some consider it fun and attractive other find it devious and dangerous. This activity has been regulated by the Government because of this paradox. Therefore a system based on administrative authorizations was implemented giving exclusive rights to the three main actors of the sector : the ‘Pari mutual urbain’, the ‘Française des Jeux’ and casinos. As a result, the French gambling system is a monopolistic one. Because it is considered as a specific activity, the Government chose to limit legal actions by restricted civil right and to severely condemn infractions by a binding penal right. The recent evolution of gambling, mainly driven by the Internet usage, added to the European commission pressure, forced the legislator to intervene. In order to limit the proliferation of illegal gambling websites, he moved away from its initial politic and opened the gambling market to competition. The n°2010-476 law from the 12 of may 2010 appeared as a renewal of ancient rights whose rules were not adapted to modern times. Taking into consideration both players’ wishes and government’s interest, this law has a double ambition : to promote a secure and diversified market and to fight against illegal market players’ offer. If the law n°2010-476 from the 12 of may, relating to the gambling market opening to competition and its regulation, appears to mix new and past decisions, it is also giving us an opportunity, two yeas after its implementation, to analyze this sector before and after this law in order to appraise its benefits and its limits

La théorie des jeux à champ moyen fut introduite en 2006 par Jean-Michel Lasry et Pierre-Louis Lions. Elle permet l'étude de la théorie des jeux dans certaines configurations où le nombre de joueurs est trop grand pour espérer une résolution pratique. Nous étudions la théorie des jeux à champ moyen sur les graphes en nous appuyant sur les travaux d'Olivier Guéant que nous étendrons à des formes plus générales d'Hilbertien. Nous étudierons aussi les liens qui existent entres les K-moyennes et les jeux à champ moyen ce qui permettra en principe de proposer de nouveaux algorithmes pour les K-moyennes grâce aux techniques de résolution numérique propres aux jeux à champ moyen. Enfin nous étudierons un jeu à champ moyen à savoir le problème "d'heure de début d'une réunion" en l'étendant à des situations où les agents peuvent choisir entre deux réunions. Nous étudierons de manière analytique et numérique l'existence et la multiplicité des solutions de ce problème
The mean field game theory was introduced in 2006 by Jean-Michel Lasry and Pierre-Louis Lions. It allows us to study the game theory in some situations where the number of players is too high to be able to be solved in practice. We will study the mean field game theory on graphs by learning from the studies of Oliver Guéant which we will extend to more generalized forms of Hilbertian. We will also study the links between the K-means and the mean field game theory. In principle, this will offer us new algorithms for solving the K-means thanks to the techniques of numerical resolutions of the mean field games. Findly, we will study a mean field game called the "starting time of a meeting". We will extend it to situations where the players can choose between two meetings. We will study analytically and numerically the existence and multiplicity of the solutions to this problem

Les graphes sont des objets mathématiques abstraits utilisés pour modéliser les interactions entre les éléments constitutifs des systèmes complexes. Cette utilisation est motivée par le fait qu’il existe un lien fondamental entre la structure de ces interactions et les propriétés macroscopiques de ces systèmes. La théorie de la percolation offre un paradigme de choix pour analyser la structure de ces graphes, et ainsi mieux comprendre les conditions dans lesquelles ces propriétés émergent. Les interactions dans une grande variété de systèmes complexes partagent plusieurs propriétés structurelles universelles, et leur incorporation dans un cadre théorique unique demeure l’un des principaux défis de l’étude des systèmes complexes. Exploitant une approche multitype, une idée toute simple mais étonnamment puissante, nous avons unifié l’ensemble des modèles de percolation sur graphes aléatoires connus en un même cadre théorique, ce qui en fait le plus général et le plus réaliste proposé à ce jour. Bien plus qu’une simple compilation, le formalisme que nous proposons augmente significativement la complexité des structures pouvant être reproduites et, de ce fait, ouvre la voie à plusieurs nouvelles avenues de recherche. Nous illustrons cette assertion notamment en utilisant notre modèle pour valider et formaliser certaines intuitions inspirées de résultats empiriques. Dans un premier temps, nous étudions comment la structure en réseau de certains systèmes complexes (ex. réseau de distribution électrique, réseau social) facilite leur surveillance, et par conséquent leur éventuel contrôle. Dans un second temps, nous explorons la possibilité d’utiliser la décomposition en couches “k-core” en tant que structure effective des graphes extraits des systèmes complexes réels. Enfin, nous utilisons notre modèle pour identifier les conditions pour lesquelles une nouvelle stratégie d’immunisation contre des maladies infectieuses est la stratégie optimale.
Graphs are abstract mathematical objects used to model the interactions between the elements of complex systems. Their use is motivated by the fact that there exists a fundamental relationship between the structure of these interactions and the macroscopic properties of these systems. The structure of these graphs is analyzed within the paradigm of percolation theory whose tools and concepts contribute to a better understanding of the conditions for which these emergent properties appear. The underlying interactions of a wide variety of complex systems share many universal structural properties, and including these properties in a unified theoretical framework is one of the main challenges of the science of complex systems. Capitalizing on a multitype approach, a simple yet powerful idea, we have unified the models of percolation on random graphs published to this day in a single framework, hence yielding the most general and realistic framework to date. More than a mere compilation, this framework significantly increases the structural complexity of the graphs that can now be mathematically handled, and, as such, opens the way to many new research opportunities. We illustrate this assertion by using our framework to validate hypotheses hinted at by empirical results. First, we investigate how the network structure of some complex systems (e.g., power grids, social networks) enhances our ability to monitor them, and ultimately to control them. Second, we test the hypothesis that the “k-core” decomposition can act as an effective structure of graphs extracted from real complex systems. Third, we use our framework to identify the conditions for which a new immunization strategy against infectious diseases is optimal.

Dans cette thèse, on s'intéresse à la notion de temps fort de stationnarité et à celle, étroitement liée, de dual de stationnarité forte. Ces outils permettent d'étu- dier la convergence de processus ergodiques, en déterminant un instant aléatoire où l'équilibre est atteint. Les espaces d'état des processus considérés ici sont des graphes continus ou discrets. Dans la première partie, on considère le cas discret, et on dégage une condition nécessaire et suffisante à l'existence, pour n'importe quelle loi initiale, d'un temps fort de stationnarité fini. Pour cela, on construit explicitement un dual de station- narité forte, à valeurs dans l'ensemble des parties connexes du graphe, qui évolue à chaque étape en ajoutant ou en enlevant des points de sa frontière. Lorsque cette opération sépare l'ensemble dual en plusieurs parties, afin de ne pas le déconnecter, une de ces parties est choisie au hasard, avec une probabilité proportionnelle à son poids par la mesure invariante. On s'intéresse également au comportement général d'un processus dual, et on donne quelques exemples différents de celui construit précédemment. Dans la deuxième partie, on traite le cas continu, et le processus étudié est alors une diffusion. On caractérise notamment sa mesure invariante, et on explicite un générateur infinitésimal qui devrait être celui d'un processus dual. Néanmoins, ce cas s'avère plus compliqué que le cas discret. Le processus dual n'est donc construit que pour un mouvement brownien sur un graphe particulier, comme l'unique so- lution d'un problème de martingale. Des pistes sont présentées pour traiter des diffusions sur des graphes plus généraux, notamment en utilisant la convergence d'une suite de processus de saut tels que ceux présentés dans la première partie
In this thesis, we are interested in the notion of strong stationary time, and in that, strongly connected, of strong stationary dual. These tools allow to study the convergence of ergodic processes, by determining a random time when the equilibrium is reached. The state space of the considered processes are discrete or continuous graphs. In the first part, we consider the discrete case, and we explicit a necessary and sufficient condition to the existence, for any initial distribution, of a finite strong stationary time. To do so, we construct explicitly a strong stationary dual, with values in the set of connected subsets of the graph, which evolves at each step by adding or removing some points at its border. Whenever this operation separates the dual set in several parts, in order not to disconnect it, one of these parts is chosen randomly, with a probability proportionnal to its weight relative to the invariant distribution. We also study the general behaviour of any dual process,2 and we give some other examples. In the second part, we deal with the continuous case, and the studied process is then a diffuion. We caracterize its invariant distribution, and we explicit an infinitesimal generator, which is expected to be that of a dual process. Nevertheless, this case turns out to be a little more involved that the discrete one. The dual process is thus constructed only for a brownian motion on a particular graph, as the unique solution of a martingale problem. Some leads are given to solve the case of diffusions on more general graphs, especially by using the convergence of a sequence of jump processes such as those presented in the first part