La reconnaissance de formes s'intéresse à la détection automatique de motifs dans des données d'entrée, afin de pouvoir, par exemple, les classer en catégories. La matière première de ces techniques est bien souvent l'image numérique. Cette dernière, dans sa forme la plus courante, est codée sous la forme d'une matrice de pixels. Néanmoins, la question du développement de représentations plus riches se pose. Ainsi, la structuration de l'information contenue dans l'image devrait permettre la mise en évidence des différents objets représentés, et des liens les unissant. C'est pourquoi nous proposons de modéliser les images numériques sous forme de graphes, pour leur richesse et expressivité d'une part, et pour exploiter les résultats de la théorie des graphes en reconnaissance de formes d'autre part. Nous développons pour cela une méthode d'extraction de graphes plans à partir d'images, basée sur le respect de la sémantique. Nous montrons que nous pouvons, étant donné un graphe, reconstruire avec perte limitée l'image d'origine. Par la suite, nous introduisons les graphes plans à trous, graphes dont les faces peuvent être visibles ou invisibles. Leur justification trouve sa place dans la recherche de motifs notamment, pour laquelle les éléments constituant l'arrière-plan d'une image ne doivent pas être retrouvés. En dirigeant notre attention sur la planarité de ces graphes, nous proposons des algorithmes polynomiaux d'isomorphisme de graphes plans et de motifs ; nous traitons également leur équivalence, qui se trouve être un isomorphisme aux faces invisibles près

.

.

Avec des volumes de données et d’informations de plus en plus importants, des données de plus en plus complexes et fortement inter-reliées, l’extraction de connaissances reste un véritable défi. Les graphes offrent actuellement un support de représentation efficace pour représenter ces données. Parmi les approches existantes, les multi-graphes ont montré que leur pouvoir d’expression était particulièrement adapté pour manipuler des données complexes possédant de nombreux types de relations entre elles. Cette thèse aborde deux aspects principaux liés aux multigraphes : la recherche de sous graphes et la fouille de sous graphes fréquents dans des multigraphes.Elle propose trois propositions dans le domaines du requêtage et de la fouille de données.La première contribution s’inscrit dans la recherche de sous graphes et concerne l’isomorphisme de sous graphes dans des multigraphes. Cette approche peut, par exemple, être appliquée dans de nombreux domaines d’applications comme l’analyse d’images satellites ou de réseaux sociaux. Dans la seconde, nous nous intéressons aux graphes de connaissances et abordons la problématique de l’homorphisme de graphes dans des multigraphes RDF. Dans les deux contributions, nous proposons de nouvelles techniques d’indexations pour représenter efficacement les informations contenues dans les multigraphes. La recherche des sous graphes tire avantage de ces nouveaux index et différentes heuristiques et optimisations sont également proposées pour garantir de bonnes performances lors de l’exécution des requêtes. La seconde contribution s’inscrit dans le domaine de la fouille de données et nous proposons un algorithme efficace pour extraire les multigraphes fréquents. Etant donné l’espace de recherche à considérer, la recherche de motifs fréquents dans des graphes est un problème difficile en fouille de données. Pour parcourir efficacement l’espace de recherche encore plus volumineux pour les multigraphes, nous proposons de nouvelles techniques et méthodes pour le traverser efficacement notamment en éliminant des candidats où détectant à l’avance les motifs non fréquents. Pour chacune de ces propositions de nombreuses expérimentations sont réalisées pour valider à la fois leurs performances et exactitudes en les comparant avec les approches existantes. Finalement, nous proposons une étude de cas sur des jeux de données issues d’images satellites modélisées sous la forme de multigraphe et montrons que l’application de nos propositions permet de mettre en évidence de nouvelles connaissances utiles. / With the ever-increasing growth of data and information, extracting the right knowledge has become a real challenge.Further, the advanced applications demand the analysis of complex, interrelated data which cannot be adequately described using a propositional representation. The graph representation is of great interest for the knowledge extraction community, since graphs are versatile data structures and are one of the most general forms of data representation. Among several classes of graphs, textit{multigraphs} have been captivating the attention in the recent times, thanks to their inherent property of succinctly representing the entities by allowing the rich and complex relations among them.The focus of this thesis is streamlined into two themes of knowledge extraction; one being textit{knowledge retrieval}, where we focus on the subgraph query matching aspects in multigraphs, and the other being textit{knowledge discovery}, where we focus on the problem of frequent pattern mining in multigraphs.This thesis makes three main contributions in the field of query matching and data mining.The first contribution, which is very generic, addresses querying subgraphs in multigraphs that yields isomorphic matches, and this problem finds potential applications in the domains of remote sensing, social networks, bioinformatics, chemical informatics. The second contribution, which is focussed on knowledge graphs, addresses querying subgraphs in RDF multigraphs that yield homomorphic matches. In both the contributions, we introduce efficient indexing structures that capture the multiedge information. The query matching processes introduced have been carefully optimized, w.r.t. the time performance and the heuristics employed assure robust performance.The third contribution is in the field of data mining, where we propose an efficient frequent pattern mining algorithm for multigraphs. We observe that multigraphs pose challenges while exploring the search space, and hence we introduce novel optimization techniques and heuristic search methods to swiftly traverse the search space.For each proposed approach, we perform extensive experimental analysis by comparing with the existing state-of-the-art approaches in order to validate the performance and correctness of our approaches.In the end, we perform a case study analysis on a remote sensing dataset. Remote sensing dataset is modelled as a multigraph, and the mining and query matching processes are employed to discover some useful knowledge.

