Fiche de cours
Vocabulaire des graphes
Définition
Un graphe est un ensemble de points reliés entre eux.
Dans la suite, on considéra comme exemple le graphe suivant.
Les points sont appelés des sommets. Le nombre total de sommets est appelé l'ordre : ici l'ordre vaut 4.
Deux sommets sont adjacents si ils sont reliés entre eux. Par exemple, $B$ et $D$ ne sont pas adjacents.
Les segments reliant deux sommets sont des arêtes.
Le degré d'un sommet correspond au nombre d'arêtes partant de ce commet. Par exemple, trois arêtes partent du sommet $A$ : $A$ est de degré 3.
Une chaîne de sommets est une liste de sommets reliés par des arêtes. Un cycle est une chaîne débutant par un sommet et terminant par ce même sommet. Par exemple $ABCD$ est une chaîne et $ABCA$ est un cycle.
La longueur d'une chaîne est le nombre d'arêtes composant cette chaine. Il ne faut donc pas compter