Ce travail a pour motivation une meilleure compréhension des graphes parfaits. La preuve en 2002 de la conjecture des graphes parfaits de Claude Berge par Chudnovsky, Robertson, Seymour et Thomas a jeté une lumière nouvelle sur ce domaine de la combinatoire, mais a laissé plusieurs questions en suspens, notamment l'existence d'un algorithme combinatoire de coloration des graphes parfaits. Une paire d'amis d'un graphe est une paire de sommets telle que tous les chemins les reliant sont de longueur paire. Comme l'ont montré Fonlupt et Urhy, la contraction d'une paire amis préserve le nombre chromatique du graphe, et appliquée récursivement, permet dans certains cas de colorier optimalement le graphe. Nous prouvons une conjecture de Everett et Reed affirmant que cette approche fonctionne pour une classe de graphes parfaits: les graphes d'Artémis. Nous en déduisons un algorithme de coloration des graphes Artémis de complexité O(mn^2). Nous donnons un algorithme de complexité O(n^9) pour la reconnaissance des graphes d'Artémis. D'autres algorithmes de reconnaissance sont donnés, tous fondés sur des routines de détection de sous-graphes dans des graphes de Berge. Nous montrons que ces problèmes de détection sont NP-complets si on cherche à les étendre aux graphes quelconques.

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.

Les graphes, outil mathématique pour modéliser les relations entre des entités, sont en augmentation constante du fait d'internet (par exemple les réseaux sociaux). La visualisation de graphe (aussi appelée dessin) permet d'obtenir immédiatement des informations sur le graphe. Les graphes issus d'internet sont généralement stockés de manière morcelée sur plusieurs machines connectées par un réseau. Cette thèse a pour but de développer des algorithmes de dessin de très grand graphes dans le paradigme MapReduce, utilisé pour le calcul sur cluster. Parmi les algorithmes de dessin, les algorithmes reposants sur un modèle physique sous-jacent pour réaliser le dessin permettent d'obtenir un bon dessin indépendamment de la nature du graphe. Nous proposons deux algorithmes par modèle de forces conçus dans le paradigme MapReduce. GDAD, le premier algorithme par modèle de force dans le paradigme MapReduce, utilise des pivots pour simplifier le calcul des interactions entre les nœuds du graphes. MuGDAD, le prolongement de GDAD, utilise une simplification récursive du graphe pour effectuer le dessin, toujours à l'aide de pivots. Nous comparons ces deux algorithmes avec les algorithmes de l'état de l'art pour évaluer leurs performances. / Graphs, usually used to model relations between entities, are continually growing mainly because of the internet (social networks for example). Graph visualization (also called drawing) is a fast way of collecting data about a graph. Internet graphs are often stored in a distributed manner, split between several machines interconnected. This thesis aims to develop drawing algorithms to draw very large graphs using the MapReduce paradigm, used for cluster computing. Among graph drawing algorithms, those which rely on a physical model to compute the node placement are generally considered to draw graphs well regardless of the type of graph. We developped two force-directed graph drawing algorithms in the MapReduce paradigm. GDAD, the fist distributed force-directed graph drawing algorithm ever, uses pivots to simplify computations of node interactions. MuGDAD, following GDAD, uses a recursive simplification to draw the original graph, keeping the pivots. We compare these two algorithms with the state of the art to assess their performances.