Les graphes définis à partir de structures algébriques possèdent d’excellentes propriétés de symétries particulièrement intéressantes. L’exemple le plus flagrant est la notion de graphe de Cayley qui s’est révélée très riche non seulement du point de vue théorique mais aussi pratique par ses applications à de nombreux domaines incluant l’architecture des réseaux ou les machines parallèles. Néanmoins, la régularité des graphes de Cayley se révèle parfois être une limite étant donné qu’ils sont toujours sommet-transitifs et donc en particulier non pertinents pour générer des réseaux semiréguliers.Cette observation a motivé, en 2005, la définition d’une nouvelle classe de graphes définis à partir d’un groupe, appelés G-graphes. Ils possèdent aussi de nombreuses propriétés de régularité mais de manière moins restrictive.Cette thèse propose un nouveau regard sur cette classe de graphes par une approche plutôt orientée recherche opérationnelle alors que la grande majorité des études précédentes est dominée par des approches essentiellement algébriques. Nous-nous sommes alors intéressés à plusieurs questions :— La caractérisation des G-graphes : nous proposons des améliorations par rapport aux précédents résultats.— Identifier des classes de graphes comme des G-graphes grâce à des isomorphismes ou en utilisant le théorème de caractérisation.— Etudier la structure et les propriétés de ces graphes, en particulier pour de possibles applications aux réseaux : colorations semi-régulières, symétries et robustesse.— Une approche algorithmique pour la reconnaissance de cette classe avec notamment un premier exemple de cas polynomial lorsque le groupe est abélien. / Interactions between graph theory and group theory have already led to interesting results for both domains. Graphs defined from algebraic groups have highly symmetrical structure giving birth to interesting properties. The most famous example is Cayley graphs, which revealed to be particularly interesting both from a theoretical and a practical point of view due to their applications in several domains including network architecture or parallel machines. Nevertheless, the regularity of Cayley graphs is also a limit as they are always vertex-transitive and therefore not relevant to generate semi-regular networks. This observation motivated the definition, in 2005, of a new family of graphs defined from a group, called G-graphs. They also have many regular properties but are less restrictive. These graphs are in particular semi-regular k-partite, with a chromatic number k directly given in the group representation and they can be either transitive or not.This thesis proposes a new insight into this class of graphs using an approach based on operational research while most of previous studies have been so far dominated by algebraic approaches. Then, the thesis addresses different kind of questions:— Characterizing G-graphs: we propose improvements of previous results.— Identifying some classes of graphs as G-graphs through isomorphism or using the characterization theorem.— Studying the structure and properties of these graphs, in particular for possible applications to networks: semi-regular coloring, symmetries and robustness.— Algorithmic approach for recognizing this class with a first example of polynomial case when the group is abelian.

Dans la pratique, énormément de problèmes concrets peuvent être modélisés par un graphe. Par exemple, une carte géographique est typiquement un graphe dans lequel on serait amener à chercher des chemins courts entre les villes, ou à passer par toutes les routes ou toutes les villes.... Cela explique pourquoi la théorie des graphes est certainement le domaine le plus populaire des mathématiques discrètes malgré son jeune âge....

