À la base de la notion de graphe se trouve une collection d'objets et des relations binaires entre ces objets.
Une relation binaire est un ensemble de couples
d'objets. En mathématique, une relation est souvent
exprimée sous la forme de prédicat, par exemple ``''
pour la relation est strictement inférieur à ou ``
'' pour la
relation est égal à.
En mathématique classique, ces relations sont
caractérisées par le fait qu'elles s'appliquent à un nombre infini d'objets,
ici par exemple tous les nombres réels.
Une relation
est donc un ensemble infini de couples
tels que
. L'ensemble correspondant à la
relation
est donc
.
L'ensemble des réels est non seulement infini mais de plus il n'est pas dénombrable. Ceci veut dire qu'il est impossible de les numéroter tous.
En informatique, les objets sont souvent plus concrets qu'en mathématique classique. Il peut s'agir de personnes, de molécules, de composants électroniques, de villes ou d'émetteurs/récepteurs pour la téléphonie mobile. Souvent un ensemble de tels objets est de taille finie, ou au moins dénombrable. Ce fait simplifie considérablement les traitements à réaliser sur ces ensembles.
Lorsque l'ensemble des objets est fini, une relation contenant des
couples d'objets est forcément finie aussi. Autrement dit, si la
relation est vue comme un ensemble de couples d'objets, cet ensemble
de couples est fini. Plus exactement, si l'ensemble des objets
est de taille , l'ensemble des couples (la relation) sera de taille
inférieure ou égale à
.
Exemples :
Dans le reste du livre, nous allons le plus souvent nous limiter à des relations symétriques sur des ensembles finis d'objets.