Search

The graph matching problem is among the most important challenges of graph processing, and plays a central role in various fields of pattern recognition. We propose an approximate method for labeled weighted graph matching, based on a convex-concave programming approach which can be applied to the matching of large sized graphs. This method allows to easily integrate information on graph label similarities into the optimization problem, and therefore to perform labeled weighted graph matching. One of the interesting applications of the graph matching problem is the alignment of protein-protein interaction networks. This problem is important when investigating evolutionary conserved pathways or protein complexes across species, and to help in the identification of functional orthologs through the detection of conserved interactions. We reformulate PPI alignment as a graph matching problem, and study how state-of-the-art graph matching algorithms can be used for this purpose. In the classical formulation of graph matching, only one-to-one correspondences are considered, which is not always appropriate. In many applications, it is more interesting to consider many-to-many correspondences between graph vertices. We propose a reformulation of the many-to-many graph matching problem as a discrete optimization problem and we propose an approximate algorithm based on a continuous relaxation. In this thesis, we also present two interesting results in statistical machine translation and bioinformatics. We show how the phrase-based statistical machine translation decoding problem can be reformulated as a Traveling Salesman Problem. We also propose a new protein binding pocket similarity measure based on a comparison of 3D atom clouds.; Le problème d'alignement de graphes, qui joue un rôle central dans différents domaines de la reconnaissance de formes, est l'un des plus grands défis dans le traitement de graphes. Nous proposons une méthode approximative pour l'alignement de graphes étiquetés et pondérés, basée sur la programmation convexe concave. Une application importante du problème d'alignement de graphes est l'alignement de réseaux d'interactions de protéines, qui joue un rôle central pour la recherche de voies de signalisation conservées dans l'évolution, de complexes protéiques conservés entre les espèces, et pour l'identification d'orthologues fonctionnels. Nous reformulons le problème d'alignement de réseaux d'interactions comme un problème d'alignement de graphes, et étudions comment les algorithmes existants d'alignement de graphes peuvent être utilisés pour le résoudre. Dans la formulation classique de problème d'alignement de graphes, seules les correspondances bijectives entre les noeuds de deux graphes sont considérées. Dans beaucoup d'applications, cependant, il est plus intéressant de considérer les correspondances entre des ensembles de nœuds. Nous proposons une nouvelle formulation de ce problème comme un problème d'optimisation discret, ainsi qu'un algorithme approximatif basé sur une relaxation continue. Nous présentons également deux résultats indépendants dans les domaines de la traduction automatique statistique et de la bio-informatique. Nous montrons d'une part comment le problème de la traduction statistique basé sur les phrases peut être reformulé comme un problème du voyageur de commerce. Nous proposons d'autre part une nouvelle mesure de similarité entre les sites de fixation de protéines, basée sur la comparaison 3D de nuages atomiques.

