Identification de sommets dans les graphes

The work presented in this document deals with identifying codes in graphs. This notion, introduced in the late 1990's, models fault-detection problems in networks. An identifying code can be seen as a variant of the domination problem, with an additional constraint for identifying the vertices. Finding the minimum cardinality of such a code is an NP-difficult problem. The results presented herein deal with four topics. The first topic is related to regular structures (grids, cycles, hypercubes, products of cliques, Sierpiński graphs), for which some results on the minimum cardinality of a code (bounds and exact values) are presented. Then, algorithmic aspects are developed, one the one hand about polynomial algorithms designed for specific graph classes (trees, fasciagraphs), on the other hand about the approximability of the problem. Some structural questions are then addressed, namely the construction of extremal graphs, the construction of families of graphs admitting a code of small cardinality, and the structure (degrees, induced subgraphs, etc.) of graphs admitting such a code. Finally, a new variant of the problem is presented, that is adaptive identifying codes. This variant enables one to model a situation where we may take advantage of the dynamic aspect of the problem, and hope to query significantly less vertices than in the static case. In particular, we explicit in this document several links that relate identifying codes to other kind of structures, such as dominating sets, superimposed codes, projective planes, or Rényi search games.Les travaux présentés dans ce document traitent des codes identifiants dans les graphes. Cette notion, introduite à la fin des années 1990, modélise des problèmes de détection de défaillance dans les réseaux. Un code identifiant peut être vu comme une variante du problème de domination, avec une contrainte supplémentaire d'identification des sommets. La recherche de la cardinalité minimum d'un tel code est un problème NP-difficile. Les résultats obtenus sont regroupés en quatre grands thèmes. Le premier thème concerne les structures régulières (grilles, cycles, hypercubes, produits de cliques, graphes de Sierpiński), pour lesquels des résultats sur la cardinalité minimum d'un code sont présentés (bornes et valeurs exactes). Ensuite, les aspects algorithmiques sont développés, que ce soit au sujet de la recherche d'algorithmes polynomiaux pour des classes de graphes particulières (arbres, fasciagraphes) ou concernant l'approximabilité du problème. Quelques questions structurelles sont ensuite discutées, notamment la construction de graphes extrémaux pour le problème, la construction de familles de graphes admettant un code identifiant de faible cardinalité, et la structure (degrés, sous-graphes, etc.) des graphes admettant un tel code. Enfin, une nouvelle variante de ces codes est présentée, les codes identifiants adaptatifs. Cette variante permet de modéliser une situation où nous pouvons tirer parti de l'aspect dynamique du problème, et espérer interroger un nombre de sommets bien moins grand que dans le cas statique. Nous explicitons en particulier dans ce document les liens qu'entretiennent les codes identifiants avec d'autres types de structures, tels les ensembles dominants, les codes superposés, les plans projectifs, ou les jeux de Rényi