Lexique de la théorie des graphesNOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.
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.
Réseau invariant d'échelleUn réseau invariant d'échelle (ou réseau sans échelle, ou encore scale-free network en anglais) est un réseau dont les degrés suivent une loi de puissance. Plus explicitement, dans un tel réseau, la proportion de nœuds de degré k est proportionnelle à pour grand, où est un paramètre (situé entre 2 et 3 pour la plupart des applications). Beaucoup de réseaux, comme le réseau du web, les réseaux sociaux et les réseaux biologiques semblent se comporter comme des réseaux invariants d'échelle, d'où l'importance de ce modèle.
Distribution des degrésthumb|right|320px|Distribution de degrés intrant/sortant du réseau des liens hypertextes de Wikipedia (échelles logarithmiques) La distribution des degrés est, dans l'étude des graphes et des réseaux, une distribution probabiliste des degrés de chaque sommet du réseau. Le degré d'un sommet est le nombre de liens entre ce sommet et d'autres sommets du graphe. Le degré d'un sommet dans un réseau est égal au nombre de liens ou d'arêtes liant ce sommet à d'autres sommets.
Graphe trivialement parfaitvignette|upright=2| Construction d'un graphe trivialement parfait à partir d'intervalles imbriqués et de la relation d'accessibilité dans un arbre. En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S.
Exposant critiqueLors d'une transition de phase de deuxième ordre, au voisinage du point critique, les systèmes physiques ont des comportements universels en lois de puissances caractérisées par des exposants critiques. Au point critique, un fluide est caractérisé par une température critique et une densité critique . Pour une température légèrement supérieure à (à nombre de particules et volume constants), le système est homogène avec une densité . Pour une température légèrement inférieure à , il y a une séparation de phase entre une phase liquide (de densité ) et une phase gazeuse (de densité ).
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.
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.
Réseau complexeEn théorie des graphes, un réseau complexe est un réseau possédant une architecture et une topologie complexe et irrégulière. Comme tous les réseaux, ils sont composés de nœuds (ou sommets ou points) représentant des objets, interconnectés par des liens (ou arêtes ou lignes). Ces réseaux sont des représentations abstraites des relations principalement présentes dans la vie réelle dans une grande diversité de systèmes biologiques et technologiques.
Giant componentIn network theory, a giant component is a connected component of a given random graph that contains a significant fraction of the entire graph's vertices. More precisely, in graphs drawn randomly from a probability distribution over arbitrarily large graphs, a giant component is a connected component whose fraction of the overall number of vertices is bounded away from zero. In sufficiently dense graphs distributed according to the Erdős–Rényi model, a giant component exists with high probability.
Small-world networkA small-world network is a mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other. Due to this, most neighboring nodes can be reached from every other node by a small number of hops or steps. Specifically, a small-world network is defined to be a network where the typical distance L between two randomly chosen nodes (the number of steps required) grows proportionally to the logarithm of the number of nodes N in the network, that is: while the global clustering coefficient is not small.
