Théorie des graphesvignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.
Line graphEn théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.
Graphe (mathématiques discrètes)Dans le domaine des mathématiques discrètes, la théorie des graphes définit le graphe, une structure composée d'objets et de relations entre deux de ces objets. Abstraitement, lesdits objets sont appelés sommets (ou nœuds ou points), et les relations entre eux sont nommées arêtes (ou liens ou lignes). On distingue les graphes non orientés, où les arêtes relient deux sommets de manière symétrique, et les graphes orientés, où les arêtes, alors appelées arcs (ou flèches), relient deux sommets de manière asymétrique.
Partitionnement de donnéesvignette|upright=1.2|Exemple de clustering hiérarchique. Le partitionnement de données (ou data clustering en anglais) est une méthode en analyse des données. Elle vise à diviser un ensemble de données en différents « paquets » homogènes, en ce sens que les données de chaque sous-ensemble partagent des caractéristiques communes, qui correspondent le plus souvent à des critères de proximité (similarité informatique) que l'on définit en introduisant des mesures et classes de distance entre objets.
Cluster graphIn graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster graphs are also called P_3-free graphs. They are the complement graphs of the complete multipartite graphs and the 2-leaf powers. The cluster graphs are transitively closed, and every transitively closed undirected graph is a cluster graph.
Mineur (théorie des graphes)La notion de mineur d'un graphe est un concept de théorie des graphes. Il a été défini et étudié par Robertson et Seymour dans une série d'articles intitulée Graph minors (I à XXIII), publiée dans le Journal of Combinatorial Theory entre 1983 et 2011. Soit un graphe non orienté fini. Un graphe est un mineur de s'il peut être obtenu en contractant des arêtes d'un sous-graphe de .
Partitionnement de grapheEn théorie des graphes et en algorithmique, le partitionnement de graphe est la tâche qui consiste à diviser un graphe orienté ou non orienté en plusieurs parties. Plusieurs propriétés peuvent être recherchées pour ce découpage, par exemple on peut minimiser le nombre d'arêtes liant deux parties différentes. Coupe maximum et Coupe minimum sont deux exemples communs de partitionnement de graphe. Une partition d'un graphe est une partition de ses nœuds, ou plus rarement de ses arêtes.
Graphe (type abstrait)thumb|upright=1.3|Un graphe orienté, dont les arcs et certains sommets sont « valués » par des couleurs. En informatique, et plus particulièrement en génie logiciel, le type abstrait graphe est la spécification formelle des données qui définissent l'objet mathématique graphe et de l'ensemble des opérations qu'on peut effectuer sur elles. On qualifie d'« abstrait » ce type de données car il correspond à un cahier des charges qu'une structure de données concrète doit ensuite implémenter.
Invariant de grapheEn théorie des graphes, un invariant de graphe est une quantité qui n'est pas modifiée par isomorphisme de graphes. Un invariant de graphe ne dépend donc que de la structure abstraite et pas des particularités de la représentation comme l'étiquetage ou le tracé. De nombreux invariants sont conservés par certains préordres ou ordres partiels naturels sur les graphes : Une propriété est monotone si elle est héritée par les sous-graphes. Le caractère biparti, sans triangle, ou planaire sont des exemples de propriétés monotones.
Graphe planaireDans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs.
Implicit graphIn the study of graph algorithms, an implicit graph representation (or more simply implicit graph) is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from some other input, for example a computable function. The notion of an implicit graph is common in various search algorithms which are described in terms of graphs. In this context, an implicit graph may be defined as a set of rules to define all neighbors for any specified vertex.
Partitionnement spectralEn informatique théorique, le partitionnement spectral ou spectral clustering en anglais, est un type de partitionnement de données prenant en compte les propriétés spectrales de l'entrée. Le partitionnement spectral utilise le plus souvent les vecteurs propres d'une matrice de similarités. Par rapport à des algorithmes classiques comme celui des k-moyennes, cette technique offre l'avantage de classer des ensembles de données de structure « non-globulaire », dans un espace de représentation adéquat.
Graphe cordalthumb|Un cycle, en noir, avec deux cordes, en vert. Si l'on s'en tient à cette partie, le graphe est cordal. Supprimer l'une des arêtes vertes rendrait le graphe non cordal. En effet, l'autre arête verte formerait, avec les trois arêtes noires, un cycle de longueur 4 sans corde. En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle.
Graph rewritingIn computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically. It has numerous applications, ranging from software engineering (software construction and also software verification) to layout algorithms and picture generation. Graph transformations can be used as a computation abstraction. The basic idea is that if the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph.
Graphe grilleIn graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space \mathbb{R}^n, forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lattice in the group-theoretical sense. Typically, no clear distinction is made between such a graph in the more abstract sense of graph theory, and its drawing in space (often the plane or 3D space). This type of graph may more shortly be called just a lattice, mesh, or grid.
Component (graph theory)In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices.
Graphe nulEn mathématiques, plus spécialement en théorie des graphes, un graphe nul désigne soit un graphe d'ordre zéro (i.e. sans sommets), soit un graphe avec sommets mais sans arêtes (on parle aussi dans ce dernier cas de graphe vide). Lorsqu'un graphe nul contient des sommets tous isolés, on le note où représente le nombre de sommets du graphe. La taille (i.e. le nombre d'arêtes ou d'arcs) d'un graphe nul est toujours zéro. L'ordre (i.e. le nombre de sommets) d'un graphe nul n'est pas nécessairement zéro.
Graphe complémentaireframe|right|Le graphe de Petersen, à gauche et son complémentaire, à droite. En théorie des graphes, le graphe complémentaire ou graphe inversé d'un graphe simple est un graphe simple ayant les mêmes sommets et tel que deux sommets distincts de soient adjacents si et seulement s'ils ne sont pas adjacents dans . Le graphe complémentaire ne doit pas être confondu avec le complémentaire dans le sens de la théorie des ensembles. En effet, l'ensemble des sommets de G reste inchangé. Le complémentaire du complémentaire est le graphe original.
Graph structure theoremIn mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Its proof is very long and involved. and are surveys accessible to nonspecialists, describing the theorem and its consequences. A minor of a graph G is any graph H that is isomorphic to a graph that can be obtained from a subgraph of G by contracting some edges.
Base de données orientée grapheUne base de données orientée graphe est une base de données orientée objet utilisant la théorie des graphes, donc avec des nœuds et des arcs, permettant de représenter et stocker les données. Par définition, une base de données orientée graphe correspond à un système de stockage capable de fournir une adjacence entre éléments voisins : chaque voisin d'une entité est accessible grâce à un pointeur physique. C'est une base de données orientée objet adaptée à l'exploitation des structures de données de type graphe ou dérivée, comme des arbres.
