Avec la croissance importante du besoin d'analyser une grande masse de données structurées tels que les composés chimiques, les structures de protéines ou même les réseaux sociaux, la fouille de sous-graphes fréquents est devenue un défi réel en matière de fouille de données. Ceci est étroitement lié à leur nombre exponentiel ainsi qu'à la NP-complétude du problème d'isomorphisme d'un sous-graphe général. Face à cette complexité, et pour gérer cette taille importante de l'espace de recherche, les méthodes classiques de fouille de graphes ont exploré des heuristiques de recherche basées sur le support, le langage de description des exemples (limitation aux chemins, aux arbres, etc.) ou des hypothèses (recherche de sous-arborescence communes, de chemins communs, etc.). Dans le cadre de cette thèse, nous nous basons sur une méthode d'appariement de graphes issue du domaine de la programmation par contraintes, nommée AC-projection, qui a le mérite d'avoir une complexité polynomiale. Nous introduisons des approches de fouille de graphes permettant d'améliorer les approches existantes pour ce problème. En particulier, nous proposons deux algorithmes, FGMAC et AC-miner, permettant de rechercher les sous-graphes fréquents à partir d'une base de graphes. Ces deux algorithmes profitent, différemment, des propriétés fortes intéressantes de l'AC-projection. En effet, l'algorithme FGMAC adopte un parcours en largeur de l'espace de recherche et exploite l'approche par niveau introduite dans Apriori, tandis que l'algorithme AC-miner parcourt l'espace en profondeur par augmentation de motifs, assurant ainsi une meilleure mise à l'échelle pour les grands graphes. Ces deux approches permettent l'extraction d'un type particulier de graphes, il s'agit de celui des sous-graphes AC-réduits fréquents. Dans un premier temps, nous prouvons, théoriquement, que l'espace de recherche de ces sous-graphes est moins important que celui des sous-graphes fréquents à un isomorphisme près. Ensuite, nous menons une série d'expérimentations permettant de prouver que les algorithmes FGMAC et AC-miner sont plus efficients que ceux de l'état de l'art. Au même temps, nous prouvons que les sous-graphes AC-réduits fréquents, en dépit de leur nombre sensiblement réduit, ont le même pouvoir discriminant que les sous-graphes fréquents à un isomorphisme près. Cette étude est menée en se basant sur une évaluation expérimentale de la qualité des sous-graphes AC-réduits fréquents dans un processus de classification supervisée de graphes. / With the important growth of requirements to analyze large amount of structured data such as chemical compounds, proteins structures, social networks, to cite but a few, graph mining has become an attractive track and a real challenge in the data mining field. Because of the NP-Completeness of subgraph isomorphism test as well as the huge search space, frequent subgraph miners are exponential in runtime and/or memory use. In order to alleviate the complexity issue, existing subgraph miners have explored techniques based on the minimal support threshold, the description language of the examples (only supporting paths, trees, etc.) or hypothesis (search for shared trees or common paths, etc.). In this thesis, we are using a new projection operator, named AC-projection, which exhibits nice complexity properties as opposed to the graph isomorphism operator. This operator comes from the constraints programming field and has the advantage of a polynomial complexity. We propose two frequent subgraph mining algorithms based on the latter operator. The first one, named FGMAC, follows a breadth-first order to find frequent subgraphs and takes advantage of the well-known Apriori levelwise strategy. The second is a pattern-growth approach that follows a depth-first search space exploration strategy and uses powerful pruning techniques in order to considerably reduce this search space. These two approaches extract a set of particular subgraphs named AC-reduced frequent subgraphs. As a first step, we have studied the search space for discovering such frequent subgraphs and proved that this one is smaller than the search space of frequent isomorphic subgraphs. Then, we carried out experiments in order to prove that FGMAC and AC-miner are more efficient than the state-of-the-art algorithms. In the same time, we have studied the relevance of frequent AC-reduced subgraphs, which are much fewer than isomorphic ones, on classification and we conclude that we can achieve an important performance gain without or with non-significant loss of discovered pattern's quality.

Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes.

