1 |
Constructive approaches to the rigidity of frameworks / Constructive approaches to the rigidity of frameworksNguyen, Viet Hang 17 October 2013 (has links)
La théorie de la rigidité étudie l'unicité des réalisations des graphes, i.e., des charpentes. Initialement motivée par l'ingénierie des structures, la théorie de la rigidité trouve aujourd'hui des applications dans plusieurs domaines importants comme la prédiction de la flexibilité des protéines, la conception assistée par ordinateur, la localisation dans les réseaux des capteurs, etc. Cette thèse traite une grande variété de problèmes concernant différents types de rigidité, qui correspondent à différents niveaux d'unicité (locale/infinitésimale, globale et universelle) dans des modèles variés de charpentes. D'abord, nous développons des résultats sur la construction récursive et la décomposition des graphes avec des conditions mixtes de sparsité ainsi que des résultats sur le packing des arborescences avec des contraintes de matroïde. Ces résultats sont alors utilisés pour obtenir des caractérisations de la rigidité infinitésimale des charpentes avec des contraintes mixtes. Nous étudions aussi l'effet des opérations d'extension sur des charpentes et étendons un résultat connu sur la préservation de la rigidité globale d'$1$-extension dans les charpentes à direction et à longueur de la dimension deux aux dimensions supérieures. Pour la rigidité universelle, un sujet que l'on connait très peu, nous obtenons une caractérisation complète pour la classe des charpentes biparties complètes sur la ligne. Nous généralisons aussi une condition suffisante pour la rigidité universelle des charpentes en permettant des positions non générales. / The theory of rigidity studies the uniqueness of realizations of graphs, i.e., frameworks. Originally motivated by structural engineering, rigidity theory nowadays finds applications in many important problems such as predicting protein flexibility, Computer-Aided Design, sensor network localization, etc. The present thesis treats a wide range of problems concerning different kinds of rigidity, corresponding to different scopes of uniqueness (local/infinitesimal, global and universal), in various types of frameworks. First, we develop results in inductive construction and decomposition of graphs with mixed sparsity conditions as well as results on the packing of arborescences with matroidal constraints. These results are then used to obtain characterizations of infinitesimal rigidity in frameworks with mixed constraints. We also investigate the effect of extension operations on frameworks and extend a known result on the global rigidity preservation of $1$-extension on direction-length frameworks in dimension two to all dimensions. For universal rigidity, where little is known, we obtain a complete characterization for the class of complete bipartite frameworks on the line. We also generalize a sufficient condition for the universal rigidity of frameworks by allowing non-general positions.
|
Page generated in 0.1305 seconds