The graph matching problem is among the most important challenges of graph processing, and plays a central role in various fields of pattern recognition. We propose an approximate method for labeled weighted graph matching, based on a convex-concave programming approach which can be applied to the matching of large sized graphs. This method allows to easily integrate information on graph label similarities into the optimization problem, and therefore to perform labeled weighted graph matching. One of the interesting applications of the graph matching problem is the alignment of protein-protein interaction networks. This problem is important when investigating evolutionary conserved pathways or protein complexes across species, and to help in the identification of functional orthologs through the detection of conserved interactions. We reformulate PPI alignment as a graph matching problem, and study how state-of-the-art graph matching algorithms can be used for this purpose. In the classical formulation of graph matching, only one-to-one correspondences are considered, which is not always appropriate. In many applications, it is more interesting to consider many-to-many correspondences between graph vertices. We propose a reformulation of the many-to-many graph matching problem as a discrete optimization problem and we propose an approximate algorithm based on a continuous relaxation. In this thesis, we also present two interesting results in statistical machine translation and bioinformatics. We show how the phrase-based statistical machine translation decoding problem can be reformulated as a Traveling Salesman Problem. We also propose a new protein binding pocket similarity measure based on a comparison of 3D atom clouds.; Le problème d'alignement de graphes, qui joue un rôle central dans différents domaines de la reconnaissance de formes, est l'un des plus grands défis dans le traitement de graphes. Nous proposons une méthode approximative pour l'alignement de graphes étiquetés et pondérés, basée sur la programmation convexe concave. Une application importante du problème d'alignement de graphes est l'alignement de réseaux d'interactions de protéines, qui joue un rôle central pour la recherche de voies de signalisation conservées dans l'évolution, de complexes protéiques conservés entre les espèces, et pour l'identification d'orthologues fonctionnels. Nous reformulons le problème d'alignement de réseaux d'interactions comme un problème d'alignement de graphes, et étudions comment les algorithmes existants d'alignement de graphes peuvent être utilisés pour le résoudre. Dans la formulation classique de problème d'alignement de graphes, seules les correspondances bijectives entre les noeuds de deux graphes sont considérées. Dans beaucoup d'applications, cependant, il est plus intéressant de considérer les correspondances entre des ensembles de nœuds. Nous proposons une nouvelle formulation de ce problème comme un problème d'optimisation discret, ainsi qu'un algorithme approximatif basé sur une relaxation continue. Nous présentons également deux résultats indépendants dans les domaines de la traduction automatique statistique et de la bio-informatique. Nous montrons d'une part comment le problème de la traduction statistique basé sur les phrases peut être reformulé comme un problème du voyageur de commerce. Nous proposons d'autre part une nouvelle mesure de similarité entre les sites de fixation de protéines, basée sur la comparaison 3D de nuages atomiques.