La baisse des coûts de communication, l'amélioration de la performance des réseaux et l'évolution des plateformes de services dédiées permettant de gérer une multitude d'objets, a conduit à l'apparition de nouveaux usages et de nouvelles applications rassemblées sous l'appellation "Machine-à-Machine'' abrégée en M2M. Ce travail de thèse propose de répondre aux défis d'autogestion caractérisés par les récentes études de l'informatique autonomique. Il traite de la modélisation et de la validation des systèmes M2M opérant dans un contexte dynamique et sous un ensemble de propriétés structurelles et temporisées. Pour ce faire, nous proposons de nous appuyer sur les grammaires de graphes et des techniques de model checking. Dans un premier temps, nous nous sommes intéressés à la vérification au moment de la conception des communications M2M opérant sous des contraintes temporisées. Pour ce faire, nous avons proposé une approche de vérification formelle basée sur les techniques de model checking. Pour caractériser les entités M2M ainsi que leurs propriétés temporisées, un modèle formel basé sur les automates temporisés a été introduit. Étant donné que les systèmes M2M impliquent un grand nombre d'éléments, une approche de vérification partielle du système a été adoptée. La vérification au moment de la conception est une étape très importante, cependant elle n'est pas suffisante. En effet, les systèmes M2M sont hautement dynamiques et leur adaptation au moment de l'exécution est cruciale pour garantir leur bon fonctionnement. Dans un premier temps, nous nous sommes intéressés à la gestion des propriétés structurelles des systèmes M2M. Pour ce faire, nous nous sommes référés au standard européen smartM2M pour définir un style architectural décrivant les organisations acceptables du système. Afin de conduire des actions de reconfiguration dynamiques, nous nous sommes basés sur les grammaires de graphes et des règles de transformation de graphes. L'approche de reconfiguration proposée a été ensuite étendue pour prendre en compte les contraintes temporisées lors de la reconfiguration des systèmes M2M. Pour ce faire, nous avons caractérisé les systèmes M2M en trois couches : une couche application qui exprime les propriétés temporisées entre les applications M2M, une couche service pour décrire les composants nécessaires à l'exécution des applications et une couche infrastructure décrivant le déploiement de ces derniers sur une infrastructure physique. Des mécanismes de reconfiguration dynamique guidés par les contraintes temporisées ont été proposés et implémentés dans un gestionnaire autonomique qui interagit avec ces différentes couches. Son rôle est de superviser, de contrôler, et de garantir le comportement temporisé du système. / The decrease in communication costs, the improvement of networks performance and the evolution of the dedicated services platforms managing multiple objects, led to the appearance of new practices and applications gathered under the designation of Machine-to-Machine communications (M2M). M2M systems have to integrate in a coordinated way various devices and software modules such as sensors, actuators, displays, middleware, etc. M2M expansion gives rise to extensive data exploitation, effective routing and reasoning mechanisms for an appropriate decision making and a coordinated control in a predictive and reactive way. This work aims to meet self-management challenges characterized by recent studies of autonomic computing. It deals with the modeling and the validation of M2M systems operating in a dynamic context and under a set of functional and non-functional properties, specifically temporal ones. To do so, we propose to rely on graph grammars and model checking related techniques. This allows to configure and to reconfigure a set of communicating objects by considering a set of constraints. First, we were interested in the validation at design time of M2M communications operating under temporal constraints. A verification and validation approach based on timed automata was proposed. A smart grid scenario was developed to validate the proposed model. This step is necessary, however it is not sufficient. Indeed, M2M systems are dynamic and verification at run time is important. To validate the execution of an M2M system, we focused on in its functional and temporal aspects. We referred to the European standard smartM2M to define an architectural style for M2M systems. This standard was selected for the following reasons: (1) its independence of the application domain and the objects' communication technology, (2) its broad scope and (3) its deployment on industrial systems. To validate the M2M system' functionalities, a multi-model approach was proposed: a first model, named functional, representing a real-time view of M2M system and a second model, named formal, based on a graph grammar incorporating the concepts of the functional layer. To conduct dynamic reconfiguration actions, graph transformation rules have been defined. Bi-directional communication mechanisms have been set up to maintain coherence between the real system and its models. A smart metering use case was developed to validate the proposed approach. With the aim of validating temporal properties of an M2M system during its execution, this approach has been extended with new concepts. We have defined a three-layers based approach to describe the features and temporal properties of an M2M system: an application layer which incorporates the concepts defined in the formal layer of the previous approach with extensions to express temporal properties between applications M2M, a service layer to describe the necessary components to meet the specification of the upper layer and infrastructure layer describing their deployment. An autonomic manager interacts with these layers to supervise and control the temporal behavior of the system. These layers are part of the autonomic manager knowledge base. The autonomic manager architecture and dynamic reconfiguration mechanisms were detailed. An eHealth scenario has been designed to illustrate the proposed approach.

