Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Codes identifiants (théorie des graphes) --- Graph theory --- Codes identifiants (théorie des graphes)

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Les codes identifiants ont été introduits en 1998 par Karpovsky, Charkrabarty et Levitin dans le but de modéliser un problème d’identification de processeurs défectueux dans des réseaux multiprocesseurs. 
Dans ce mémoire, nous nous intéressons au cardinal minimum que doit avoir un code identifiant d’un graphe. Cependant, ce problème est un problème difficile au niveau de la complexité : il n’est pas aisé de déterminer le cardinal minimum d’un code identifiant d’un graphe quelconque. Nous nous intéressons donc à des familles particulières de graphes pour lesquelles nous pouvons donner une valeur pour le cardinal minimum d’un code identifiant d’un graphe en fonction du nombre de sommets du graphe. Dans ce travail, nous avons donc choisi de travailler sur des graphes qui sont en réalité le produit de cliques : nous donnons une valeur, en fonction de la taille de ces cliques, pour le cardinal minimum d’un code identifiant du produit direct de deux cliques ainsi que pour le produit cartésien de cliques de même taille et de tailles différentes.
Enfin, nous concluons ce mémoire par un chapitre présentant les aspects plus généraux des codes identifiants : leurs applications, leur complexité, quelques variantes ainsi que des bornes pour le cardinal minimum d’un code identifiant d’un graphe quelconque. Identifying codes in graphs were introduced in 1998 by Karpovsky, Charkrabarty and Levitin in order to model fault-diagnosis in multiprocessor systems.
In this Master thesis, we are looking for the minimum cardinality of an identifying code of any graph. However, this issue is a difficult problem in terms of complexity: it is not straightforward to determine the minimum cardinality of an identifying code of any graph. We are therefore interested in particular families of graphs for which we can give a value for the minimum cardinality of an identifying code of a graph according to the number of vertices it contains. In the following, we decided to work on graphs that are actually the product of cliques: we give a value, according to the size of these cliques, for the minimum cardinality of an identifying code of the direct product of two cliques as well as for the Cartesian product of cliques of the same size and different sizes.

Finally, we conclude this Master thesis with a chapter presenting the more general aspects of identifying codes: their applications, their complexity, some variants as well as limits for the minimum cardinality of an identifying code of any graph.

Code identifiant --- Théorie des graphes --- Produit direct --- Produit cartésien --- Clique --- Identifying code --- Physique, chimie, mathématiques & sciences de la terre > Mathématiques