On établit la dimension de l'enveloppe convexe des couplages maximums d'un graphe, avec un résultat sur le cas des couplages parfaits. On étudie le squelette des polytopes. On démontre que si chaque sommet du polytope peut être représenté par un vecteur à valeurs 0 ou 1 alors ce squelette est soit un hypercube soit Hamilton connexe. On considère le polyèdre associé au problème du voyageur de commerce. Une méthode de décomposition permet de décrire entièrement ce polyèdre dans un cas particulier. Pour une version dite graphique de ce problème, on donne un ensemble d'inéquations nécessaires a la description du polyèdre associé.

L’analyse de tolérances par des ensembles de contraintes repose sur la détermination de l’accumulation de variations géométriques par des sommes et intersections d’ensembles opérandes 6d. Les degrés de liberté des liaisons et les degrés d’invariance des surfaces génèrent des opérandes non-bornés (polyèdres), posant des problèmes de simulation. En 2014, L. Homria proposé une méthode pour résoudre ce problème, consistant à ajouter des limites artificielles(contraintes bouchon) sur les déplacements non-bornés. Même si cette méthode permet la manipulation d’objets bornés (polytopes), les contraintes bouchon augmentent la complexité des simulations. En réponse à cette difficulté, une méthode dérivée est proposée dans cette thèse.Cette méthode consiste à tracer et simplifier les contraintes bouchon au travers des opérations.Puis une seconde stratégie basée sur la décomposition d’un polyèdre en une somme d’un polytope et de lignes droites (associées aux déplacements non-bornés). Cette stratégie consiste à simuler d’une part les sommes de droites, et d’autre part, à déterminer la somme de polytopes dans un sous-espace de dimension inférieur à 6. Ces trois stratégies sont comparées au travers d’une application industrielle. Cela montre que la traçabilité des contraintes bouchons est un aspect fondamental pour contrôler leur propagation et pour réduire le temps de calcul des simulations. Toutefois, cette méthode exige encore de déterminer les limites des déplacements non-bornés. La deuxième méthode, adaptant systématiquement la dimension de l’espace de calcul, elle permet de diminuer davantage le temps de calcul. Ce travail permet d’envisager la mise en oeuvre de cette méthode selon des formulations statistiques avec la prise en compte des défauts de forme des surfaces. / The cumulative stack-up of geometric variations in mechanical systems can be modelled summing and intersecting sets of constraints. These constraints derive from tolerance zones or from contact restrictions between parts. The degrees of freedom (DOF) of jointsgenerate unbounded sets (i.e. polyhedra) which are difficult to deal with. L. Homri presented in 2014 a solution based on the setting of fictitious limits (called cap constraints) to each DOFto obtain bounded 6D sets (i.e. polytopes). These additional constraints, however, increase the complexity of the models, and therefore, of the computations. In response to this situation,we defined a derived strategy to control the effects of the propagation of the fictitious limits by tracing and simplifying the generated, new cap constraints. We proposed a second strategy based on the decomposition of polyhedra into the sum of a polytope and a set of straight lines.The strategy consists in isolating the straight lines (associated to the DOF) and summing the polytopes in the smallest sub-space. After solving an industrial case, we concluded that tracing caps constraints during the operations allows reducing the models complexity and,consequently, the computational time; however, it still involves working in 6d even in caseswhere this is not necessary. In contrast, the strategy based on the operands decompositionis more efficient due to the dimension reduction. This study allowed us to conclude that the management of mechanisms’ mobility is a crucial aspect in tolerance simulations. The gain on efficiency resulting from the developed strategies opens up the possibility for doing statistical treatment of tolerances and tolerance synthesis.

