Les réseaux sont présents dans plusieurs domaines scientifiques et d’ingénierie tels que la biologie, la physique, la sociologie ainsi que la robotique ou la théorie de la communication. L’étude de ces réseaux montre qu’ils sont souvent structurés en sous-groupes. Entre eux il n’y a pas ou il y a très peu d’interaction. Par conséquent, un accord local au sein de chaque groupe est naturellement atteint alors que le consensus associé à un tel réseau doit être imposé par une loi de commande spécifique. Nous proposons donc un contrôleur discret quasi-périodique pour échanger des informations entre les groupes. Un agent de chaque groupe est choisi le « leader » et, à certains moments, ces leaders communiquent entre eux à travers un nouveau réseau. Ceci permet d’obtenir le consensus dans tout le réseau mais engendre des réinitialisation/sauts dans l’état de leaders. La première contribution de la thèse est la caractérisation de la valeur de consensus dans le cadre des systèmes linéaires impulsifs. Il est remarquable que la valeur de consensus dépende seulement des conditions initiales et des topologies des réseaux impliqués. Elle n’est donc pas sensible aux instants de réinitialisation des états de leaders. Afin d’étudier la stabilité de la valeur de consensus obtenue, nous proposons une méthode fondée sur la vérification d’une condition LMI. Cela peut être adaptée pour la conception du réseau d’interaction entre les leaders permettant d’atteindre une valeur de consensus a priori choisie. Il est aussi possible d’utiliser la condition LMI afin de garantir une vitesse de convergence désirée vers le consensus. Pour ces derniers objectifs, la topologie du réseau continue à être considérée comme fixe et connue pour chaque groupe. L’ensemble des valeurs de consensus qui peuvent être atteintes est contenu dans l’intervalle défini par le minimum et le maximum des accords locaux initiaux. Ensuite nous présentons l’étude d’un problème pratique. Des robots mobiles non-holonome, séparés dans des groupes, doivent atteindre une formation donnée. L’algorithme de consensus à pour mission de définir les trajectoires de référence pour ces robots en prenant en compte juste les informations locale. Le robot poursuit la trajectoire de référence en utilisant une commande classique pour cela. / Networks appear in several areas of science and engineering such as biology, physics, sociology as well as robotics and communication theory. Studying these networks it is possible to see cluster-like structures, which are disconnected or very weakly connected one to another. The presence of these clusters hampers consensus throughout the overall network. Instead, local agreement is reached within each cluster. To enforce consensus we have to design an appropriate decentralized controller that imposes interactions between clusters. While the interactions inside each cluster are continuous, we propose a quasi-periodic discrete controller to exchange information between clusters. A single agent from each cluster is chosen to be the leader, and at certain moments, the leaders communicate with each other through a new network. This allows consensus in the entire network but generates resets/jumps on the leaders’ state. The first contribution of this manuscript is related to the characterization of the consensus value in the linear impulsive dynamics framework. It is noteworthy that the consensus value depends only on the initial conditions and the topologies of the involved networks. Therefore, the consensus value does not depend on the reset sequence used for the leaders’ states. To study the stability of the consensus value a LMI based condition is proposed. The main advantage of this approach is its flexibility. Indeed with some modifications to the LMI condition it is possible to analyse the convergence speed of the network or to design the leaders’ network. The purpose of leaders’ network design is to reach an a priori specified consensus value with a specified convergence speed. Whatever is the objective, throughout the manuscript we consider that the network topology is fixed and known for each cluster. The set of consensus values that can be reached is restricted to the interval defined by the minimum and maximum initial local agreements. A last contribution is related to the application of the proposed methodology to a practical situation. We consider a fleet of non-holonomic mobile robots separated in clusters. The communication inside each cluster are secured and cheap while between clusters it is expensive and not securely to communicate. Nevertheless the robots have to reach a given formation. In this case our consensus algorithm is in charge of providing reference trajectories to each robot by using only the available local information. The robot follows the reference by using a classical trajectory tracking control.