Cette thèse porte sur deux sujets d’algorithmique des graphes. Le premier sujet est l’inférence de réseaux. Quelle est la complexité pour déterminer un graphe inconnu à partir de requêtes de plus court chemin entre ses sommets ? Nous supposons que le graphe est de degré borné. Dans le problème de reconstruction, le but est de reconstruire le graphe ; tandis que dans le problème de vérification, le but est de vérifier qu’un graphe donné est correct. Nous développons des algorithmes probabilistes utilisant une décomposition en cellules de Voronoi. Ensuite, nous analysons des algorithmes de type glouton, et montrons qu’ils sont quasi-optimaux. Nous étudions aussi ces problèmes sur des familles particulières de graphes, démontrons des bornes inférieures, et étudions la reconstruction approximative. Le deuxième sujet est l’étude de deux problèmes d’optimisation sur les graphes planaires. Dans le problème de classification par corrélations, l’entrée est un graphe pondéré, où chaque arête a une étiquette h+i ou h-i, indiquant si ses extrémités sont ou non dans la même catégorie. Le but est de trouver une partition des sommets en catégories qui respecte au mieux les étiquettes. Dans le problème d’augmentation 2-arête-connexe, l’entrée est un graphe pondéré et un sous-ensemble R des arêtes. Le but est de trouver un sous-ensemble S des arêtes de poids minimum, tel que pour chaque arête de R, ses extrémités sont dans une composante 2-arête-connexe de l’union de R et S. Pour les graphes planaires, nous réduisons le premier problème au deuxième et montrons que les deux problèmes, bien que NP-durs, ont un schéma d’approximation en temps polynomial. Nous utilisons la technique récente de décomposition en briques. / This thesis focuses on two topics of graph algorithms. The first topic is network inference. How efficiently can we find an unknown graph using shortest path queries between its vertices? We assume that the graph has bounded degree. In the reconstruction problem, the goal is to find the graph; and in the verification problem, the goal is to check whether a given graph is correct. We provide randomized algorithms based on a Voronoi cell decomposition. Next, we analyze greedy algorithms, and show that they are near-optimal. We also study the problems on special graph classes, prove lower bounds, and study the approximate reconstruction. The second topic is optimization in planar graphs. We study two problems. In the correlation clustering problem, the input is a weighted graph, where every edge has a label of h+i or h−i, indicating whether its endpoints are in the same category or in different categories. The goal is to find a partition of the vertices into categories that tries to respect the labels. In the two-edge-connected augmentation problem, the input is a weighted graph and a subset R of edges. The goal is to produce a minimum-weight subset S of edges, such that for every edge in R, its endpoints are two-edge-connected in the union of R and S. For planar graphs, we reduce correlation clustering to two-edge-connected augmentation, and show that both problems, although they are NP-hard, have a polynomial-time approximation scheme. We build on the brick decomposition technique developed recently.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissance / Two problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph

