A 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. Adjacence une relation d'adjacence propriété de deux sommets d'être connectés par la même arête (dits sommets adjacents) ou propriété de deux arêtes de présenter une extrémité commune (dites arêtes adjacentes). Également appelé relation de voisinage. Adjoint un graphe adjoint est synonyme de line graph. Admittance autre nom d'une matrice laplacienne. Aléatoire un graphe est aléatoire, ou non déterministe, dès que sa construction fait intervenir des probabilités. Arbre graphe connexe et acyclique. Équivalent à un graphe connexe à sommets et arêtes. Arbre enraciné ou arborescence graphe acyclique orienté où on distingue une racine de degré entrant nul, et où tous les autres sommets sont de degré entrant 1. Arc arête dans un graphe orienté. Autre formulation : couple (ensemble ordonné de deux éléments) de sommets reliés par une arête dans un graphe non orienté. Arc-transitif un graphe G est arc-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses arcs. Étant donné deux arêtes , il existe deux automorphismes et tels que , , et , , , . Arête connexion entre deux sommets et . Dans le cas des graphes orientés on parle d'arc. Le terme « arête » est alors utilisé pour désigner l'ensemble des deux arcs , c'est-à-dire de vers , et , c'est-à-dire de vers . Ne pas confondre avec arête en géométrie. Arête multiple ensemble d'arêtes parallèles relatif à un couple de sommets. Arête parallèle arête ayant pour extrémités les mêmes sommets qu'une autre arête. On parle d'arêtes parallèles. Arête-transitif un graphe est arête-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses arêtes. Autre formulation de la condition : pour tout couple d'arêtes, au moins un automorphisme envoie la première composante sur la seconde. Toutes les arêtes jouent exactement le même rôle à l'intérieur du graphe. Exemple : un graphe complet. Automorphisme isomorphisme d'un graphe sur lui-même. Chaque graphe possède au moins un automorphisme : l'identité. L'ensemble des automorphismes d'un graphe forme un groupe.
B Biconnexe un graphe non orienté est dit biconnexe si, en retirant n'importe lequel de ses sommets, il reste connexe. Cela revient à dire que le graphe n'a pas de point d'articulation. Biparti un graphe est dit biparti s'il existe une partition de son ensemble de sommets en deux sous-ensembles et telle que deux sommets adjacents soient dans deux parties différentes. Cela revient à dire que le graphe est 2-colorable. Biparti complet un graphe est dit biparti complet s'il est biparti et qu'il existe une arête entre chaque sommet de et de . On note le graphe biparti complet tel que et . Birégulier un graphe est dit birégulier s'il est biparti et si chacune de ses parties et n'a que des sommets de même degré. On le dit -régulier si et . Blob bridgeless component en anglais, ensemble de sommets ne contenant pas d'isthme. Bloc ensemble de sommets ne contenant pas de point d'articulation. Boucle arête partant d'un sommet et arrivant sur lui-même.
C Cactus un graphe connexe dans lequel deux cycles simples quelconques ont au plus un sommet en commun. Centralité un indicateur de centralité est une mesure censée capturer la notion d'importance dans un graphe, en identifiant les sommets les plus significatifs. Chaîne dans un graphe non orienté, une chaîne est une suite finie non vide de sommets telle que chaque paire de sommets consécutifs de la suite soit une arête du graphe ; la suite (un moins en longueur) d'arêtes ainsi obtenue caractérise aussi la chaîne. La notion correspondante dans un graphe orienté est celle d'un chemin. La longueur d'une chaîne est celle de sa suite d'arêtes (un moins que la longueur sa suite de sommets). La source de la chaîne est son premier sommet, et son but est son dernier sommet. Une chaîne est dite élémentaire si aucun sommet ne figure plus d'une fois dans la suite, à l'exception de la source et le but de la chaîne qui peuvent coïncider. Chemin dans un graphe orienté, un chemin est une suite finie non vide de sommets telle que chaque couple de sommets consécutifs de la suite est un arc du graphe ; la suite d'arcs ainsi obtenue caractérise aussi le chemin. La notion correspondante dans un graphe non orienté est celle d'une chaîne. La longueur d'un chemin est celle de sa suite d'arcs (un moins que la longueur sa suite de sommets). La source du chemin est son premier sommet, et son but est son dernier sommet. Un chemin est dit élémentaire si aucun des sommets ne figure plus d'une fois comme source, ni plus d'une fois comme but d'un arc du chemin (mais source et but du chemin peuvent coïncider). Chenille c'est un arbre dans lequel tous les sommets sont à distance au plus 1 d'un chemin central. Circonférence longueur du plus grand cycle. Nombre chromatique nombre minimal de couleurs pour colorier un graphes sans sommets adjacents de même couleur. Nombre chromatique non répétitif nombre minimal de couleurs pour colorier un graphes dont les chaînes sont sans facteurs de couleurs répétées. Clique sous-graphe induit complet, c'est-à-dire un sous-ensemble des sommets tels que chacun est connecté à tous les autres. Une clique est un ensemble indépendant (ou stable) du graphe complémentaire. Coloration fonction associant à tout sommet une couleur, tels que deux sommets adjacents aient une couleur différente (c'est-à-dire partitionne les sommets en ensembles indépendants). k-coloration coloration d'un graphe en k couleurs distinctes. Complémentaire le complémentaire (ou inverse, ou complément) d'un graphe simple est un graphe simple qui a les mêmes sommets que G, reliés si et seulement s’ils ne sont pas reliés dans le graphe d'origine, soit . Complet dans un graphe complet chaque sommet est relié à tous les autres par une arête ou un arc. On note le graphe complet à n sommets. Composante une composante d'un graphe est un sous-graphe connexe maximal. Connexe un graphe est connexe s'il existe un chemin entre tout couple de sommets. Quand on parle de connexité pour un graphe orienté, on considère non pas ce graphe mais le graphe non-orienté correspondant. On peut déterminer ceci par exemple avec un algorithme de parcours en profondeur. Un graphe orienté est dit fortement connexe si, pour tout couple de sommets (u,v) du graphe, il existe un chemin de u à v et de v à u. k-arête-connexe un graphe est k-arête-connexe s'il cesse d'être connexe uniquement quand on supprime k arêtes ; ceci peut se vérifier par la présence de k chaînes disjointes (ne partageant aucune arête) entre chaque sommet. k-sommet-connexe (ou k-connexe) un graphe est k-sommet-connexe s'il cesse d'être connexe uniquement quand on supprime k sommets. Contenir un graphe contient si est un sous-graphe induit de . Contraction supprime une arête d'un graphe en fusionnant ses deux extrémités. Autrement dit, la contraction d'une arête à un sommet rend le sommet adjacent à tous les voisins précédents de . Corde arête reliant deux sommets non-adjacents d'un cycle. Cospectral deux graphes sont cospectraux s'ils ont le même spectre. Ce spectre pouvant être basé sur plusieurs matrices, on peut préciser A-cospectraux pour le spectre de la matrice d'adjacence et L-cospectraux pour le spectre de la matrice laplacienne. Coupe partition des sommets en deux sous-ensembles. Peut aussi désigner l’ensemble des arêtes ayant une extrémité dans chaque sous-ensemble. Couverture par sommets Une couverture par sommets ou transversale d'un graphe G est un ensemble C de sommets de G tel que chaque arête du graphe est incidente à au moins un sommet de C. Couvrant un sous-graphe d'un graphe couvre (on dit aussi qu'il est un sous-graphe couvrant ou un graphe partiel de ) si tous les sommets de sont dans (). Creux un graphe creux possède un nombre d'arêtes (ou d'arcs) faible par rapport au nombre de sommets. Cubique graphe 3-régulier. Cycle chaîne dont les sommets de départ et de fin sont les mêmes. Autrement dit, soit un chemin dont les arêtes sont : le cycle est alors défini par . Dans un graphe orienté, on parlera d'un circuit plutôt que d'un cycle, même si la terminologie n'est pas tout à fait stabilisée. Cyclomatique le nombre cyclomatique d'un graphe est , où est le nombre de composantes connexes. C'est également la dimension de l'espace des cycles.
D Degré dans le cas non-orienté et non pondéré, le degré du sommet est le nombre d'arêtes de . Dans le cas d'un graphe orienté, le degré entrant est le nombre d'arcs vers tandis que le degré sortant est le nombre d'arcs sortant de . Le degré maximum est noté , et le degré minimal . Dans le cas pondéré, le degré d'un sommet est la somme du poids des arêtes incidentes à ce sommet. Demi-carré le sous-graphe induit sur l'un des deux sous-ensembles de sommets du carré d'un graphe biparti. Se dit aussi moitié bipartie. Demi-graphe un graphe biparti qui possède environ la moitié des arêtes d'un graphe biparti complet sur ses sommets. Degrés (matrice) la matrice des degrés d'un graphe est une matrice carrée de taille telle que et . Dense un graphe dense possède un nombre d'arêtes (ou d'arcs) proche du nombre maximal. Densité la densité d'un graphe est le rapport entre le nombre d'arêtes (ou d'arcs) divisé par le nombre d'arêtes (ou d'arcs) possibles. Dans le cas d'un graphe non orienté, simple et fini , c'est le rapport . Diamètre excentricité maximale des sommets, notée . Dilatation dans un plongement où associe des sommets d'un graphe à ceux d'un graphe , la dilatation est la distance maximale entre les images par de deux sommets adjacents dans . Autrement dit, si deux sommets sont voisins dans un graphe, leurs images peuvent être séparées par un chemin qui augmente donc la distance entre eux, et la plus grande augmentation est la dilatation. Dimension la dimension minimale d'un espace euclidien afin qu'un graphe puisse y être représenté avec des arêtes qui soient toutes de longueur 1. Dimension euclidienne ou dimension fidèle la dimension minimale d'un espace euclidien afin qu'un graphe puisse y être représenté de telle sorte que des sommets soient à distance 1 si et seulement s'ils sont reliés. Dimension bipartie le nombre minimal de sous-graphes bipartis complets nécessaires pour couvrir toutes les arêtes d'un graphe. Dimension métrique le nombre minimal de sommets d'un sous-graphe de tel que tous les autres sommets sont déterminés de façon unique par leur distance aux sommets de . Distance la distance entre et est la longueur du plus court chemin entre ces sommets ; aussi appelée distance géodésique. Distance (matrice de) matrice d'éléments aij correspondant a la longueur du plus court chemin (la distance) entre les sommets d'indices i et j. Distance-régulier un graphe est distance-régulier si pour tous sommets , le nombre de sommets voisins de à distance et le nombre de sommets voisins de à distance ne dépendent que de et de la distance entre et . Formellement, tels que et Dominant (ou absorbant) un ensemble de sommet est dominant si tout sommet en fait partie ou est voisin d'un sommet en faisant partie. Dureté la dureté (« toughness » en anglais) est une mesure de la connexité d'un graphe. Un graphe est dit -dur pour un nombre réel donné si, pour tout entier , ne peut pas être divisé en composantes connexes par la suppression de moins de sommets.
E