Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphes.

Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphes. / In this thesis, we define a new class of graphs : the hypochordal graphs. These graphs satisfy that for any path of length two, there exists a chord or another path of length two between its two endpoints. This class can represent robust networks. Indeed, we show that in such graphs, in the case of an edge or a vertex deletion, the distance beween any pair of nonadjacent vertices remains unchanged. Then, we study several properties for this class of graphs. Especially, after introducing a family of specific partitions, we show the relations between some of these partitions and hypochordality. Moreover, thanks to these partitions, we characterise minimum hypochordal graph, that are, among connected hypochordal graphs, those that minimise the number of edges for a given number of vertices. In a second part, we study the complexity, for hypochordal graphs, of problems that are NP-hard in the general case. We first show that the classical problems of hamiltonian cycle, colouring, maximum clique and maximum stable set remain NP-hard for this class of graphs. Then, we analyse graph modification problems : deciding the minimal number of edges to add or delete from a graph, in order to obtain an hypochordal graph. We study the complexity of these problems for sevaral classes of graphs.

Étude sur les graphes bipartis orientes de Moore montrant que de tels graphes existent, pour certaines valeurs du diamètre, et servent a la construction d'une classe de graphes bipartis orientes, asymptotiquement optimaux. Dans la deuxième partie du travail, quelques notions de coloration des graphes sont présentées. Celles-ci permettent de généraliser certains résultats déjà connus dans le cadre de la coloration habituelle et d'en obtenir d'autres plutôt spécifiques a ces notions. La généralisation de la notion de perfection en b-perfection est proposée ce qui permet l'obtention des graphes triangules représentant la seule classe de graphes b-parfaits

Étude de certains problèmes d'optimisation combinatoire. Le premier concerne un problème de régulation de trafic pour lequel on donne une formulation mathématique et on propose une méthode permettant de le résoudre. Le deuxième problème traité est un des problèmes de la physique statistique qui relève de la combinatoire et de l'optimisation, celui du fondamental d'un verre de spins (modèle d'Ising). Enfin on étudie, deux autres problèmes d'optimisation combinatoire: l'absorbant et le Ki-recouvrement de poids minimum

Les travaux présentés dans ce manuscrit s’inscrivent dans le contexte de l’inspection automatisée d’assemblages mécaniques aéronautiques par vision artificielle. Il s’agit de décider si l’assemblage mécanique a été correctement réalisé (assemblage conforme). Les travaux ont été menés dans le cadre de deux projets industriels. Le projet CAAMVis d’une part, dans lequel le capteur d’inspection est constitué d’une double tête stéréoscopique portée par un robot, le projet Lynx© d’autre part, dans lequel le capteur d’inspection est une caméra Pan/Tilt/Zoom (vision monoculaire). Ces deux projets ont pour point commun la volonté d’exploiter au mieux le modèle CAO de l’assemblage (qui fournit l’état de référence souhaité) dans la tâche d’inspection qui est basée sur l’analyse de l’image ou des images 2D fournies par le capteur. La méthode développée consiste à comparer une image 2D acquise par le capteur (désignée par « image réelle ») avec une image 2D synthétique, générée à partir du modèle CAO. Les images réelles et synthétiques sont segmentées puis décomposées en un ensemble de primitives 2D. Ces primitives sont ensuite appariées, en exploitant des concepts de la théorie de graphes, notamment l’utilisation d’un graphe biparti pour s’assurer du respect de la contrainte d’unicité dans le processus d’appariement. Le résultat de l’appariement permet de statuer sur la conformité ou la non-conformité de l’assemblage. L’approche proposée a été validée à la fois sur des données de simulation et sur des données réelles acquises dans le cadre des projets sus-cités. / The work presented in this manuscript deals with automated inspection of aeronautical mechanical parts using computer vision. The goal is to decide whether a mechanical assembly has been assembled correctly i.e. if it is compliant with the specifications. This work was conducted within two industrial projects. On one hand the CAAMVis project, in which the inspection sensor consists of a dual stereoscopic head (stereovision) carried by a robot, on the other hand the Lynx© project, in which the inspection sensor is a single Pan/Tilt/Zoom camera (monocular vision). These two projects share the common objective of exploiting as much as possible the CAD model of the assembly (which provides the desired reference state) in the inspection task which is based on the analysis of the 2D images provided by the sensor. The proposed method consists in comparing a 2D image acquired by the sensor (referred to as "real image") with a synthetic 2D image generated from the CAD model. The real and synthetic images are segmented and then decomposed into a set of 2D primitives. These primitives are then matched by exploiting concepts from the graph theory, namely the use of a bipartite graph to guarantee the respect of the uniqueness constraint required in such a matching process. The matching result allows to decide whether the assembly has been assembled correctly or not. The proposed approach was validated on both simulation data and real data acquired within the above-mentioned projects.

