Lexique sur les graphes
Entre parenthèses, le terme anglais.
A |
B |
C |
D |
E |
F |
G |
H |
I-J |
K
|
L |
M |
N |
O |
P-Q
|
R |
S |
T-U |
V-Z
Un graphe est acyclique s'il ne contient aucun cycle.
Deux sommets sont adjacents s'ils sont reliés par une arête. On qualifie souvent de voisins deux sommets adjacents. Voici deux sommets adjacents:
Arbre avec un sommet distingué r (la racine).
Graphe connexe ne contenant aucun cycle.
Un sous-graphe maximum d'un graphe qui est aussi un arbre. On parle aussi d'arbre de recouvrement.
Arbre binaire qui a été étiqueté avec des nombres de sorte que le fils de droite d'un sommet s et tous ses descendants aient des numéros plus petits que le numéro de s, et le fils de gauche de s et tous ses descendants ont des numéros plus grands que celui de s.
Un arbre où chaque sommet a 0 ou n fils. Quand n = 2, on parle d'arbre binaire.
Une arête orientée d'un digraphe.
Une arête relie deux sommets dans un graphe. Nous appelons ces deux sommets les extrémités de l'arête. Voici les arêtes d'un graphe (en rouge):
Un graphe est biparti si ses sommets peuvent être divisés en deux ensembles X et Y, de sorte que toutes les arêtes du graphe relient un sommet dans X à un sommet dans Y. Les arbres sont des exemples des graphes bipartis. Si G est biparti, il est habituellement noté par G = (X, Y, E), où E est l'ensemble des arêtes.
K3,3 est un graphe biparti:
Arête ou arc partant d'un sommet et allant vers lui-même. Les boucles ne sont pas autorisées dans les graphes et digraphes simples.
Une chaîne dans un graphe est une suite de sommets reliés par des arêtes. La longueur d'une chaîne est le nombre d'arêtes utilisées, ou, ce qui revient au même, le nombre de sommets utilisés moins un. Une chaîne simple ne peut pas visiter le même sommet deux fois. Voici un exemple d'une chaîne simple:
Un chemin dans un digraphe est une suite de sommets reliés les uns aux autres par des arcs. La longueur du chemin est le nombre d'arcs utilisés, ou le nombre de sommets moins un. Un chemin simple ne peut pas visiter le même sommet plus d'une fois. Un chemin fermé a pour dernier sommet le premier. Voici un exemple de chemin:
Dans un digraphe, un circuit est un chemin fermé simple.
Sous-graphe complet d'un graphe G. L'ordre de la plus grande clique de G est noté w(G). Prononcer oméga de G.
Dans un graphe complet, toutes les paires de sommets sont adjacentes. Un graphe complet à n sommets est noté Kn (le K est en l'honneur de Kuratowski, un pionnier de la théorie des graphes).
Voici le graphe complet sur cinq sommets, noté K5:
Dans un graphe, une composante connexe est un sous-graphe induit maximal connexe. Maximal signifie qu'il n'y a pas de sous-graphe induit connexe plus grand contenant les sommets de la composante.
Étant donné un graphe G, si deux sommets de G sont fusionnés et si tous les boucles ou arêtes multiples créés par cette fusion sont enlevées, le graphe résultant s'appelle le graphe condensé.
Un graphe connexe est un graphe dans lequel chaque paire de sommets est reliée par une chaîne. Un graphe qui n'est pas connexe est dit non connexe, et se décompose en composantes connexes.
On appelle corde d'un cycle élémentaire une arête qui relie deux sommets non consécutifs de ce cycle.
Un couplage est un ensemble d'arêtes tel que chaque sommet du graphe appartient à au plus une arête de cet ensemble.
Dans un graphe à 2n sommets, un couplage avec n arêtes est dit parfait. Chaque sommet du graphe est saturé par un couplage parfait.
Dans un graphe, un cycle est une chaîne
simple dont les extrémités coïncident. On ne rencontre pas deux fois le même
sommet, sauf celui choisi comme sommet de départ et d'arrivée.
Le degré d'un sommet est la taille de son voisinage. Le degré d'un graphe est le degré maximum de tous ses sommets.
Le diamètre d'un graphe est la plus longue des distances entre deux sommets de ce graphe.
Un digraphe est un graphe dans lequel les arêtes sont orientées et appelées arcs. Plus formellement, un digraphe est un ensemble de sommets ainsi qu'un ensemble de paires ordonnées des sommets, appelées les arcs. Voici un digraphe sur 4 sommets:
La distance entre deux sommets est la longueur de la plus courte chaîne entre eux.
Les étiquettes sont simplement des noms donnés aux sommets et aux arêtes de façon à pouvoir les différencier. L'étiquetage des sommets est arbitraire.
Une chaîne ou un circuit est dit eulérien si chaque arête du graphe y apparaît exactement une fois.
La fermeture d'un graphe G à n sommets est le graphe obtenu à partir de G en ajoutant progressivement des arêtes entre les sommets non adjacents dont la somme des degrés est au moins égale à n, jusqu'à ce que ceci ne puisse plus être fait. Plusieurs résultats sur l'existence des circuits hamiltoniens se rapportent à la fermeture d'un graphe.
Sommet de degré 1. Aussi appelé sommet pendant.
Dans un arbre, les sommets adjacents à un sommet donné du niveau supérieur sont appelés fils de ce sommet. Les descendants d'un sommet sont les sommets qui sont le fils, ou le fils du fils, etc., d'un sommet donné.
Graphe qui ne contient aucun cycle. Les composantes connexes d'une forêt sont des arbres.
Dans un digraphe fortement connexe, chaque sommet peut être atteint depuis n'importe quel autre par un chemin.
Un graphe est un ensemble de points, dont certaines paires sont reliées par des lignes. Les points sont appelés sommets et les lignes sont nommées arêtes.
Plus formellement, un graphe est composé de deux ensembles, l'ensemble des arêtes (E) et l'ensemble des sommets (V). L'ensemble des sommets est simplement une collection d'étiquettes qui permettent de distinguer un sommet d'un autre. L'ensemble des arêtes est constitué de paires non ordonnées d'étiquettes de sommets.
Voici la représentation graphique d'un graphe et les ensembles définissant le graphe:
 |
V={A, B, C, D}
-- l'ensemble des sommets
E={(A,B) , (A,C) , (B,C) ,
(B,D)}
-- l'ensemble des arêtes |
| Une représentation graphique |
|
Une chaîne ou un cycle est dit hamiltonien si chaque sommet du graphe y apparaît exactement une fois. Les chemins et les circuits des digraphes sont dits hamiltoniens sous les mêmes conditions. Un graphe contenant un circuit hamiltonien ou un digraphe contenant un cycle hamiltonien est appelé graphe ou digraphe hamiltonien.
La hauteur d'un arbre est la longueur de la plus longue chaîne simple partant de la racine de l'arbre.
Deux graphes sont homéomorphes s'ils peuvent tous les deux être obtenus à partir d'un graphe commun en remplaçant les arêtes par des chaînes simples.
Un sommet est incident à une arête s'il est situé à une des deux extrémités de cette arête. Inversement, une arête est incidente à un sommet si elle "touche" ce sommet.
L'indice chromatique d'un graphe est le plus petit nombre k pour lequel il existe une k-coloration des arêtes. L'indice chromatique du graphe G est noté par c(G) [c est la lettre grecque khi].
Dans l'exemple ci-dessous, l'indice chromatique vaut 4.
Deux graphes sont isomorphes si ce sont les mêmes graphes, dessinés différemment. Deux graphes sont isomorphes si on peut étiqueter les deux graphes avec les mêmes étiquettes de sorte que chaque sommet ait exactement les mêmes voisins dans les deux graphes. Voici deux graphes isomorphes:
Arête dont la suppression augmente le nombre de composantes connexes du graphe.
Un graphe est dit k-colorable si à chacun de ses sommets peut être assignée une parmi k couleurs de sorte qu'à deux sommets adjacents soit assignée une couleur différente. Cette assignation est appelée coloration.
Une représentation d'un graphe ou d'un digraphe qui énumère, pour chaque sommet, tous les sommets qui sont adjacents au sommet donné.
Une représentation d'un digraphe utilisant les arcs du digraphe. Ce peut être une liste de paires ordonnées de sommets, ou deux listes triées avec le sommet de départ dans une
liste et le sommet de fin à la position correspondante de la deuxième liste.
Une matrice carrée contenant des 0 et des 1, dont les lignes et les colonnes sont classées par sommets. Un 1 en position (i,j) signifie qu'il y a une arête (ou arc) du sommet i au sommet j. Un 0 indique qu'il n'y a aucune arête ou arc. Peut être utilisée pour des graphes et des digraphes.
Une matrice contenant des 0 et des 1 dont les lignes sont indexées par les sommets du graphe et dont les colonnes sont indexées par les arêtes. Un 1 à la position (i,j) de la matrice signifie que le sommet i est une extrémité de l'arête j. Un 0 indique que ce n'est pas le cas.
Autre mot pour sommet.
Le nombre chromatique d'un graphe est le plus petit nombre k pour lequel il existe une k-coloration des sommets. Le nombre chromatique du graphe G est noté par g(G) [g est la lettre grecque gamma].
Dans l'exemple ci-dessous, le nombre chromatique vaut 3.
L'ordre d'un graphe est le nombre de ses sommets.
Un ordre topologique d'un digraphe est un étiquetage des sommets avec des entiers consécutifs de sorte que chaque arc soit orienté d'un numéro plus petit vers un plus grand.
Une assignation de direction aux arêtes d'un graphe. Une arête orientée est un arc. Le graphe auquel on a donné une orientation est dit graphe orienté et est un digraphe.
Le graphe obtenu en enlevant des arêtes d'un graphe G est appelé graphe partiel:
|
 |
| Un graphe |
Un graphe partiel |
Un sommet est pendant s'il est de degré 1. Aussi appelé feuille si le graphe est un arbre.
Un graphe planaire est un graphe que l'on peut dessiner sur une surface plate sans que ses arêtes se croisent. Les graphes que l'on ne peut pas desssiner sans croisements sont dits non planaires. Tout graphe contenant l'un ou l'autre des deux sous-graphes ci-dessous est non planaire:
Sommet distingué d'un arbre. En distinguant un sommet d'un arbre, on obtient une arborescence.
Dans une arborescence, les sommets à la même distance de la racine sont dits être au même rang. La racine est par convention au rang 0 et la hauteur de l'arbre est le rang maximum.
Si une arête, a, est enlevée d'un graphe G, le graphe résultant, noté G'a est appelé le graphe réduit.
Dans un graphe régulier, tous les sommets ont le même degré. Si le degré commun est k, alors on dit que le graphe est k-régulier.
Un sommet appartenant à une arête d'un couplage est dit saturé.
Un graphe est dit simple, s'il ne contient pas de boucles et s'il n'y a pas plus d'une arête reliant deux mêmes sommets.
Un sommet est dit simplicial si l'ensemble de ses voisins forme une clique.
Un sommet est un 'noeud' du graphe. C'est l'extrémité d'une arête. Voici les sommets (en rouge) d'un graphe:
Un sous-graphe d'un graphe est obtenu en
y enlevant des sommets et toutes les arêtes
incidentes à ces sommets.
|
 |
| Un graphe |
Un sous-graphe |
Un stable d'un graphe G est un sous-graphe de G sans arêtes. L'ordre du plus grand stable de G est noté a(G) est s'appelle nombre de stabilité. Prononcer alpha de G.
La taille d'un graphe est le nombre de ses arêtes.
Digraphe complet.
Le voisinage d'un sommet est l'ensemble de tous ses sommets adjacents. Ci-dessous le voisinage (en rouge) du sommet bleu:
 |
 Didier Müller, 11.11.99 |