Objets et relations entre objets

À 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 $\mathcal{R}$ est donc un ensemble infini de couples $(x,y)$ tels que $x \mathcal{R} y$. L'ensemble correspondant à la relation $=$ est donc $\{(34.5, 34.5), (1/4, 0.25), \ldots \}$.

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 $n$, l'ensemble des couples (la relation) sera de taille inférieure ou égale à $n^2$.

Exemples :

1. L'ensemble contient toutes les personnes assistant à un repas de Noël et la relation contient tous les couples de personnes $(p_1, p_2)$ tels que $p_1$ est ancêtre de $p_2$. Dans cet exemple, la relation n'est pas symétrique , à savoir qui si $p_1$ est ancêtre de $p_2$, alors $p_2$ n'est pas nécessairement ancêtre de $p_1$; elle est même antisymétrique et transitive.

2. L'ensemble contient toutes les personnes assistant à un repas de Noël et la relation contient tous les couples de personnes $(p_1, p_2)$ tels que $p_1$ est parent de $p_2$. Ici la relation est antisymétrique mais elle n'est pas transitive.

3. Avec le même ensemble que ci-dessus, on considère la relation qui contient tous les couples de personnes $(p_1, p_2)$ tels que $p_1$ est cousin de $p_2$. Cette relation est symétrique, car si $p_1$ est cousin de $p_2$, alors $p_2$ est cousin de $p_1$.

4. L'ensemble contient les atomes d'une molécule et la relation tous les couples d'atomes $(a1, a2)$ tels que $a1$ et $a2$ partagent au moins un électron. Cette relation est symétrique et réflexive.

5. L'ensemble contient les composants électroniques d'un circuit et la relation tous les couples de composants $(c_1, c_2)$ tels que $c_1$ est directement connecté à $c_2$.

6. L'ensemble contient des stations-relais d'un réseau de communication de téléphonie mobile et la relation contient tous les couples de stations $(s_1, s_2)$ tels qu'il existe un lien direct de communication (par micro-ondes, câble, etc.) entre $s_1$ et $s_2$.

Dans le reste du livre, nous allons le plus souvent nous limiter à des relations symétriques sur des ensembles finis d'objets.