Dans cette thèse, nous étudions trois catégories de problèmes : les d-extensibles, les d-bloqueurs et les d-transversaux.Les d-extensibles de stables optimaux sont des ensembles de sommets d'un graphe G tels que tout stable de cardinal d du sous-graphe induit par un d-extensible peut être étendu à un stable optimal de G à l'aide de sommets qui n'appartiennent pas au d-extensible. Nous étudions les d-extensibles de cardinal maximal de stables dans les graphes bipartis. Nous démontrons quelques propriétés structurelles puis nous déterminons une borne inférieure du cardinal maximal d'un d-extensible. Nous étudions quelques classes de graphes dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial. Nous nous intéressons ensuite aux d-extensibles de stables dans les arbres. Nous prouvons plusieurs propriétés structurelles, déterminons une autre borne inférieure du cardinal maximal d'un d-extensible et étudions quelques classes d'arbres dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial.Les d-bloqueurs de stables sont des ensembles de sommets d'un graphe G tels que, si on retire les sommets d'un d-bloqueur, le cardinal maximal d'un stable du graphe induit par les sommets restants est inférieur d'au moins d au cardinal maximal d'un stable du graphe initial. Nous nous intéressons ici aux d-bloqueurs de coût minimal de stables dans les arbres. Après avoir prouvé une caractérisation des d-bloqueurs de stables dans les arbres, nous démontrons que déterminer un d-bloqueur de coût minimal de stable est un problème polynomial dans une classe d'arbres particulière.Soit Pi un problème d'optimisation sur un ensemble d'éléments fini. Un d-transversal de Pi est un ensembles d'éléments tel que l'intersection entre le d-transversal et toute solution optimale au problème Pi est de cardinal supérieur égal à d. Nous proposons ici une approche de génération de contraintes pour déterminer des d-transversaux de cardinal maximal de problèmes modélisés par des programmes mathématiques en variables binaires. Nous étudions deux variantes de cette approche que nous testons sur des instances de graphes générés aléatoirement pour déterminer des d-transversaux de stables optimaux et des d-transversaux de couplages optimaux / In this thesis, we study three types of problems : the d-extensibles sets, the d-blockers and the d-transversals.In a graph G, a d-extensible set of maximum independent sets is a subset of vertices of G such that every stable set of cardinality d in the subgraph restricted to the d-extensible set can be extented to a maximum stable set of G using only vertices that do not belong to the d-extensible set. We study d-extensible sets of mxaimum cardinality of stable sets in bipartite graphs. We show some structural properties and we determine a lower bound of the maximum cardinality of a d-extensible set. We consider some classes of graph where finding an optimum d-extensible set can be done in polynomial time. Then, we study the d-extensibles sets of stable sets in trees. We prove some properties on the structures of the d-extensibles sets and we determine another lower bound of the maximum cardinality of a d-extensible set. Finaly, we study somme classes of tree where a d-extensible sets of maximum cardinality can be done in polynomial time.In a graph G, a d-blocker is a subset of vertices such that, if removed, a maximum stable set of the resulting subgraph is of cardinality at most the cardinality of a maximum stable set of G minus d. We study d-blocker of minimal cost of stable sets in tree.We prove a caracterisation of d-blockers in tree and we study a particular classe of trees where computing a d-blocker of minimal cost of stable sets can be done in polynomial time.Let Pi be an optimisation problem on a finite set of elements. A d-transversal of Pi is a subset of elements such that the intersection between the d-transversal and every optimal solution of Pi contains at lest d elements. We propose an approach to compute d-transversal of any optimisation problem modelised by mathematical program with binary variables. We use a contraints generation approach. We compare two variations of this approach on randomly generated graph by computing d-transversals of stables sets and d-transversals of matching