Intelligent analysis and comparison of images is one of the most dynamic topic of research in both academia and industry. Describing and comparing images automatically is a critical issue for the full development of the «information society» Search engines working on textual data have dramatically proved their value. However, there is currently no similar system for image-only data. One possible explanation is that we do not really have a language made for describing images, thus meaningful comparisons are much more difficult than in the case of text. Nevertheless, textual search engines have shown that it is not necessary that the machines understand what they analyse to return good results. Simple syntactic analysis methods, coupled with composition rules are enough to drive extremely efficient systems. To enable machines to simulate the interpretation of images, it would be necessary to create descriptors playing the role of words in text and composition rules making it possible to compare images like search engines compare sentences.We already have at our disposal numerous methods to detected automatically simple objects or regions in images, by their common color, their identical motion, etc. Furthering the analogy, these objects could be seen as syllables. The difficulty lies in grouping them to form words, then sentences, and compare them while being robust to perturbations. To achieve this, we use graphs to store these objects and their relationships. These can be either of a neighboring nature, or inclusion, which leads the graphs to be either planar graphs or trees. We will see several methods to construct either type as well as their pros and cons. In a first step, we have used the graph-matching algorithms developed by Cristina Gomila at the end of her PhD thesis at the CMM (1998-2001). While working with the european project MASCOT studying the use of «metadata» to enhance video coding, we have studied in detail the algorithm and spotted its strengths and weaknesses.We first tested replacing the core of the matching algorithm by a better one. This resulted in slight improvements in both quality and computation time. Then we tried to reduce our sensitivity to variations in the segmentation process by using a spectral graph-matching algorithm. Despite good results on simple images, our tests on harder images have not succeeded. To improve our robustness with respect to the stability of the graphs, we then prefered working on the source material : images. The second step of this work was the development of image-base techniques to reduce the sensitivity of our segmentation algorithms to noise and small variations. First, we developed a class of adaptive filtering operatiors, the «morphological amoebas», which proved extremely effective in reducing noise in image. Second, we created a robust color gradient operator that can detect contour lines in noisy images. These two operators have improved sometimes spectacularly the stability of our segmentations, hence that of our graphs and in the end the quality of the results. The next step in this work has been the modeling of objects independently from the rest of the image. This approach was motivated by realizing that in some scenarii the content of the image outvii side some well-defined objects is not informative. We must thus analyse directly and as precisely as possible the objects themselves. We first supposed that the segmentation of the outline of the objects was a solved problem, and concentrated on creating a robust signature for each object. To get it, we modified a watershed algorithm in order to perform a top-down resegmentation of a morphological scalespace based on levelings. We used this resegmentation to build a robust tree of embedded regions, and we defined a distance between those trees. We tested the whole process on a commonly used database by the indexation community. The last step was centered around applications. First by comparing the various approches presented in this document, concentrating in particular on the speed versus robustness compromise. Then we search for the best combination of techniques to build a videosurveillance application. In particular, we developed fast and robust segmentation techniques for the project PS26-27 «Intelligent Environment» in partnership with ST Microelectronics and the ORION group of the INRIA. This aim of this project is to build a technology demonstrator for videosurveillance applied to the detection of accidents in hospitals or at home. Our part of the work was the detection of the outline of people in video sequences. Finally, by coupling these detectors to our tree-based objects descriptors, we were able to define robust signatures for people that could be use with great profit by automatic videosurveillance systems.; L'analyse et la comparaison intelligentes d'images sont parmi les sujets suscitant le plus d'intérêt dans les milieux académiques autant qu'industriels. Décrire et comparer automatiquement les images est en effet un enjeu critique pour le plein développement de la «société de l'information». Les moteurs de recherche fonctionnant sur le texte ont prouvé leur utilité de façon éclatante mais à l'heure actuelle il n'existe aucun système équivalent fonctionnant uniquement sur les images. Une explication possible est que nous ne disposons pas de langage permettant de décrire les images et que les comparaisons pertinentes sont ainsi beaucoup plus difficiles que dans le cas du texte. Cependant, le cas du texte nous montre qu'il n'est pas nécessaire que les machines comprennent ce qu'elles analysent pour renvoyer des résultats pertinents. Des méthodes simples d'analyse syntaxique associées à des règles de composition suffisent à piloter des moteurs de recherche d'une grande efficacité. Pour permettre à des machines de simuler l'interprétation des images, il faudrait donc créer des descripteurs faisant office de mots et des règles pour les regrouper, ce qui permettrait de comparer des scènes comme on compare des phrases. On dispose d'ores et déjà de nombreuses méthodes pour détecter automatiquement de petits objets et des régions dans des images, par leur couleur commune, leur mouvement identique, etc. Poursuivant l'analogie, on pourrait comparer ces petits objets à des syllabes. La difficulté consiste à les grouper en mots, puis en phrases et comparer celles-ci, tout en étant robuste face aux perturbations. Pour ce faire, nous utilisons des graphes pour stocker ces objets et leurs relations. Ces relations peuvent être de voisinage ou d'inclusion, ce qui conduit les graphes à être respectivement des graphes plans ou des arbres. Nous verrons ainsi plusieurs méthodes permettant de construire l'un ou l'autre type de représentation, ainsi que leurs avantages et inconvénients. Dans une première étape, nous avons utilisé les algorithmes d'appariement de graphes développés par Cristina Gomila à la fin de sa thèse au CMM (1998-2001). Profitant du projet européen MASCOT étudiant l'utilisation de «métadonnées» pour faciliter le codage vidéo, nous avons étudié en détail les forces et faiblesses de cette approche. Nous avons d'abord testé le remplacement de l'algorithme au coeur de l'appariement de graphes. Nous avons obtenu une légère amélioration de la stabilité et également de meilleurs temps de calcul. Puis nous avons cherché à améliorer notre robustesse face aux variations de segmentation en utilisant une projection dans le domaine spectral. Malgré de bons résultats sur des images simples, nos essais sur des images plus difficiles n'ont pas été couronnés de succès. Pour pallier cette fragilité dès que les graphes ne sont plus similaires, nous avons préféré revenir à notre matériau source, les images. La seconde étape de ce travail a porté sur le développement de techniques basées sur l'image pour réduire la sensibilité de nos algorithmes de segmentation au bruit et aux petites variations. Pour ce faire, nous avons développé une classe d'opérateurs de filtrage adaptatifs, les «amibes morphologiques », extrêmement efficaces pour réduire le bruit dans les images. Par ailleurs, nous avons également développé un opérateur de gradient couleur robuste permettant de mieux détecter les contours dans les images bruitées. Ces deux opérateurs ont amélioré de façon parfois impressionnante la stabilité de nos modélisations, puis de nos graphes et donc des résultats globaux. L'étape suivante dans ce travail a porté sur le développement de modélisations d'objets indépendamment du reste de l'image. La motivation derrière cette approche est de considérer que, dans certains scénarios, le contenu de l'image, hors de certains objets bien définis, n'est pas informatif. Il faut donc analyser directement et de la façon la plus précise possible les objets eux-mêmes. Nous avons dans un premier temps supposé que les segmentations des objets étaient connues, afin de nous concentrer sur le calcul d'une signature robuste de chaque objet. Pour l'obtenir, nous avons modifié un algorithme de ligne de partage des eaux pour effectuer une resegmentation «top-down» d'un espace d'échelle morphologique basé sur des nivellements. Ceci a donné lieu à une nouvelle modélisation robuste utilisant des arbres de régions imbriquées. Nous avons également développé une distance entre ces arbres et nous l'avons testée sur une base d'images classique dans le domaine de l'indexation. La dernière étape est centrée sur l'aspect applicatif. En premier lieu en comparant les différentes approches présentées dans ce travail, notamment aux niveaux de leur robustesse et de leur vitesse d'exécution. Enfin, nous avons cherché la meilleure combinaison de techniques pour concevoir une application de vidéosurveillance. En particulier, nous avons développé des techniques rapides et robustes de segmentation dans le cadre du projet PS26-27 «Environnement Intelligent» en collaboration avec ST Microelectronics et le groupe ORION de l'INRIA. Ce projet visait à construire un démonstrateur de technologies de vidéosurveillance appliquées à la détection d'accidents dans les cadres domestique et hospitalier. Notre part du travail consistait à la mise au point d'algorithmes de détection de silhouettes en mouvement dans des séquences vidéo. Ainsi, en couplant ces techniques à nos descripteurs d'objets par arbres, nous avons pu définir des signatures robustes de personnes, qui pourront être utilisées avec un grande efficacité dans des systèmes automatisés de vidéosurveillance.

