Dans cette thèse, nous étudions des problèmes d'identification des sommets dans les graphes. Identifier les sommets d'un graphe consiste à attribuer à chaque sommet un objet qui rend le sommet unique par rapport aux autres. Nous nous intéressons particulièrement aux codes identifiants : sous-ensembles de sommets d'un graphe, dominants, tels que le voisinage fermé de chaque sommet du graphe a une intersection unique avec l'ensemble. Les sommets du code identifiant peuvent être considérés comme des capteurs et chaque sommet du graphe comme un lieu possible pour une défaillance. Nous caractérisons tout d'abord l'ensemble des graphes pour lesquels tous les sommets sauf un sont nécessaires dans tout code identifiant. Le problème consistant à trouver un code identifiant optimal, c'est-`a-dire de taille minimale, étant NP-difficile, nous l'étudions sur quatre classes restreintes de graphes. Suivant les cas, nous pouvons résoudre complètement le problème (pour les graphes de Sierpinski), améliorer les bornes générales (pour les graphes d'intervalles, les graphes adjoints, la grille du roi) ou montrer que le problème reste difficile même restreint (pour les graphes adjoints). Nous considérons ensuite des variations autour des codes identifiants permettant plus de flexibilité pour les capteurs. Nous étudions par exemple des capteurs du plan capables de détecter des défaillances `a un rayon connu avec une erreur tolérée. Nous donnons des constructions de tels codes et bornons leur taille pour des valeurs de rayons et d'erreurs fixés ou asymptotiques. Nous introduisons enfin la notion de coloration identifiante d'un graphe, permettant d'identifier les sommets d'un graphe avec les couleurs présentes dans son voisinage. Nous comparons cette coloration avec la coloration propre des graphes et donnons des bornes sur le nombre de couleurs nécessaires pour identifier un graphe, pour plusieurs classes de graphes. / In this thesis, we study problems on vertices identification of graphs. To identify the vertices of a graph consists in giving to each vertex of the graph an object that makes it unique. We are specially interested in the problem of identifying codes : dominating sets of vertices for which the closed neighborhood of each vertex has a unique intersection with the set. The vertices of the identifying code can be seen as sensors and each vertex of the graph as the location of a potential fault. We first classify all finite graphs for which all but one of the vertices are needed in any identifying code. Finding an optimal identifying code, i.e, an identifying code of minimum size, is a $NP$-hard problem. Therefore, we study this problem in some restricted classes of graphes. Depending on the class considered, we are able to solve this problem (for Sierpi`nski graphs), to give better bounds on the size of an identifying code than the general one (for interval graphs, line graphs and the king grid) or to prove that the problem remains NP-hard even in the restricted class (for line graphs). Then, we consider some variations of identifing codes that give flexibility to the sensors. For example, we study codes sensors able to detect faults within a radius around a fixed value. We give constructions of such codes and bounds on their size for general and asymptotic values of the radius and the tolerance on it. Finally, we introduce identifying colourings of graphs; verex-colouring of graph such that each vertex is identified by the set of colours in its closed neighbourhood. We compare this colouring of graphs with proper vertex-coloring and give bounds on the number of colours required to identify a graph, for several class of graphs.
| Identifer | oai:union.ndltd.org:theses.fr/2012GRENM028 |
| Date | 05 July 2012 |
| Creators | Parreau, Aline |
| Contributors | Grenoble, Gravier, Sylvain |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0027 seconds