Dans cette thèse, nous étudions des problèmes de transversaux d'un point de vue tant algorithmique que combinatoire. Etant donné un hypergraphe, un transversal est un ensemble de sommets qui touche toutes les hyperarêtes. Un packing est un ensemble d'hyperarêtes deux à deux disjointes. Alors que la taille minimale d'un transversal est au moins égale à la taille maximale d'un packing on ne peut pas dans le cas général borner la taille minimale d'un transversal par une fonction du packing maximal. Dans un premier temps, un état de l'art rappelle les différentes conditions qui assurent l'existence de bornes supérieures sur la taille des transversaux, en particulier en fonction de la taille d'un packing. La plupart d'entre elles sont valables lorsque la VC-dimension de Vapnik-Chervonenkis de l'hypergraphe, est bornée. L'originalité de la thèse consiste à utiliser ces outils d'hypergraphes pour obtenir des résultats sur des problèmes de graphes. Nous prouvons notamment une conjecture de coloration de Scott dans le cas des graphes sans-triangle maximaux; ensuite, nous généralisons un résultat de Chepoi, Estellon et Vaxès traitant de domination à grande distance; enfin nous nous attaquons à une conjecture de Yannakakis sur la séparation des cliques et des stables d'un graphe.Dans un second temps, nous étudions les transversaux d'un point de vue algorithmique. On se concentre plus particulièrement sur les problèmes de séparation de graphe où on cherche des transversaux à un ensemble de chemin. En combinant des outils de connexité, les séparateurs importants et le théorème de Dilworth, nous obtenons un algorithme FPT pour le problème Multicut paramétré par la taille de la solution. / In this manuscript we study hitting sets both from a combinatorial and from an algorithmic point of view. A hitting set is a subset of vertices of a hypergraph which intersects all the hyperedges. A packing is a subset of pairwise disjoint hyperedges. In the general case, there is no function linking the minimum size of a hitting set and a maximum size of a packing.The first part of this thesis is devoted to present upper bounds on the size of hitting sets, in particular this upper bounds are expressed in the size of the maximum packing. Most of them are satisfied when the dimension of Vapnik-Chervonenkis of the hypergraph is bounded. The originality of this thesis consists in using these hypergraph tools in order to obtain several results on graph problems. First we prove that a conjecture of Scott holds for maximal triangle-free graphs. Then we generalize a result of Chepoi, Estellon and Vaxès on dominating sets at large distance. We finally study a conjecture of Yannakakis and prove that it holds for several graph subclasses using VC-dimension.The second part of this thesis explores algorithmic aspects of hitting sets. More precisely we focus on parameterized complexity of graph separation problems where we are looking for hitting sets of a set of paths. Combining connectivity tools, important separator technique and Dilworth's theorem, we design an FPT algorithm for the Multicut problem parameterized by the size of the solution.

Convex geometries are combinatorial structures; they capture in an abstract way the essential features of convexity in Euclidean space, graphs or posets for instance. A convex geometry consists of a finite ground set plus a collection of subsets, called the convex sets and satisfying certain axioms. In this work, we study two natural problems on convex geometries. First, we consider the maximum-weight convex set problem. After proving a hardness result for the problem, we study a special family of convex geometries built on split graphs. We show that the convex sets of such a convex geometry relate to poset convex geometries constructed from the split graph. We discuss a few consequences, obtaining a simple polynomial-time algorithm to solve the problem on split graphs. Next, we generalize those results and design the first polynomial-time algorithm for the maximum-weight convex set problem in chordal graphs. Second, we consider the realizability problem. We show that deciding if a given convex geometry (encoded by its copoints) results from a point set in the plane is ER-hard. We complete our text with a brief discussion of potential further work. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

