Un fasciagraphe de taille n et de fibre F est constitué de n copies consécutives du graphe F, chaque copie étant reliée à la suivante selon le même schéma. Les rotagraphes sont définis similairement, mais selon une structure circulaire. Dans cette thèse nous caractérisons un ensemble de problèmes combinatoires qui peuvent être résolus de façon efficace dans la classe des fasciagraphes et rotagraphes. Dans ce contexte, nous définissons les (d,q,w)-propriétés closes et stables, et présentons pour de telles propriétés un algorithme pour calculer une solution optimale en temps constant pour l'ensemble des fasciagraphes ou rotagraphes de fibre fixée. Nous montrons que plusieurs problèmes communément étudiés dans la théorie des graphes et NP-complets dans le cas général sont caractérisés par des (d,q,w)-propriétés closes ou stables. Dans une seconde partie de la thèse, nous adaptons cet algorithme générique à trois problèmes spécifiques caractérisés par des (d,q,w)-propriétés stables : le problème du code identifiant minimum, et deux problèmes proches, celui de dominant-localisateur minimum et celui du dominant-total-localisateur minimum. Nous présentons alors une implémentation de l'algorithme qui nous a permis de répondre à des questions ouvertes dans certains rotagraphes particuliers : les bandes circulaires de hauteur bornée. Nous en déduisons d'autres résultats sur les bandes infinies de hauteur bornée. Enfin, nous explorons le problème du code identifiant dans une autre classe de graphes à structure répétitive : les graphes fractals de cycle. / A fasciagraph of length n and of fiber F, is constituted of n consecutive copies of a graph F, each copy being linked to the next one according to a same scheme. Rotagraphs are defines similarily, but along a circular structure. In this thesis, we caracterize a set of combinatorial problems that can be efficiently solved when applied on the class of rotagraphs and fasciagraphs. In this context, we define closed and stable (d,q,w)-properties, and we present, for such properties, an algorithm to compute an optimal solution, in constant time, for the set of fasciagraphs or rotagraphs of fixed fiber. We show that several problems, largely studied in graph theory, are caracterized by closed or stable (d,q,w)-properties. In a second part of the thesis, we adapt the generic algorithm to three problems caracterized by stable (d,q,w)-properties : the problem of minimum indentifying code, and two other, close to this one, the problem of minimum locating-dominating set et the one of minimum locating-total-dominating set. We present an implementation of our algorithm which has let us respond to open questions in a certain sub-class of rotagraphs : the circular strips of bounded height. We deduce from there other results on infinite strips of bounded height. Finaly we explore the problem of minimum identifying code in another class of graphs with repetitive structure : the fractal graphs.
| Identifer | oai:union.ndltd.org:theses.fr/2012GRENM036 |
| Date | 04 July 2012 |
| Creators | Bouznif, Marwane |
| Contributors | Grenoble, Preissmann, Myriam, Moncel, Julien |
| 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.0025 seconds