Modèle mathématique dans lequel un ensemble d’objets, représentés par des points appelés sommets, sont reliés entre eux par des liens, représentés par des lignes ou des traits appelés arcs ou arêtes. Les sommets sont nommés par des étiquettes.
Un graphe est donc constitué de deux ensembles, d’une part l’ensemble L des arêtes et d’autre part l’ensemble S des sommets. L’ensemble des sommets est simplement une collection d’étiquettes qui permettent de distinguer un sommet d’un autre. Dans un graphe non orienté, l’ensemble des arêtes est constitué de paires non ordonnées d’étiquettes de sommets. Dans un graphe orienté, l’ensemble des arcs est constitué de couples d’étiquettes de sommets.
Exemple
Voici un graphe G :
Le graphe G ci-dessus, non orienté, peut-être défini par son nombre S de sommets et son nombre L d’arêtes :
G = (S, L) où S = {A, B, C, D, E, F} et L = {a, b, c, d, e}.