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.
Nombre de Hadwigervignette|upright=1.4|Un graphe avec quatre sous-graphes connectés qui, lorsqu'ils sont contractés, forment un graphe complet. Il ne possède pas de mineur complet à cinq sommets par le théorème de Wagner, donc son nombre de Hadwiger est exactement quatre. En théorie des graphes, le nombre de Hadwiger d'un graphe non orienté G est la taille du plus grand graphe complet qui peut être obtenu en contractant des arêtes de G. De manière équivalente, le nombre de Hadwiger h(G) est le plus grand entier k pour lequel le graphe complet K k est un mineur de G.
Total coloringIn graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges, no adjacent vertices and no edge and either endvertex are assigned the same color. The total chromatic number χ′′(G) of a graph G is the fewest colors needed in any total coloring of G.
Calcul distribuéUn calcul distribué, ou réparti ou encore partagé, est un calcul ou un traitement réparti sur plusieurs microprocesseurs et plus généralement sur plusieurs unités centrales informatiques, et on parle alors d'architecture distribuée ou de système distribué. Le calcul distribué est souvent réalisé sur des clusters de calcul spécialisés, mais peut aussi être réalisé sur des stations informatiques individuelles à plusieurs cœurs. La distribution d'un calcul est un domaine de recherche des sciences mathématiques et informatiques.
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.
Morphisme de graphesUn morphisme de graphes ou homomorphisme de graphes est une application entre deux graphes (orientés ou non orientés) qui respecte la structure de ces graphes. Autrement dit l'image d'un graphe dans un graphe doit respecter les relations d'adjacence présentes dans . thumb|alt=Un homomorphisme entre deux graphes|Le graphe de gauche se projette dans le graphe de droite, par exemple de cette façon là Si et sont deux graphes dont on note les sommets V(G) et V(H) et les arêtes E(G) et E(H), une application qui envoie les sommets de G sur ceux de H est un morphisme de graphes si : , .
Polynôme chromatiqueEn mathématiques, plus particulièrement en théorie des graphes, le polynôme chromatique d'un graphe est une fonction polynômiale donnant le nombre de colorations distinctes d'un graphe, en fonction du nombre de couleurs autorisées. Il a été introduit d'abord en 1912 pour les graphes planaires, par George David Birkhoff, qui cherchait à démontrer le théorème des quatre couleurs. Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs au nombre chromatique du graphe et a pour degré l'ordre du graphe.
Graphe de PetersenLe graphe de Petersen est, en théorie des graphes, un graphe particulier possédant et . Il s'agit d'un petit graphe qui sert d'exemple et de contre-exemple pour plusieurs problèmes de la théorie des graphes. Il porte le nom du mathématicien Julius Petersen, qui l'introduisit en 1898 en tant que plus petit graphe cubique sans isthme dont les arêtes ne peuvent être colorées avec trois couleurs. Il a cependant été mentionné par Alfred Kempe pour la première fois auparavant, en 1886.
Largeur de cliquevignette|upright=1.6|Construction d'un graphe (ici un graphe à distance héréditaire) de largeur de clique 3 par une succession d'unions disjointes, de renommages et de fusions d'étiquettes. Les étiquettes des sommets sont affichées sous forme de couleurs. En théorie des graphes, la largeur de clique d'un graphe est l'un des paramètres qui décrit la complexité structurelle du graphe ; il est étroitement lié à largeur arborescente, mais contrairement à celle-ci, elle peut être bornée même pour des graphes denses .
Graphe dualEn théorie des graphes, le graphe dual d'un graphe plongé dans une surface est défini à l'aide des composantes de son complémentaire, lesquelles sont reliées entre elles par les arêtes du graphe de départ. Cette notion généralise celle de dualité dans les polyèdres. Il faut noter qu'un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan. Un graphe (plongé) isomorphe à son dual est dit autodual.
