Un graphe est une représentation composée de sommets (des points) reliés par des arêtes (segments).
Un graphe orienté est un graphe dont les arêtes sont munies d'un sens de parcours.
L'ordre d'un graphe est le nombre de sommets de ce graphe.
Le degré d'un sommet est le nombre d'arêtes incidentes à ce sommet, sans tenir compte de leur éventuel sens de parcours.

Deux sommets sont adjacents lorsqu'ils sont reliés par au moins une arête.
Un graphe est complet lorsque tous ses sommets sont deux à deux adjacents.

Pour un graphe non orienté, une chaîne est une suite d'arêtes consécutives reliant deux sommets (éventuellement confondus).
La longueur d'une chaîne est le nombre d'arêtes la composant.
Pour un graphe orienté, un chemin est une suite d'arêtes consécutives reliant deux sommets (éventuellement confondus) en tenant compte du sens de parcours des arêtes.

Un graphe non orienté est connexe lorsque chaque couple de ses sommets peut être relié par une chaîne.

Les sommets \text{A} et \text{B}, par exemple, ne sont pas adjacents donc ce graphe n'est pas complet.
La chaîne \mathrm{A}-\mathrm{C}-\mathrm{D}-\mathrm{E}-\mathrm{G}-\mathrm{B}-\mathrm{F} passe par tous les sommets donc ce graphe est connexe.

Exercices

33

et

34

p. 191