Sur la base de recherches à caractère expérimental, nous revisitons et approfondissons le paradigme de la consistance cognitive. Contrairement à ce que prévoient les théories de la consistance, nous montrons que, non seulement les gens ne présentent pas systématiquement des structures cognitives consistantes, mais aussi qu’ils se défendent fort peu face à des « agressions » idéologiques induisant de l’inconsistance. Nous expliquons ces observations, par le fait que la consistance n’est une valeur cognitive que dans des univers de croyances dotés d’une pertinence minimale. Par ailleurs, l’étude de la consistance cognitive donne lieu à la comparaison du formalisme classique des graphes et d’un formalisme nouveau : le graphe des parentés. Ces deux derniers convergent sur les indices de consistance. Le graphe des parentés met en évidence deux nouveaux indices : l’assimilation et la disjonction. Leur analyse donne lieu à une interprétation psychologique. / Based on experimental research we reviewed and thoroughly examined the paradigm of cognitive consistency. In contrast with various consistence theory predictions, we showed that people are not systematically endowed with consistent cognitive structures and do not defend themselves very carefully against ideological “aggressions” inducing inconsistency. We explained these findings by the fact that consistency has a cognitive value only in self relevant fields. On the other hand, studies on cognitive consistency gave rise to comparisons between classical formalism of graphs and a new formalism one: the graph of relationships. Both graphs converge on consistency factors. The graph of relationships underlies two new factors: assimilation and disjunction. Their analysis gave rise to psychological interpretations.

