Mixed graphIn graph theory, a mixed graph G = (V, E, A) is a graph consisting of a set of vertices V, a set of (undirected) edges E, and a set of directed edges (or arcs) A. Consider adjacent vertices . A directed edge, called an arc, is an edge with an orientation and can be denoted as or (note that is the tail and is the head of the arc). Also, an undirected edge, or edge, is an edge with no orientation and can be denoted as or . For the purpose of our application example we will not be considering loops or multiple edges of mixed graphs.
Graphe de CayleyEn mathématiques, un graphe de Cayley (du nom d'Arthur Cayley) est un graphe qui encode la structure d'un groupe. C'est un outil important pour l'étude de la combinatoire et de la géométrie des groupes. Étant donné un groupe et une partie génératrice de ce groupe, le graphe de Cayley Cay(G,S) est construit comme suit : À chaque élément de , on associe un sommet . À chaque élément de , on associe une couleur . Pour tout et , on trace une arête orientée de couleur du sommet vers le sommet .
Graphe planaire extérieurvignette|Un graphe planaire extérieur maximal, muni d'une 3-coloration. En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes.
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.
Graphe régulierEn théorie des graphes, un graphe régulier est un graphe où tous les sommets ont le même nombre de voisins, c'est-à-dire le même degré ou valence. Un graphe régulier dont les sommets sont de degré est appelé un graphe -régulier ou graphe régulier de degré . Un graphe 0-régulier est un ensemble de sommets déconnectés; un graphe 1-régulier a un nombre pair de sommets et est un ensemble d'arêtes déconnectées ou couplage; enfin, un graphe 2-régulier est un ensemble de cycles déconnectés.
Graphe fortement régulierEn théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe régulier. Soit G = (V,E) un graphe régulier ayant v sommets et degré k. On dit que G est fortement régulier s'il existe deux entiers λ et μ tels que Toute paire de sommets adjacents a exactement λ voisins communs. Toute paire de sommets non-adjacents a exactement μ voisins communs. Un graphe avec ces propriétés est appelé un graphe fortement régulier de type (v,k,λ,μ).
Graphe distance-régulierEn théorie des graphes, un graphe régulier est dit distance-régulier si pour tous sommets distants de , et pour tous entiers naturels , il y a toujours le même nombre de sommets qui sont à la fois à distance de et à distance de . De manière équivalente, un graphe est distance-régulier si pour tous sommets , le nombre de sommets voisins de à distance de et le nombre de sommets voisins de à distance de ne dépendent que de et de la distance entre et . Formellement, tels que et où est l’ensemble des sommets à distance de , et .
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.
Graphe biparti completEn théorie des graphes, un graphe est dit biparti complet (ou encore est appelé une biclique) s'il est biparti et chaque sommet du premier ensemble est relié à tous les sommets du second ensemble. Plus précisément, il existe une partition de son ensemble de sommets en deux sous-ensembles et telle que chaque sommet de est relié à chaque sommet de . Si le premier ensemble est de cardinal m et le second ensemble est de cardinal n, le graphe biparti complet est noté . Si m = 1, le graphe complet biparti K1,n est une étoile et est noté .
Voisinage (théorie des graphes)En théorie des graphes on dit que deux sommets d'un graphe non-orienté sont voisins ou adjacents s'ils sont reliés par une arête. Le voisinage d'un sommet peut désigner l'ensemble de ses sommets voisins ou bien un sous-graphe associé, par exemple le sous-graphe induit. Dans un graphe orienté, on emploie généralement le terme de prédécesseur ou de successeur. Dans un graphe non orienté , le voisinage d'un sommet , souvent noté (N pour neighbourhood) peut désigner plusieurs choses : L'ensemble des sommets voisins : Les sous-graphe de induit par les sommets précédents, avec ou sans selon les versions.
Densité d'un grapheEn mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe. Ce paramètre mesure si le graphe a beaucoup d'arêtes ou peu. Un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal, par exemple un nombre quadratique par rapport au nombre de sommets. Un graphe creux (sparse graph) a au contraire peu d'arêtes, par exemple un nombre linéaire. La distinction entre graphe creux et dense est plutôt vague et dépend du contexte.
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.
Graphe cactusvignette|upright=1.4| Un graphe cactus. En théorie des graphes, un graphe cactus (parfois appelé arbre cactus) est un graphe connexe dans lequel deux cycles simples quelconques ont au plus un sommet en commun. De manière équivalente, c'est un graphe connexe dans lequel chaque arête appartient à au plus un cycle simple, ou (pour les cactus non triviaux) dans lequel chaque bloc (sous-graphe maximal sans point d'articulation) est une arête ou un cycle.
List of graphsThis partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer.
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.
HypergrapheLes hypergraphes sont des objets mathématiques généralisant la notion de graphe. Ils ont été nommés ainsi par Claude Berge dans les années 1960. Les hypergraphes généralisent la notion de graphe non orienté dans le sens où les arêtes ne relient plus un ou deux sommets, mais un nombre quelconque de sommets (compris entre un et le nombre de sommets de l’hypergraphe). Certains théorèmes de la théorie des graphes se généralisent naturellement aux hypergraphes, par exemple le théorème de Ramsey.
Eulerian pathIn graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this: Given the graph in the image, is it possible to construct a path (or a cycle; i.
Optimisation linéairethumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes.
Polynôme de TutteLe polynôme de Tutte, aussi appelé polynôme dichromatique ou polynôme de Tutte–Whitney, est un polynôme invariant de graphes dont les valeurs expriment des propriétés d'un graphe. C'est un polynôme en deux variables qui joue un rôle important en théorie des graphes et en combinatoire. Il est défini pour tout graphe non orienté et contient des informations liées à ses propriétés de connexité. L'importance de ce polynôme provient des informations qu'il contient sur le graphe .
Problème NP-completEn théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l