Intelligent analysis and comparison of images is one of the most dynamic topic of research in both academia and industry. Describing and comparing images automatically is a critical issue for the full development of the «information society» Search engines working on textual data have dramatically proved their value. However, there is currently no similar system for image-only data. One possible explanation is that we do not really have a language made for describing images, thus meaningful comparisons are much more difficult than in the case of text. Nevertheless, textual search engines have shown that it is not necessary that the machines understand what they analyse to return good results. Simple syntactic analysis methods, coupled with composition rules are enough to drive extremely efficient systems. To enable machines to simulate the interpretation of images, it would be necessary to create descriptors playing the role of words in text and composition rules making it possible to compare images like search engines compare sentences.We already have at our disposal numerous methods to detected automatically simple objects or regions in images, by their common color, their identical motion, etc. Furthering the analogy, these objects could be seen as syllables. The difficulty lies in grouping them to form words, then sentences, and compare them while being robust to perturbations. To achieve this, we use graphs to store these objects and their relationships. These can be either of a neighboring nature, or inclusion, which leads the graphs to be either planar graphs or trees. We will see several methods to construct either type as well as their pros and cons. In a first step, we have used the graph-matching algorithms developed by Cristina Gomila at the end of her PhD thesis at the CMM (1998-2001). While working with the european project MASCOT studying the use of «metadata» to enhance video coding, we have studied in detail the algorithm and spotted its strengths and weaknesses.We first tested replacing the core of the matching algorithm by a better one. This resulted in slight improvements in both quality and computation time. Then we tried to reduce our sensitivity to variations in the segmentation process by using a spectral graph-matching algorithm. Despite good results on simple images, our tests on harder images have not succeeded. To improve our robustness with respect to the stability of the graphs, we then prefered working on the source material : images. The second step of this work was the development of image-base techniques to reduce the sensitivity of our segmentation algorithms to noise and small variations. First, we developed a class of adaptive filtering operatiors, the «morphological amoebas», which proved extremely effective in reducing noise in image. Second, we created a robust color gradient operator that can detect contour lines in noisy images. These two operators have improved sometimes spectacularly the stability of our segmentations, hence that of our graphs and in the end the quality of the results. The next step in this work has been the modeling of objects independently from the rest of the image. This approach was motivated by realizing that in some scenarii the content of the image outvii side some well-defined objects is not informative. We must thus analyse directly and as precisely as possible the objects themselves. We first supposed that the segmentation of the outline of the objects was a solved problem, and concentrated on creating a robust signature for each object. To get it, we modified a watershed algorithm in order to perform a top-down resegmentation of a morphological scalespace based on levelings. We used this resegmentation to build a robust tree of embedded regions, and we defined a distance between those trees. We tested the whole process on a commonly used database by the indexation community. The last step was centered around applications. First by comparing the various approches presented in this document, concentrating in particular on the speed versus robustness compromise. Then we search for the best combination of techniques to build a videosurveillance application. In particular, we developed fast and robust segmentation techniques for the project PS26-27 «Intelligent Environment» in partnership with ST Microelectronics and the ORION group of the INRIA. This aim of this project is to build a technology demonstrator for videosurveillance applied to the detection of accidents in hospitals or at home. Our part of the work was the detection of the outline of people in video sequences. Finally, by coupling these detectors to our tree-based objects descriptors, we were able to define robust signatures for people that could be use with great profit by automatic videosurveillance systems.; L'analyse et la comparaison intelligentes d'images sont parmi les sujets suscitant le plus d'intérêt dans les milieux académiques autant qu'industriels. Décrire et comparer automatiquement les images est en effet un enjeu critique pour le plein développement de la «société de l'information». Les moteurs de recherche fonctionnant sur le texte ont prouvé leur utilité de façon éclatante mais à l'heure actuelle il n'existe aucun système équivalent fonctionnant uniquement sur les images. Une explication possible est que nous ne disposons pas de langage permettant de décrire les images et que les comparaisons pertinentes sont ainsi beaucoup plus difficiles que dans le cas du texte. Cependant, le cas du texte nous montre qu'il n'est pas nécessaire que les machines comprennent ce qu'elles analysent pour renvoyer des résultats pertinents. Des méthodes simples d'analyse syntaxique associées à des règles de composition suffisent à piloter des moteurs de recherche d'une grande efficacité. Pour permettre à des machines de simuler l'interprétation des images, il faudrait donc créer des descripteurs faisant office de mots et des règles pour les regrouper, ce qui permettrait de comparer des scènes comme on compare des phrases. On dispose d'ores et déjà de nombreuses méthodes pour détecter automatiquement de petits objets et des régions dans des images, par leur couleur commune, leur mouvement identique, etc. Poursuivant l'analogie, on pourrait comparer ces petits objets à des syllabes. La difficulté consiste à les grouper en mots, puis en phrases et comparer celles-ci, tout en étant robuste face aux perturbations. Pour ce faire, nous utilisons des graphes pour stocker ces objets et leurs relations. Ces relations peuvent être de voisinage ou d'inclusion, ce qui conduit les graphes à être respectivement des graphes plans ou des arbres. Nous verrons ainsi plusieurs méthodes permettant de construire l'un ou l'autre type de représentation, ainsi que leurs avantages et inconvénients. Dans une première étape, nous avons utilisé les algorithmes d'appariement de graphes développés par Cristina Gomila à la fin de sa thèse au CMM (1998-2001). Profitant du projet européen MASCOT étudiant l'utilisation de «métadonnées» pour faciliter le codage vidéo, nous avons étudié en détail les forces et faiblesses de cette approche. Nous avons d'abord testé le remplacement de l'algorithme au coeur de l'appariement de graphes. Nous avons obtenu une légère amélioration de la stabilité et également de meilleurs temps de calcul. Puis nous avons cherché à améliorer notre robustesse face aux variations de segmentation en utilisant une projection dans le domaine spectral. Malgré de bons résultats sur des images simples, nos essais sur des images plus difficiles n'ont pas été couronnés de succès. Pour pallier cette fragilité dès que les graphes ne sont plus similaires, nous avons préféré revenir à notre matériau source, les images. La seconde étape de ce travail a porté sur le développement de techniques basées sur l'image pour réduire la sensibilité de nos algorithmes de segmentation au bruit et aux petites variations. Pour ce faire, nous avons développé une classe d'opérateurs de filtrage adaptatifs, les «amibes morphologiques », extrêmement efficaces pour réduire le bruit dans les images. Par ailleurs, nous avons également développé un opérateur de gradient couleur robuste permettant de mieux détecter les contours dans les images bruitées. Ces deux opérateurs ont amélioré de façon parfois impressionnante la stabilité de nos modélisations, puis de nos graphes et donc des résultats globaux. L'étape suivante dans ce travail a porté sur le développement de modélisations d'objets indépendamment du reste de l'image. La motivation derrière cette approche est de considérer que, dans certains scénarios, le contenu de l'image, hors de certains objets bien définis, n'est pas informatif. Il faut donc analyser directement et de la façon la plus précise possible les objets eux-mêmes. Nous avons dans un premier temps supposé que les segmentations des objets étaient connues, afin de nous concentrer sur le calcul d'une signature robuste de chaque objet. Pour l'obtenir, nous avons modifié un algorithme de ligne de partage des eaux pour effectuer une resegmentation «top-down» d'un espace d'échelle morphologique basé sur des nivellements. Ceci a donné lieu à une nouvelle modélisation robuste utilisant des arbres de régions imbriquées. Nous avons également développé une distance entre ces arbres et nous l'avons testée sur une base d'images classique dans le domaine de l'indexation. La dernière étape est centrée sur l'aspect applicatif. En premier lieu en comparant les différentes approches présentées dans ce travail, notamment aux niveaux de leur robustesse et de leur vitesse d'exécution. Enfin, nous avons cherché la meilleure combinaison de techniques pour concevoir une application de vidéosurveillance. En particulier, nous avons développé des techniques rapides et robustes de segmentation dans le cadre du projet PS26-27 «Environnement Intelligent» en collaboration avec ST Microelectronics et le groupe ORION de l'INRIA. Ce projet visait à construire un démonstrateur de technologies de vidéosurveillance appliquées à la détection d'accidents dans les cadres domestique et hospitalier. Notre part du travail consistait à la mise au point d'algorithmes de détection de silhouettes en mouvement dans des séquences vidéo. Ainsi, en couplant ces techniques à nos descripteurs d'objets par arbres, nous avons pu définir des signatures robustes de personnes, qui pourront être utilisées avec un grande efficacité dans des systèmes automatisés de vidéosurveillance.