Un graphe est un ensemble de noeuds, ensemble de liens reliant des paires de noeuds. Avec la quantité accumulée de données collectées, il existe un intérêt croissant pour la compréhension des structures et du comportement de très grands graphes. Néanmoins, l’augmentation rapide de la taille des grands graphes rend l’étude de tous les graphes de moins en moins efficace. Ainsi, il existe une demande impérieuse pour des méthodes plus efficaces pour étudier de grands graphes sans nécessiter la connaissance de tous les graphes. Une méthode prometteuse pour comprendre le comportement de grands graphes consiste à exploiter des propriétés spécifiques de structures locales, telles que la taille des grappes ou la présence locale d’un motif spécifique, c’est-à-dire un graphe donné (généralement petit). Un exemple classique de la théorie des graphes (cas avérés de la conjecture d'Erdos-Hajnal) est que, si un graphe de grande taille ne contient pas de motif spécifique, il doit alors avoir un ensemble de noeuds liés par paires ou non liés, de taille exponentiellement plus grande que prévue. Cette thèse abordera certains aspects de deux questions fondamentales de la théorie des graphes concernant la présence, en abondance ou à peine, d’un motif donné dans un grand graphe : - Le grand graphe peut-il être partitionné en copies du motif ? - Le grand graphe contient-il une copie du motif ? Nous discuterons de certaines des conjectures les plus connues de la théorie des graphes sur ce sujet: les conjectures de Tutte sur les flots dans les graphes et la conjecture d'Erdos-Hajnal mentionnée ci-dessus, et présenterons des preuves pour plusieurs conjectures connexes - y compris la conjecture de Barát-Thomassen, une conjecture de Haggkvist et Krissell, un cas particulier de la conjecture de Jaeger-Linial-Payan-Tarsi, une conjecture de Berger et al, et une autre d'Albouker et al. / A graph is a set of nodes, together links connecting pairs of nodes. With the accumulating amount of data collected, there is a growing interest in understanding the structures and behavior of very large graphs. Nevertheless, the rapid increasing in size of large graphs makes studying the entire graphs becomes less and less efficient. Thus, there is a compelling demand for more effective methods to study large graphs without requiring the knowledge of the graphs in whole. One promising method to understand the behavior of large graphs is via exploiting specific properties of local structures, such as the size of clusters or the presence locally of some specific pattern, i.e. a given (usually small) graph. A classical example from Graph Theory (proven cases of the Erdos-Hajnal conjecture) is that if a large graph does not contain some specific pattern, then it must have a set of nodes pairwise linked or not linked of size exponentially larger than expected. This thesis will address some aspects of two fundamental questions in Graph Theory about the presence, abundantly or scarcely, of a given pattern in some large graph: - Can the large graph be partitioned into copies of the pattern? - Does the large graph contain any copy of the pattern?We will discuss some of the most well-known conjectures in Graph Theory on this topic: the Tutte's flow conjectures on flows in graphs and the Erdos-Hajnal conjecture mentioned above, and present proofs for several related conjectures -- including the Barát-Thomassen conjecture, a conjecture of Haggkvist and Krissell, a special case of Jaeger-Linial-Payan-Tarsi's conjecture, a conjecture of Berger et al, and another one by Albouker et al.

Ce document présente une vue synthétique de mes travaux de recherche menés ces cinq dernières années, au sein du LaBRI.<br />Les activités de recherche d'un enseignant-chercheur ne s'inscrivent pas souvent dans un plan de recherche soigneusement pensé. Elles évoluent en fonction de multiples impondérables, dont notamment les rencontres avec d'autres chercheurs ou encore les opportunités ``stratégiques'' de financement. De ce fait, il n'est pas toujours facile de dégager un fil conducteur qui permette de regrouper un ensemble des résultats obtenus ``au fil de l'eau'' sans avoir recours à des raccourcis un peu ``artificiels''. <br /><br />Lorsque je me suis efforcé de dégager un point commun à mes travaux, je me suis aperçu que des objets mathématiques bien particuliers n'étaient jamais très loin de mes activités: les groupes cycliques finis. En creusant un peu plus cette perception, il m'est apparu que mes travaux accordent une place considérable à des graphes élémentaires associés aux groupes cycliques, dits graphes ou encore webs.<br /><br />Ce document est donc consacré à la mise en valeur des multiples facettes de ces graphes. ``Facettes'' est ici à double sens, puisqu'une partie conséquente de mes résultats est précisément dédiée à la détermination des facettes de certains polytopes associés aux graphes!<br /><br />Sur la forme, les preuves ont été omises afin d'alléger le texte, à l'exception de quelques preuves sélectionnées pour leur brièveté et pour la pertinence du résultat qu'elles procurent. Des hyperliens pointent vers la version anglaise des preuves manquantes, telles qu'elles figurent dans le recueil d'articles en annexe. Pour faciliter également la lecture, l'index à la fin de l'ouvrage redonne toutes les principales définitions.<br /><br />Sur le fond, ce document est structuré de la manière suivante.<br /><br />Le premier chapitre est consacré aux principaux résultats connus sur les graphes parfaits. Ceci permet de définir les objets mathématiques utilisés par la suite, et de rappeler l'extraordinaire richesse conceptuelle des graphes parfaits.<br /><br />Dans le second chapitre, nous abordons un raffinement de la coloration usuelles des graphes, appelé ``coloration circulaire''. Cette coloration est à l'origine d'une généralisation récente des graphes parfaits: les ``graphes circulaires-parfaits''. Nous étudions la possibilité d'une caractérisation analogue à celles des graphes parfaits, que ce soit par sous-graphes exclus ou bien polyédrale. <br /><br />Dans le troisième chapitre, nous nous intéressons à une généralisation naturelle des webs: ``les graphes quasi-adjoints''. Il s'agit d'une sous-famille des graphes sans griffe, et à ce titre, l'étude de leur polytope des stables est de première importance.<br /><br />Dans le quatrième chapitre, nous menons des investigations directes sur le polytope des stables des graphes sans griffe.<br /><br />La conclusion est donnée dans le dernier et cinquième chapitre, qui contient également une brève présentation de quelques résultats préliminaires quant au calcul en temps polynomial du nombre circulaire-chromatique des graphes circulaires-parfaits et au calcul du nombre de stabilité des graphes quasi-adjoints. Tout repose sur l'introduction d'un nouveau polytope construit à partir des webs ...

Rappels sur les graphes topologiques et les propriétés algébriques des constellations. Triangulations minimales de surfaces orientables : étude des constellations dans le cas des triangulations et methode permettant de trouver de nouvelles triangulations minimales de surfaces orientables. On étudie une classe particulière de graphes pour lesquels le nombre minimum de faces d'une immersion 2-cellulaire dans une surface orientable est 1 ou 2 : les graphes sup-immergeables.