Dans cette thèse, nous étudions l'enveloppe convexe des arbres binaires à racine sur n feuilles.Ce sont les arbres de Huffman dont les feuilles sont labellisées par n caractères. à chaque arbre de Huffman T de n feuilles, nous associons un point xT , appelé point de Huffman, dans l'espace Qn où xT est le nombre d'arêtes du chemin reliant la feuille du ième caractère et la racine.L'enveloppe convexe des points de Huffman est appelé Huffmanoèdre. Les points extrêmes de ce polyèdre sont obtenus dans un premier temps en utilisant l'algorithme d'optimisation qui est l'algorithme de Huffman. Ensuite, nous décrivons des constructions de voisinages pour un point de Huffman donné. En particulier, une de ces constructions est principalement basée sur la construction des sommets adjacents du Permutoèdre. Puis, nous présentons une description partielle du Huffmanoèdre contenant en particulier une famille d'inégalités définissant des facettes dont les coefficients, une fois triés, forment une suite de Fibonacci. Cette description bien que partielle nous permet d'une part d'expliquer la plupart d'inégalités définissant des facettes du Huffmanoèdre jusqu'à la dimension 8, d'autre part de caractériser les arbres de Huffman les plus profonds, i.e. une caractérisation de tous les facettes ayant au moins un plus profond arbre de Huffman comme point extrême. La contribution principale de ce travail repose essentiellement sur les liens que nous établissons entre la construction des arbres et la génération des facettes / In this thesis, we study the convex hull of full binary trees of n leaves. There are the Huffman trees, the leaves of which are labeled by n characters. To each Huffman tree T of n leaves, we associate a point xT , called Huffman point, in the space Qn where xT i is the lengths of the path from the root node to the leaf node marked by the ith character. The convex hull of the Huffman points is called Huffmanhedron. The extreme points of the Huffmanhedron are first obtained by using the optimization algorithm which is the Huffman algorithm. Then, we describe neighbour constructions given a Huffman point x. In particular, one of these constructions is mainly based on the neighbour construction of the Permutahedron. Thereafter, we present a partial description of the Huffmanhedron particularly containing a family of inequalities-defining facets whose coeficients follows in some way the law of the well-known Fibonacci sequence. This description allows us, on the one hand, to explain the most of inequalities-defining facets of the Huffmanhedron up to the dimension 8, on the other hand, to characterize the Huffman deepest trees, i.e a linear characterization of all the facets containing at least a Huffman deepest tree as its extreme point. The main contribution of this work is essentially base on the link what we establish between the Huffman tree construction and the facet generation.

