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 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.
Nombre de croisements (théorie des graphes)vignette| Une représentation du graphe de Heawood avec trois croisements. C'est le nombre minimum de croisements parmi toutes les représentations de ce graphe, qui a donc un nombre de croisements . En théorie des graphes, le nombre de croisements d'un graphe G est le plus petit nombre d'intersections d'arêtes d'un tracé du graphe G. Par exemple, un graphe est planaire si et seulement si son nombre de croisements est nul. La détermination du nombre de croisements tient une place importante dans le tracé de graphes.
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 sommet-connexeEn théorie des graphes, un graphe connexe . Un graphe autre qu'un graphe complet est de degré de sommet-connexité k s'il est k-sommet-connexe sans être k+1-sommet-connexe, donc si k est la taille du plus petit sous-ensemble de sommets dont la suppression déconnecte le graphe. Les graphes complets ne sont pas inclus dans cette version de la définition car ils ne peuvent pas être déconnectés en supprimant des sommets. Le graphe complet à n sommets est de degré de connexité n-1.
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.
Coloration de graphethumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.
Degré (théorie des graphes)thumb|Un graphe non orienté où on a indiqué le degré de chaque sommet sur ce sommet. Dans ce graphe, le degré maximal est et le degré minimal est . En mathématiques, et plus particulièrement en théorie des graphes, le degré (ou valence) d'un sommet d'un graphe est le nombre de liens (arêtes ou arcs) reliant ce sommet, avec les boucles comptées deux fois. Le degré d'un sommet est noté . Dans le cas d'un graphe orienté, on parle aussi du degré entrant d'un sommet , c'est-à-dire le nombre d'arcs dirigés vers le sommet , et du degré sortant de ce sommet , c'est-à-dire le nombre d'arcs sortant de .
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 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.
Graphe sans triangleEn théorie des graphes, un graphe sans triangle est un graphe qui ne possède pas de triplet d'arêtes formant un triangle. Le théorème de Mantel, cas particulier du théorème de Turán, est : La famille des graphes sans triangle, contient notamment les graphes acycliques et est contenue dans les graphes sans diamant. Les graphes sans triangle peuvent être reconnus en temps , où est le nombre d'arêtes. De façon plus générale, on peut reconnaître les graphes n'ayant pas de cycles d'une certaine longueur (fixé dans l'algorithme), en temps (avec le nombre de sommets) ou en temps .
Graphe orientéthumb|Un graphe orienté .(Figure 1) Dans la théorie des graphes, un graphe orienté est un couple formé de un ensemble, appelé ensemble de nœuds et un ensemble appelé ensemble d'arêtes. Les arêtes sont alors nommées arcs, chaque arête étant un couple de noeuds, représenté par une flèche. Étant donné un arc , on dit que est l'origine (ou la source ou le départ ou le début) de et que est la cible (ou l'arrivée ou la fin) de . Le demi-degré extérieur (degré sortant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour origine.
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.
Graphe cycleLes graphes cycles, ou n-cycles, forment une famille de graphes. Le graphe cycle est constitué d'un unique cycle élémentaire de longueur n (pour ). C'est un graphe connexe non-orienté d'ordre n à n arêtes. Il est 2-régulier, c'est-à-dire que chacun de ses sommets est de degré 2. Beaucoup de termes sont employés pour désigner le graphe cycle : n-cycle, polygone et n-gone. Le terme de graphe cyclique est parfois employé, mais il pose problème car il s'oppose normalement à graphe acyclique. Nombre chromatique.
Parcours de grapheEn théorie des graphes, un parcours de graphe est un algorithme consistant à explorer les sommets d'un graphe de proche en proche à partir d'un sommet initial. Un cas particulier important est le parcours d'arbre. Le mot parcours est également utilisé dans un sens différent, comme synonyme de chemin (un parcours fermé étant un circuit). Il existe de nombreux algorithmes de parcours. Les plus couramment décrits sont le parcours en profondeur et le parcours en largeur.
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.
Taux d'expansion (théorie des graphes)En mathématiques, et plus particulièrement en théorie des graphes, le taux d'expansion d'un graphe est une mesure de connectivité de ce graphe. Informellement, un grand taux d'expansion veut dire que n'importe quel sous-ensemble de sommets relativement petit possède beaucoup de connexions avec le reste du graphe. Cette mesure est surtout utilisée en raison des propriétés intéressantes des graphes ayant un fort taux d'expansion, parfois appelés graphes expanseurs. On les retrouve notamment en informatique théorique.
Graphe orienté acycliqueEn théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.
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.
Droite (mathématiques)En géométrie, le mot droite désigne un objet formé de points alignés. Une droite est illimitée des deux côtés, et sans épaisseur (dans la pratique, elle est représentée, sur une feuille, par une ligne droite ayant bien entendu des limites — celles de la feuille — et une épaisseur — celle du crayon). Pour les Anciens, la droite était un concept « allant de soi », si « évident » que l'on négligeait de préciser de quoi l'on parlait. L'un des premiers à formaliser la notion de droite fut le Grec Euclide dans ses Éléments.
