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.
Isomorphisme de graphesEn mathématiques, dans le cadre de la théorie des graphes, un isomorphisme de graphes est une bijection entre les sommets de deux graphes qui préserve les arêtes. Ce concept est en accord avec la notion générale d'isomorphisme, une bijection qui préserve les structures. Plus précisément, un isomorphisme f entre les graphes G et H est une bijection entre les sommets de G et ceux de H, telle qu'une paire de sommets {u, v} de G est une arête de G si et seulement si {ƒ(u), ƒ(v)} est une arête de H.
Théorie spectrale des graphesEn mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée. Soit un graphe , où désigne l'ensemble des sommets et l'ensemble des arêtes. Le graphe possède sommets, notés et arêtes, notées .
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 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 .
Distance (théorie des graphes)En théorie des graphes, la distance entre deux nœuds d'un graphe est la longueur d'un plus court chemin entre ces deux nœuds. La longueur d'un chemin est sa longueur en nombre d'arêtes. Pour un graphe pondéré c'est la somme des poids des arêtes empruntées. Pour les graphes non orientés, c'est une distance au sens mathématique, tandis que pour les graphes orientés elle ne vérifie pas la propriété de symétrie. Cette notion permet entre autres de définir le diamètre et le rayon d'un graphe. Catégorie:Concept
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.
Graphe distance-unitéEn mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe s'obtenant à partir d'un ensemble de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1. Les arêtes peuvent se croiser si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. S'il n'y a pas de croisement entre les arêtes, alors le graphe est qualifié de graphe allumette.
Graphe aléatoirevignette|Graphe orienté aléatoire avec 20 nœuds et une probabilité de présence d'arête égale à 0,1. En mathématiques, un graphe aléatoire est un graphe généré par un processus aléatoire. Le premier modèle de graphes aléatoires a été popularisé par Paul Erdős et Alfréd Rényi dans une série d'articles publiés entre 1959 et 1968. Il y a deux modèles d'Erdős et Rényi, formellement différents, mais étroitement liés : le graphe aléatoire binomial et le graphe aléatoire uniforme.
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.
