|
Graphe
Diagramme
constitué de points et de lignes.
Sommet
Les points sont les sommets du graphe.
Dans le graphe de la figure P ci-après, A, B, C, D, E, F et G sont les sommets.
Arête
Les lignes comprises entre deux points
sont les arêtes. AB, AC, AE, AG, BC, BG, CD, DE, EF et FG sont des arêtes
(figure P).
Degré d’un sommet
Le degré d’un sommet est le nombre d’arêtes
qui commencent ou se terminent en un même point. Le degré de A est 4, celui de
B est 3, celui de D est 2 (figure P).
Chaîne
Une suite d’arêtes est une chaîne.
Par exemple, GB, BC, CD et DE forment une chaîne (figure P).
Cycle
Une chaîne qui commence et se termine
au même sommet est un cycle. Par exemple, AC, CB, BG et GA forment un cycle
(figure P).
Graphe eulérien
Une chaîne qui passe une seule fois
par toutes les arêtes forme un graphe eulérien. Le graphe P n’est pas
eulérien.
Graphe hamiltonien
Une chaîne qui passe une seule fois
par les sommets forme un graphe hamiltonien. En partant de A, on peut passer par
tous les sommets une seule fois (figure P).
Graphe valué
Un graphe pour lequel on attribue une
valeur numérique à chacune des arêtes est un graphe valué. Dans le graphe Q,
le nombre 4 signifie, par exemple, qu’il faut verser quatre dollars pour
passer d’un point à l’autre de l’arête marquée 4.
Graphe orienté
Un graphe dont les arêtes sont munies
d’un sens est appelé graphe orienté comme dans la figure R.
Flèche
L’arête d’un graphe orienté est
une flèche.
© Charles-É. Jean
Index
: G
|