La régionalisation est autant un processus spatial qu'un processus territorial. Elle est spatiale parce qu'elle se réalise sur des structures spatiales héritées tout en les mettant en oeuvre. Nous avons voulu mettre en perspective dans le processus ou les volontés de régionalisation, le système formé des notions de territoires, de villes et de réseaux.<br />Aussi, nous proposons de définir des territoires autour de réseaux de villes qui donnent à penser les régionalisations souhaitables ou souhaitées à partir des propriétés des territoires et de leur organisation par la représentation des interactions spatiales entre les villes. Sont alors créés des réseaux de villes autour desquels la régionalisation des territoires serait possible.<br />Les mises en réseaux de villes se basent sur le corpus conceptuel et théorique du fonctionnement et des propriétés des systèmes de villes, et tiennent compte des caractéristiques du système de villes étudié à travers les critères de la taille des villes et de leur localisation. Ces seuls critères déterminent les espacements entre les villes et leur position dans la hiérarchie de niveaux dans le système, ce qui intègre et révèle les structures spatiales sous-jacentes ou locales.<br />Sont alors définies deux catégories de réseaux de villes :<br />• les réseaux de villes de proximité et de voisinage, sur des contraintes d'espacement entre les villes ;<br />• les réseaux de villes hiérarchisés, sur des contraintes de taille des villes et de principes d'emboîtement de structures hiérarchiques (type administratif, à la hiérarchie stricte, ou type principe de marché, à la hiérarchie non stricte).<br />La formalisation et les représentations des mises en réseaux de villes sont réalisées par la théorie des graphes qui permet une modélisation aisée des organisations hiérarchiques, en particulier des emboîtements de niveaux, par un de ses sous-ensembles, les arbres.<br />La mise en place de ces méthodes et l'évaluation des performances des régionalisations qu'elles engendrent se fait sur deux exemples à problématiques et échelles différentes. La première application montre une approche spatiale en archéologie pour aider à dégager les principales structures d'un système de peuplement d'un territoire autour de la Cité antique de Luteva (Lodève, Hérault, France) durant la période du Haut-Empire (Ier siècle ap. J.-C. - IIIe siècle ap. J.-C.). La seconde application consiste à définir un arc méditerranéen théorique à partir du système de villes européennes sans maillage administratif.

Dans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problèmes de coupes et de multicoupes puis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néanmoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problèmes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP- complétude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynomiaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des topologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits couvrant un ensemble T de sommets donnés. Après avoir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas où la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large.

Cette thèse s'intéresse au probleme de la reconnaissance d'objets en présence d'une vaste base de modèles. L'indexation de modèles peut être décrite comme suit: étant donne un groupe d'indices image, extraire rapidement de la base de modèles, les modèles contenant le groupe d'indices. La combinatoire du paradigme classique d'appariement indices-modèles étant prohibitive dans ce cas, nous proposons une methode d'indexation par une technique de hachage de graphes. Nous décrivons d'abord les principes: codage d'image et des modelés sous une forme de graphes, gestion d'une base de modèles par tables hash-codees, comparaison de graphes sur la base de leur caractérisation polynomiale, accès a la base de modèles. Ensuite, nous décrivons le système mis en œuvre selon ces principes, et nous présentons quelques résultats d'expérimentation