Cette dernière décennie, la modélisation des villes 3D est devenue l'un des enjeux de la recherche multimédia et un axe important en reconnaissance d'objets. Dans cette thèse nous nous sommes intéressés à localiser différentes primitives, plus particulièrement les fenêtres, dans les façades de Paris. Dans un premier temps, nous présentons une analyse des façades et des différentes propriétés des fenêtres. Nous en déduisons et proposons ensuite un algorithme capable d'extraire automatiquement des hypothèses de fenêtres. Dans une deuxième partie, nous abordons l'extraction et la reconnaissance des primitives à l'aide d'appariement de graphes de contours. En effet une image de contours est lisible par l'oeil humain qui effectue un groupement perceptuel et distingue les entités présentes dans la scène. C'est ce mécanisme que nous avons cherché à reproduire. L'image est représentée sous la forme d'un graphe d'adjacence de segments de contours, valué par des informations d'orientation et de proximité des segments de contours. Pour la mise en correspondance inexacte des graphes, nous proposons plusieurs variantes d'une nouvelle similarité basée sur des ensembles de chemins tracés sur les graphes, capables d'effectuer les groupements des contours et robustes aux changements d'échelle. La similarité entre chemins prend en compte la similarité des ensembles de segments de contours et la similarité des régions définies par ces chemins. La sélection des images d'une base contenant un objet particulier s'effectue à l'aide d'un classifieur SVM ou kppv. La localisation des objets dans l'image utilise un système de vote à partir des chemins sélectionnés par l'algorithme d'appariement. / This last decade, modeling of 3D city became one of the challenges of multimedia search and an important focus in object recognition. In this thesis we are interested to locate various primitive, especially the windows, in the facades of Paris. At first, we present an analysis of the facades and windows properties. Then we propose an algorithm able to extract automatically window candidates. In a second part, we discuss about extraction and recognition primitives using graph matching of contours. Indeed an image of contours is readable by the human eye, which uses perceptual grouping and makes distinction between entities present in the scene. It is this mechanism that we have tried to replicate. The image is represented as a graph of adjacency of segments of contours, valued by information orientation and proximity to edge segments. For the inexact matching of graphs, we propose several variants of a new similarity based on sets of paths, able to group several contours and robust to scale changes. The similarity between paths takes into account the similarity of sets of segments of contours and the similarity of the regions defined by these paths. The selection of images from a database containing a particular object is done using a KNN or SVM classifier.

L'hypercube a suscité de nombreuses études engendrant une littérature très dense aussi bien en mathématiques discrètes qu'en informatique. Cet intérêt sans cesse croissant est largement motivé par l'utilisation de sa structure dans de nombreux domaines (architectures parallèles, transfert de l'information, décision multicritère,...). Chacun peut s'étonner des raisons qui font que le cube soit le cube?. Sa simple définition peut déjà apporter une réponse quoique partielle à une telle question. Plusieurs propriétés spécifiques à l'hypercube ont, soit, défini de nouvelles classes de graphes, soit, fait ressortir le rôle remarquable joué par celui-ci dans plusieurs classes déjà existantes. Les (0, 2)-graphes sont une généralisation naturelle de l'hypercube. Il est maximal dans cette classe. Le thème de cette thèse consiste en la définition et la caractérisation de quelques classes de (0, 2)-graphes obtenues à partir de l'hypercube par rajout d'arêtes ou identification de sommets. Nous caractérisons au chapitre II, le graphe de l'hyperoctaèdre comme un {2(n-2), 2(n-1)}-graphe d'ordre 2n, et nous prouvons l'unicité de son cycle hamiltonien et cela à une équivalence naturelle près. Nous donnons, au chapitre III, une caractérisation de l'hypercube en tant que graphe distance-régulier de vecteur d'intersection {d, d-1, ..., 1; 1, 2, ..., d}. Une classe de (0, 2)-graphes minimaux -les graphes de Shrikhande généralisés- y est étudiée et une caractérisation des graphes de Laborde-Mulder comme (0, 2)-graphes de diamètre minimum [d/2] parmi ceux d'ordre 2d-1 et de degré d impair est donnée. Au chapitre IV, nous caractérisons parmi les hypercubes généralisés ceux qui sont des (0, 2)-graphes. Nous présentons une construction de (0, 2)-graphes non sommet-transitifs. On montre enfin que les graphes de Laborde-Mulder et du demi-cube sont plongeables dans le carré de l'hypercube. Dans un dernier chapitre, nous nous intéressons au problème d'existence de (0, 2)-graphe d'un ordre donné. Nous donnons une condition nécessaire d'existence de tels graphes pour un ordre impair. Nous montrons ensuite qu'à l'ordre 18 et 20, il n'existe pas de (0, 2)-graphes, en utilisant à cette fin un algorithme de construction de (0, 2)-graphes. Nous présentons enfin quelques résultats sur la structure locale des (0, 2)-graphes

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 (s,a)=(1,0) si k=0, (s,a)=(1,1) si k=1, s=a>0 si k=2, 0< s <= 2a <= 2ks si k>2. (resp. (s,a)=(1,0) si k=0, (s,a)=(1,1) si k=1 ou 2, s-1<=a<=(k-1)s+1 et s,a>0 si k>2.) 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. 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.