Le polyèdre associé à un problème d'optimisation combinatoire est l'enveloppe convexe des (vecteurs d'incidence des) solutions réalisables de ce problème. De nombreux problèmes d'optimisation combinatoire se formulent comme une maximisation de fonctions linéaires sur les polyèdres qui leurs sont associés. La description du polyèdre par un système d'inéquations linéaires est intimement liée à la résolution du problème correspondant, par le biais de la programmation linéaire. Afin de déterminer un tel système, une approche classique consiste à décomposer le problème en sous-problèmes tels que les polyèdres associés soient connus ; une composition ultérieure de ces derniers conduit à une description du polyèdre associé au problème considéré. L'objet principal de cette thèse est l'étude de la composition des polyèdres. Dans un premier temps, une approche de composition, basée sur la programmation dynamique et les méthodes de projection polyédrale, est étudiée et des résultats généraux sont proposés, permettant ainsi d'unifier des recherches existantes dans ce domaine. Cette approche est, ensuite, appliquée à la composition de polyèdres associés au problème du voyageur de commerce. En seconde partie, considérant le problème du stable, des opérations sur les graphes (composition par identification de sous-graphes de deux graphes donnés, adjonction d'une nouvelle arête) sont traitées. Des résultats polyédraux sont donc donnés, et des conséquences concernant la perfection et la h-perfection des graphes sont montrés

Cette thèse est centrée sur l'étude des polytopes hyperboliques, des groupes de réflexions et invariants associes. Soit G un groupe de Coxeter, sous-groupe de Isom Hn. Alors, il existe un domaine fondamental P ⊂ Hn qui est naturellement associe 'a ce groupe G. Le domaine P est un polytope de Coxeter. Réciproquement, chaque polytope de Coxeter P engendre un groupe de Coxeter agissant sur Hn: le groupe engendre par les réflexions par rapport a ses facettes. Ces réflexions forment un ensemble naturel de générateurs pour le groupe G. On peut donc exprimer la série de d'accroissement fS (t) du groupe G par rapport a l'ensemble S. Par un resultat de R. Steinberg, la série d'accroissement associée correspond a la série de Taylor d'une fonction rationnelle. Le taux d'accroissement τ de G est l'inverse du rayon de convergence de cette dernière. Le taux de convergence est un entier algébrique et, par un resultat de J. Milnor, τ > 1. Par un résultat de W. Parry, si G agit sur H2 de fa¸con co-compacte, son taux d'accroissement est un nombre de Salem. Par un résultat de W. Floyd, il existe un lien géométrique entre les taux d'accroissement des groupes de Coxeter cocompacts et ceux des groupes a co-volume fini agissant sur H2. Ce lien correspond a une image géométrique de la convergence d'une suite de nombres de Salem vers un nombre de Pisot. Dans cette thèse, on verra un phénomène analogue en dimension 3. En dimension n ≥ 4, le taux d'accroissement d'un groupe de Coxeter agissant de fa¸con cocompacte sur Hn n'est plus un nombre de Salem, ni un nombre de Pisot. Nous nous intéressons a une classe particulière de groupes de Coxeter est celle des groupes de Coxeter rectangulaires. Dans ce cas, les domaines fondamentaux sont des poly- topes aux angles diedres droits. Concernant la classe de polytopes rectangulaires compacts (respectivement, 'a volume fini, id'eaux) dans H4, on pose les problèmes suivants: - déterminer le volume minimal dans ces familles, - déterminer le nombre minimal de composante combinatoire (facettes, faces, arêtes, sommets) dans ces familles. Dans le cas des polytopes rectangulaires a volume fini, la solution a été donnée par E. Vinberg, L. Potyagailo et par B. Everitt, J. Ratcliffe, S. Tschantz. Pour les polytopes rectangulaires compacts, il existe seulement une conjecture. Dans cette these, nous repondons a ces questions dans le cas des polytopes rectangulaires id'eaux.

Etant donné trois entiers k, s et a, nous prouvons dans le premier chapitre qu'il existe un graphe k-régulier fini (resp. un graphe k-régulier connexe fini) dont le groupe d'automorphismes a exactement s orbites sur l'ensemble des sommets et a orbites sur l'ensemble des arêtes si et seulement si<p><p>(s,a)=(1,0) si k=0,<p>(s,a)=(1,1) si k=1,<p>s=a>0 si k=2,<p>0< s <= 2a <= 2ks si k>2.<p><p>(resp.<p>(s,a)=(1,0) si k=0,<p>(s,a)=(1,1) si k=1 ou 2,<p>s-1<=a<=(k-1)s+1 et s,a>0 si k>2.)<p><p>Nous étudions les polyèdres convexes de R³ dans le second chapitre. Pour tout polyèdre convexe P, nous notons Isom(P) l'ensemble des isométries de R³ laissant P invariant. Si G est un sous-groupe de Isom(P), le f_G-vecteur de P est le triple d'entiers (s,a,f) tel que G ait exactement s orbites sur l'ensemble sommets de P, a orbites sur l'ensemble des arêtes de P et f orbites sur l'ensemble des faces de P. Remarquons que (s,a,f) est le f_{id}-vecteur (appelé f-vecteur dans la littérature) d'un polyèdre si ce dernier possède exactement s sommets, a arêtes et f faces. Nous généralisons un théorème de Steinitz décrivant tous les f-vecteurs possibles. Pour tout groupe fini G d'isométries de R³, nous déterminons l'ensemble des triples (s,a,f) pour lesquels il existe un polyèdre convexe ayant (s,a,f) comme f_G-vecteur. Ces résultats nous permettent de caractériser les triples (s,a,f) pour lesquels il existe un polyèdre convexe tel que Isom(P) a s orbites sur l'ensemble des sommets, a orbites sur l'ensemble des arêtes et f orbites sur l'ensemble des faces.<p><p>La structure d'incidence I(P) associée à un polyèdre P consiste en la donnée de l'ensemble des sommets de P, l'ensemble des arêtes de P, l'ensemble des faces de P et de l'inclusion entre ces différents éléments (la notion de distance ne se trouve pas dans I(P)). Nous déterminons également l'ensemble des triples d'entiers (s,a,f) pour lesquels il existe une structure d'incidence I(P) associée à un polyèdre P dont le groupe d'automorphismes a exactement s orbites de sommets, a orbites d'arêtes et f orbites de sommets. / Doctorat en sciences, Spécialisation mathématiques / info:eu-repo/semantics/nonPublished

L'étude des espaces-temps plats singuliers munis d'une surface de Cauchy polyédrale est motivée par leur rôle de model jouet de gravité quantique proposé par Deser, Jackiw et 'T Hooft. Cette thèse porte sur les paramétrisations de certaines classes d'espaces-temps plat singuliers : les espaces-temps plats avec particules massives et BTZ Cauchy-compacts maximaux. Deux paramétrisations sont proposées, l'une reposant sur une extension du théorème de Mess aux espaces-temps plats avec BTZ et la surface de Penner-Epstein, l'autre reposant sur une généralisation du théorème d'Alexandrov aux espaces-temps plats avec particules massives et BTZ. Ce travail propose également une amorce de cadre théorique permettant de considérer des espaces-temps singuliers plus généraux. / The study of singular flat spacetimes with polyhedral Cauchy-surfaces is motivated by the quantum gravity toy model role they play in the seminal work of Deser, Jackiw and 'T Hooft. This thesis study parametrisations of classes of singular flat spacetimes : Cauchy-compact maximal flat spacetimes with massive and BTZ-like singularities. Two parametrisations are constructed. The first is based on an extension of Mess theorem to flat spacetimes with BTZ and Penner-Epstein convex hull construction. The second is based on a generalisation of Alexandrov polyhedron theorem to radiant Cauchy-compact flat spacetimes with massive and BTZ-like singularities. This work also initiate a wider theoretical background that encompass singular spacetimes.