Not available, La recherche combinatoire est une branche de l'algorithmique combinatoire qui est étroitement liée avec d'autres domaines des mathématiques et de l'informatique, tels que l'étude de la complexité d'algorithmes, la théorie des graphes, la théorie des nombres, la théorie des ensembles extrémaux. En termes très généraux, la recherche combinatoire étudié les problèmes d'identification d'un objet inconnu dans un ensemble d'objets à l'aide de questions indirectes sur cet objet. Les méthodes de la recherche combinatoire trouvent de nombreuses applications pratiques dans les domaines de la biologie, la médecine, la conception de réseaux, et d'autres. Le thème central de la thèse est le modèle additif en recherche combinatoire. Nous étudions la puissance de ce modèle en l'appliquant à quelques problèmes classiques de recherche combinatoire. Trois familles de problèmes sont considérées : les problèmes de pesage de monnaies, le problème de reconstruction de graphes d'une classe donnée et le problème de reconstruction de partitions. Pour les problèmes de reconstruction de graphes et de pesage, nous examinons les résultats connus et démontrons de nouveaux résultats plus généraux. Un des résultats les plus importants est l'obtention d'une borne supérieure pour le problème de reconstruction de vecteurs à poids borné. Nous introduisons également le problème de reconstruction de partitions, pour lequel nous développons des algorithmes efficaces dont nous analysons la complexité

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