Le travail de thèse présenté dans ce document traite de l'analyse de différentes propriétés liées à l'observabilité des systèmes à entrée inconnue par approche graphique. La simplicité de mise en œuvre de l'approche graphique permet de se défaire des difficultés numériques inhérentes aux approches géométrique et algébrique. Ce constat a conduit ces dernières décennies, à une série d'études structurelles basées sur l'approche graphique. <br />Parmi les propriétés encore non abordées graphiquement, l'observabilité forte traduit l'observabilité des variables d'état d'un système pour toute valeur d'entrée ainsi que l'observabilité conjointe de l'état et de l'entrée. Ces propriétés plus fortes que l'observabilité simple et le diagnostic nous ont paru utiles et pertinentes à étudier. En effet, les outils d'analyse développés peuvent s'avérer importants dans le cadre de la synthèse d'observateurs ou d'estimateurs d'entrées utile à la synthèse de lois de commandes tolérantes aux défauts ou robustes aux perturbations, ou encore quand il s'agit de vérifier si la propriété d'observabilité d'un système n'est pas altérée lorsqu'il est soumis à des perturbations, voire à des défauts d'amplitude trop importante pour être négligés. <br />Le manuscrit est structuré en trois parties. Dans la première, nous avons abordé l'analyse de différentes propriétés d'observabilité. Plus précisément, nous avons tout d'abord donné des conditions nécessaires et suffisantes d'observabilité de l'entrée et de l'état d'un système. Des conditions nécessaires et suffisantes pour l'observabilité forte d'une partie donnée des composantes de l'entrée et de l'état ont ensuite été établies. Le dernier résultat de cette partie concerne l'observabilité forte de tout l'état d'un système à entrée inconnue. Des conditions nécessaires et suffisantes ont été démontrées. <br />La seconde partie de cette thèse a consisté à étudier le problème du placement des capteurs afin de recouvrer des propriétés d'observabilité forte lorsque les conditions de la première partie ne sont pas vérifiées. Deux cas ont été traités. Le premier concerne la propriété d'observabilité forte d'une partie donnée de l'état. La stratégie de placement de capteurs consiste alors en une condition nécessaire permettant d'imposer qu'au moins une sortie du système soit sensible à chacune des composantes de l'état devant être fortement observables, puis en un système de relations graphiques, utilisé comme condition suffisante à ce qu'une configuration de capteurs assure l'observabilité forte des composantes de l'état choisies. Le second problème de placement de capteurs a pour objectif de rendre observables toutes les composantes de l'état. Le problème a été traité en trois étapes. Pour chacune d'elles, des conditions nécessaires et suffisantes sur le placement de capteurs ont été trouvées. Le nombre minimal de capteurs nécessaire et suffisant a aussi été déterminé. Les conditions trouvées sont fondées essentiellement sur des algorithmes classiques de la théorie des graphes.<br />La troisième partie traite de l'implémentation des résultats établis dans une boîte à outils dédiée à l'analyse structurelle (lisa) des systèmes linéaires et bilinéaires structurés. En premier lieu, les motivations qui ont conduit à la conception de cette boîte à outils sont exposées. La structure de lisa est ensuite présentée. Elle repose entièrement sur des algorithmes de base tels que la détermination des ensembles de successeurs et de prédécesseurs, le calcul des tailles de lien et de couplages maximaux entre deux ensembles de sommets et la caractérisation des ensembles de sommets essentiels dans des liens de taille maximale ou encore des séparateurs d'entrée et de sortie. Tous ces algorithmes ont des ordres de complexité polynomiaux. Nous avons montré comment en associant certains algorithmes de base, nous sommes arrivés à analyser l'observabilité de l'état et de l'entrée et à établir des conditions de détection et de localisation de défauts. Enfin, il est présenté des fonctions pouvant être rajoutées à lisa concernant différentes propriétés structurelles pour en faire un outil d'analyse plus complet.

.

Ce mémoire présente quelques résultats récents sur les codes identifiants. La thèse est structurée en cinq chapitres. Le Chapitre 1 contient les définitions et présente la notion de code identifiant. Dans le Chapitre 2 nous étudions l'aspect algorithmique des codes identifiants. Le Chapitre 3 contient quelques résultats concernant des classes de graphes particulières, à savoir les hypercubes, les grilles, et les cycles. Nous étudions quelques questions extrémales au Chapitre 4. Enfin, le Chapitre 5 présente quelques résultats récents sur les codes identifiants dans les graphes aléatoires. A la fin du document nous résumons les résultats les plus importants que nous avons présentés et nous donnons quelques problèmes ouverts sur le sujet.

On considère la métropolisation comme un ensemble de processus, qui, depuis les années 1980, bouleversent les rapports des sociétés à leurs territoires. En particulier, ces changements ont réinterrogé le rôle du transport comme outil d‟aménagement du territoire. Les réseaux de transport présentent ainsi des aptitudes à structurer les territoires métropolitains, en permettant un fonctionnement des lieux en interaction et une appropriation de la part des individus et des sociétés qui les gèrent et les utilisent. L‟objectif de cette recherche est de construire un outil d‟aide à la décision en aménagement du territoire et politique des transports qui puisse rendre compte du potentiel que les réseaux de transports offrent à la structuration du territoire métropolitain. Dans l‟esprit de proposer une alternative au tout-automobile, le travail se concentre sur les réseaux de transport collectif. Concrètement, une démarche modélisatrice est menée et mobilise les notions d‟accessibilité et de capillarité, qui font l‟objet de mesures chiffrées. Ces indicateurs peuvent informer les décideurs sur les qualités des réseaux de transport étudiés. L‟application est menée sur les réseaux de transport collectifs des régions Nord-Pas-de-Calais et Provence-Alpes-Côte d‟Azur. Les analyses mettent en relief certains dysfonctionnements, c‟est pour y remédier que des projets d‟aménagement en matière de transport ont été simulés dans chacune des régions. Les résultats montrent comment les réseaux de transport collectif peuvent favoriser une construction métropolitaine, mais aussi leurs limites. En effet, la thèse plaide pour une conception coordonnée des politiques de transport et d‟aménagement.