La première partie de la thèse porte sur les graphes de Steinhaus réguliers. On commence par obtenir une nouvelle preuve du théorème de Dymacek, selon lequel toute matrice de Steinhaus associée à un graphe pair est bisymétrique, en exhibant une relation entre les éléments de l'antidiagonale d'une matrice de Steinhaus et les degrés des sommets du graphe associé. Ce théorème est ensuite utilisé pour montrer que toute matrice de Steinhaus associée à un graphe régulier de degré impair admet une grande sous-matrice multisymétrique. On étudie alors les matrices de Steinhaus multisymétriques, en particulier celles dont le graphe associé admet une certaine régularité. Cette étude permet enfin de vérifier jusqu'à 1500 sommets une conjecture de Dymacek, qui annonce que le graphe complet à deux sommets K2 est le seul graphe de Steinhaus régulier de degré impair, améliorant ainsi d'un facteur 12 la borne précédemment connue (117 sommets).<br />La seconde partie porte sur les triangles de Steinhaus dans Z/nZ. En 1978 Molluzzo pose le problème de savoir si, pour tout n≥1 et pour toute longueur admissible m, il existe une suite balancée de longueur m dans Z/nZ, c'est-à-dire une suite dont le triangle de Steinhaus associé contienne chaque élément de Z/nZ avec la même multiplicité. On donne ici une réponse complète et positive au Problème de Molluzzo dans tout groupe cyclique d'ordre une puissance de 3. Plus généralement, on construit une infinité de suites balancées dans tout groupe cyclique d'ordre impair. Ces résultats, qui sont les premiers obtenus sur ce problème dans Z/nZ avec n>3, proviennent de l'étude des triangles de Steinhaus des suites arithmétiques dans les groupes cycliques.

Cabri-graphes est un environnement logiciel, destine aux chercheurs, étudiants et enseignants en théorie des graphes. La pratique de cette discipline amené a recourir a des représentations graphiques, afin de visualiser les structures mathématiques mises en œuvre; ceci dans le but de les manipuler, de leur appliquer concrètement certaines transformations, afin de vérifier une propriété, conforter ou infirmer une idée, une conjecture. Cette pratique, menée sur un cahier de brouillon traditionnel, souffre de limitations et les résultats ne sont que faiblement garantis. C'est pourquoi nous avons étudié et réalisé un logiciel, alliant la simplicité d'usage d'un environnement interactif à la puissance de l'ordinateur. Cette thèse présente l'ensemble des concepts mathématiques et de génie logiciel ayant servi a la réalisation de ce projet. Nous donnons en particulier l'implémentation d'un générateur de graphes aléatoires, ainsi que quelques applications motivées et réalisées grâce à cet environnement logiciel

Nous considérons le problème de concevoir des représentations compactes ou succinctes de structures de données géométriques. Dans ce cadre, en plus des questions de simple compression, l'attention est portée sur l'étude de structures de données nécessitant une petite quantité de ressources mémoire et permettant de répondre à des requêtes locales en temps O(1). L'une des contributions de cette thèse consiste à proposer un cadre algorithmique général pour la conception de représentations compactes de structures telles que les graphes planaires et les maillages surfaciques. Comme application nous présentons différentes structures spécialement conçues pour représenter de manière compacte la connectivité (ou information combinatoire) de certaines classes de graphes localement planaires. Pour le cas des triangulations planaires à m faces, nous proposons une représentation compacte de l'information combinatoire nécessitant asymptotiquement 2:175 bits par triangle pour le coût en espace et qui permet la navigation entre triangles adjacents, ainsi que d'autres requêtes locales d'incidence entre sommets, en temps constant : cette structure est ainsi optimale pour la classe des triangulations ayant un bord de taille arbitraire. Une telle représentation reste valide et optimale dans le cas de triangulations d'une surface de genre g borné : O(g lgm) bits supplémentaires sont alors nécessaires. Cette représentation est bien adaptée pour faire une mise à jour locale efficace de la triangulation. Plus précisément, il est possible d'effectuer des mises à jour en temps O(1) amorti après insertion de sommets, et en temps O(log2m) amorti après suppression de sommets et flip d'arêtes. Et en ce qui concerne les triangulations et les graphes planaires 3-connexes, correspondant aux maillages triangulaires et polygonaux homéomorphes à une sphère, nous proposons les premières représentations succinctes optimales : elles atteignent l'entropie respective des deux classes, 2 bits par arête pour les graphes 3-connexes, et 1:62 bits par triangle (ou 3:24 bits par sommet) pour les triangulations. Ces structures permettent aussi l'accès en temps O(1) aux informations associées aux sommets, notamment leurs coordonnées. Cependant nous ne traitons pas ici la compression de cette information géométrique.