A partir du concept de paire d'amis dans un graphe (paire de sommets telle que toutes les chaînes sans cordes qui les relient sont de longueur paire) deux classes de graphes parfaits ont été déjà définies. La première notée QPS (graphes de quasi-parité stricte) est définie par l'existence de paires d'amis pour tout sous-graphe induit incomplet. La deuxième notée PC (graphes parfaitement contractibles) est définie à partir de l'idée algorithmique de coloration du graphe ou de ses sous-graphes induits par enchaînement de contractions successives des sommets d'une paire d'amis jusqu'à obtenir une clique, auquel cas la coloration est optimale. Dans cette thèse nous avons abordé deux conjectures: la première (relative à la classe QPS) énoncée par S. Hougardy est proche de la conjecture forte de graphes parfaits et la deuxième énoncée par H. Everett et B. Reed consite à caractériser les graphes PC par sous-graphes exclus. Nous avons pu valider ces deux conjectures dans deux cas: le cas des graphes planaires et le cas des graphes sans griffe. Ces quatre résultats sont assortis d'algorithmes polynomiaux de reconnaissance (ainsi que de coloration pour la classe PC)

Université : Université scientifique et médicale de Grenoble; Introduction. Graphes de cordes. Généralités. Diagrammes orientés. Orientations géométriques. Pseudo-tournois de cordes orientées. PL-graphes. Graphes de cordes et matroïdes binaires. Bibliographie

