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.
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.
Connectivity (graph theory)In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.
Tracé de graphesEn théorie des graphes, le tracé de graphes consiste à représenter des graphes dans le plan. Le tracé de graphes est utile à des applications telles que la conception de circuits VLSI, l'analyse de réseaux sociaux, la cartographie, et la bio-informatique. Les graphes sont généralement représentés en utilisant des points, disques ou boites pour représenter les sommets, et des courbes ou des segments pour représenter les arêtes. Pour les graphes orientés, on utilise habituellement ses flèches en bout d'arête pour représenter l'orientation.
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.
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.
Intervalle (mathématiques)En mathématiques, un intervalle (du latin intervallum) est étymologiquement un ensemble ordonné de points compris entre deux bornes. Cette notion première s'est ensuite développée jusqu'à aboutir à la notion topologique de boule d'un espace métrique. Initialement, on appelle intervalle réel un ensemble de nombres délimité par deux nombres réels constituant une borne inférieure et une borne supérieure. Un intervalle contient tous les nombres réels compris entre ces deux bornes.
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.
CourbeEn mathématiques, plus précisément en géométrie, une courbe, ou ligne courbe, est un objet du plan ou de l'espace usuel, similaire à une droite mais non nécessairement linéaire. Par exemple, les cercles, les droites, les segments et les lignes polygonales sont des courbes. La notion générale de courbe se décline en plusieurs objets mathématiques ayant des définitions assez proches : arcs paramétrés, lignes de niveau, sous-variétés de .
Intervalle unitéEn mathématique, l'intervalle unité est l'intervalle fermé [0,1], c'est-à-dire, l'ensemble de tous les nombres réels qui sont supérieurs ou égaux à 0 et inférieurs ou égaux à 1. Il est souvent noté I. Dans la littérature, le terme "intervalle unité" est parfois appliqué à d'autres intervalles : (0,1], [0,1), et (0,1). Cependant, la notation I est généralement réservée à l'intervalle fermé [0,1]. L'intervalle unité est un espace métrique complet.
Graphe d'une fonctionthumb|Représentation du graphe de la fonction . Le graphe d'une fonction f de E dans F est le sous-ensemble G de E×F formé par les couples d'éléments liés par la correspondance : Cet ensemble est appelé le graphe de f parce qu'il permet d'en donner une représentation graphique dans le cas usuel où E et F sont des ensembles de réels : en effet, on peut alors parfois représenter E et F sur deux axes sécants, chaque couple de G peut alors être représenté par un point dans le plan, muni d'un repère défini par les deux axes.
Ensemble de définitionEn mathématiques, l'ensemble de définition (également appelé domaine de définition ou parfois ensemble de départ, voir la discussion plus bas) d'une application ou d'une fonction désigne informellement l'ensemble des entrées acceptées par elle. La terminologie entre ensemble de définition et ensemble de départ diffère si l'on fait la distinction entre la notion de fonction et d'application ou non.
Longueur d'un arcthumb|Camille Jordan est l'auteur de la définition la plus courante de la longueur d'un arc. En géométrie, la question de la longueur d'un arc est simple à concevoir (intuitive). L'idée d'arc correspond à celle d'une ligne, ou d'une trajectoire d'un point dans un plan ou l'espace par exemple. Sa longueur peut être vue comme la distance parcourue par un point matériel suivant cette trajectoire ou encore comme la longueur d'un fil prenant exactement la place de cette ligne. La longueur d'un arc est, soit un nombre positif, soit l'infini.
Fonction (mathématiques)vignette|Diagramme de calcul pour la fonction En mathématiques, une fonction permet de définir un résultat (le plus souvent numérique) pour chaque valeur d’un ensemble appelé domaine. Ce résultat peut être obtenu par une suite de calculs arithmétiques ou par une liste de valeurs, notamment dans le cas de relevé de mesures physiques, ou encore par d’autres procédés comme les résolutions d’équations ou les passages à la limite. Le calcul effectif du résultat ou son approximation repose éventuellement sur l’élaboration de fonction informatique.
Parabolevignette|Une parabole représentée par la fonction f(x)=x. La parabole est une courbe plane, symétrique par rapport à un axe, ayant approximativement la forme d'un U dont les branches s'écarteraient indéfiniment. Cette courbe intervient dans les problèmes les plus élémentaires de mécanique ou de mathématiques. En effet la trajectoire d'un projectile qui n'est soumis qu'à la pesanteur est une parabole, ou encore, en mathématiques, la représentation graphique des polynômes de degré 2 est une parabole.
Parité d'une fonctionEn mathématiques, la parité d'une fonction d'une variable réelle, complexe ou vectorielle est une propriété qui requiert d'abord la symétrie du domaine de définition par rapport à l'origine, puis s'exprime par l'une ou l'autre des relations suivantes : fonction paire : pour tout x du domaine de définition, f (−x) = f (x) ; fonction impaire : pour tout x du domaine de définition, f (−x) = −f (x).
Fonction convexevignette|upright=1.5|droite|Fonction convexe. En mathématiques, une fonction réelle d'une variable réelle est dite convexe : si quels que soient deux points et du graphe de la fonction, le segment est entièrement situé au-dessus du graphe, c’est-à-dire que la courbe représentative de la fonction se situe toujours en dessous de ses cordes ; ou si l'épigraphe de la fonction (l'ensemble des points qui sont au-dessus de son graphe) est un ensemble convexe ; ou si vu d'en dessous, le graphe de la fonction est en bosse.
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 .
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.