.

.

Le problème de placement sur deux dimensions consiste à décider s'il existe un rangement d'objets rectangulaires dans une boîte donnée. C'est un problème combinatoire difficile (à la complexité du respect des capacités s'ajoute celle du positionnement des objets). Nous considérons les variantes sans rotation des objets et avec ou sans optimisation de la valeur des objets placés. Nous menons une étude exploratoire des méthodologies qui peuvent être développées à l'interface de la programmation mathématique, de l'optimisation combinatoire et de la théorie des graphes. Nous comparons les formulations de la littérature et en proposons de nouvelles. Nous développons et testons deux approches de résolution innovantes. L'une est basée sur la décomposition de Dantzig-Wolfe (avec un branchement sur les contraintes disjonctives de non recouvrement des objets). L'autre constitue en une approche combinatoire basée sur diverses caractérisations des graphes d'intervalles (modélisant le chevauchement des objets selon chaque axe).

Dans la limite "diluée" où les nombres d'arêtes et de sommets divergent de manière comparable, il est naturel d'espérer que divers invariants classiques en théorie des graphes seront essentiellement déterminés par la seule "géométrie locale" du graphe -- c'est à dire, informellement, par l'aspect d'une boule de petit rayon autour d'un "sommet typique". Cette heuristique a pour origine l'étude des systèmes de particules en physique statistique, où sous certaines conditions, les contributions microscopiques provenant de sites suffisamment éloignés peuvent être considérées comme mutuellement indépendantes dans le calcul des grandeurs macroscopiques fondamentales du système. Mathématiquement, cette précieuse absence d'intéractions à longue portée peut se décrire rigoureusement à l'aide d'une propriété topologique : la continuité de l'invariant considéré vis-à-vis de la convergence locale faible des graphes. Tout invariant pour lequel on peut établir une telle continuité admettra aussitôt une limite déterministe le long de la plupart des suites de graphes aléatoires classiques, et pourra être efficacement approximé par des algorithmes locaux et distribués, indépendamment de la taille totale du système. Dans cette thèse, nous établissons la continuité de quatre invariants de graphes qui jouent un rôle essentiel en théorie comme dans les applications : la distribution spectrale empirique, la dimension du noyau de la matrice d'adjacence, la taille d'un couplage maximum, et le polynôme énumérant certaines familles de sous-graphes couvrants. Plus précisément, nous montrons qu'il existe une unique manière localement cohérente d'étendre chacune de ces notions aux limites locales faibles de graphes finis, et que ce prolongement est continu. Pour les modèles de graphes aléatoires classiques, les équations de cohérence locale se simplifient en une équation aux distributions que nous résolvons explicitement. Cela conduit à de nouvelles formules asymptotiques, ainsi qu'à la simplification, l'unification et la généralisation de divers résultats jusqu'alors isolés.

Cette thèse s'inscrit dans l'étude des graphes infinis de présentation finie. Nous nous intéressons à la fois à leurs propriétés logiques et aux langages qui leur sont associés. Nous nous concentrons sur l'étude des graphes infinis associés aux automates à pile d'ordre supérieur. Notre première contribution est la définition d'une notion de rationalité pour les piles d'ordre supérieur. Nous montrons que cette notion partage de nombreuses propriétés de la rationalité sur les mots : clôture par complémentaire, accepteurs déterministes et complets, et caractérisation en logique du second ordre monadique. Nous établissons un lien étroit entre les automates à pile d'ordre supérieur et les ensembles rationnels de piles d'ordre supérieur. Notre seconde contribution est l'étude structurelle des graphes associés à ces automates. Nous en donnons différentes caractérisations qui montrent la robustesse de ces familles de graphes infinis.