Université : Université scientifique et médicale de Grenoble; É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

La première partie de notre travail, menée en collaboration étroite avec V. BOUCHITTE et M. HABIB, porte sur l'étude de quelques invariants comme le nombre de sauts et la dimension sur les ensembles ordonnés finis. Nous reproduisons ici intégralement les deux articles N-free posets as generalizations of series-parallel posets M. HABIB, R. JEGOU Sorne results on the greedy dimension V. BOUCHITTE~ M. HABIB, R. JEGOU à paraître respectivement dans Discrete Applied Mathematics et dans Order. Le nombre de sauts a fait l'objet de nombreux travaux parmi lesquels ceux de G. CHATY, M. CHEIN, O. COGIS, U. FAIGLE, G. GIERZ, M. HABIB, P. MARTIN, G. PETOLLA, W. POGUNTKE, W.R. PULLEYBLANK, I. RIVAL, M.M. SYSLO ..., et reste d'actua1ité comme en témoigne le congrès GRAPHS and OROER (Banff 1984). Cette notion définie originellement sur les graphes sans circuit comme étant le nombre minimum d'arcs à ajouter à un tel graphe pour obtenir un graphe sans circuit ayant un chemin hamiltonien, est étudiée ici sur les ordres sans N. Nous mettons en évidence une construction récursive de ces ordres en généralisant celle des ordres série parallèles(SP) introduits par E.L. LAWLER et étudiés notamment par J. VALDES, R.E. TARJAN et E.L. LAWLER. Les ordres sans N, ou quasi-série-parallè1es(QSP), peuvent donc se définir à 1 'aide de deux opérations simples à partir de l'ordre réduit à un élément. Cette construction permet en particulier d'obtenir un algorithme linéaire (en fonction du nombre de sommets et du nombre d'arcs du graphe de Hasse) de reconnaissance et de décomposition qui calcule le nombre de sauts., No abstract

Introduction. Couvertures des graphes par des cycles. Couverture par des circuits d'un matroïde régulier qui admet un Z.5- flot non nul. Flots de Fulkerson. Flots de Petersen. Constructions locales. Annexe. Bibliographie