Définitions d'un graphe

Dans ce chapitre, nous allons examiner diverses définitions possibles de la notion de graphe. Le choix d'une telle définition est important. En effet, de cette définition peut dépendre l'utilité du concept pour une application.

Voici une première tentative de définition :

Définition 4.1   Un graphe est un couple $(V,E)$, où $V$ est un ensemble d'objets appelés les sommets du graphe ($V$ pour l'anglais ``vertex'', ou sommet en français), et $E \subseteq V \times V$ est une relation binaire sur $V \times V$. Les éléments de $E$ sont appelés les arêtes du graphe ($E$ pour l'anglais ``edge'').

Examinons maintenant cette définition. La seule difficulté potentielle réside dans la définition de l'ensemble des arêtes. Dans la définition, une arête est un élément de l'ensemble $V \times V$, ce qui signifie qu'une arête est un couple de sommets. Plus précisément, une arête est un membre du carré cartésien de l'ensemble des sommets. Bien qu'elle semble raisonnable, cette définition a en fait deux inconvénients.

D'abord, on ne pourra pas avoir deux arêtes dont les extrémités sont les mêmes sommets. La raison est que les arêtes forment (selon la définition) un ensemble, et qu'un élément ne peut pas figurer plusieurs fois dans un ensemble. On obtient avec cette définition un graphe simple bouclé, signifiant que l'on autorise des arêtes dont les deux extrémités sont le même sommet. On appelle une telle arête une boucle.

Le deuxième problème est que techniquement le couple $(s_1, s_2)$, n'est pas la même chose que le couple $(s_2 , s_1)$. En fait, avec notre première définition, les arêtes sont orientées, ce qui donne un graphe orienté. Or nous souhaitons pour l'instant avoir des graphes non orientés.

Pour corriger ces problèmes, il va falloir compliquer un peu la définition :

Définition 4.2   Un graphe est un triplet $(V,E,\phi)$, où $V$ est un ensemble d'élément appelés les sommets du graphe, et $E$ est un ensemble d'éléments appelés les arêtes du graphe et $\phi$ est une fonction $\phi : E \longrightarrow {\cal P}(V)$ telle que $\forall e \in E, \vert \phi (e) \vert \in \{1, 2\}$

Cette définition est effectivement plus compliquée que la précédente. Examinons ce qu'elle veut dire. D'abord, l'ensemble $E$ des arêtes n'est plus un sous-ensemble du carré cartésien de l'ensemble des sommets. On suppose alors que les arêtes sont des objets à part. Par contre, nous avons désormais une fonction $\phi$ qui, étant donnée une arête, fournit un ensemble de sommets. L'idée est que cette fonction donne les points extrêmes de l'arête. Par contre, afin de se limiter à des arêtes connectant exactement deux sommets (ou parfois un seul sommet si l'arête a ses deux extrémités sur le même sommet), la taille de l'ensemble donné par $\phi$ doit être de $1$ ou de $2$. On traduit la formule `` $\phi : E \longrightarrow {\cal P}(V)$ telle que $\forall x \in E, \vert \phi (x) \vert \in \{1, 2\}$'' en français  par ``$\phi$ est une fonction qui prend un seul argument (une arête) et qui retourne comme valeur un ensemble de sommets de taille $1$ ou $2$''.

Il est souvent souhaitable de donner une interprétation plus concrète d'une définition comme celle-ci. En fait, nous allons faire la correspondance entre une définition et un programme d'ordinateur. La définition 4.2 sera donc interprétée de la manière suivante :

Dans un programme d'ordinateur pour manipuler des graphes, nous pouvons, à partir d'un objet de type graphe récupérer l'ensemble des sommets du graphe et l'ensemble des arêtes du graphe. De plus, étant donnée une arête du graphe, nous pouvons récupérer les sommets extrémités de l'arête (ou le sommet dans le cas d'une boucle)`.

On suppose que ces opérations, dites primitives, s'exécutent très vite. L'ensemble des opérations primitives sur un objet, ici le graphe, est souvent appelé un type abstrait. Nous allons voir dans les autres parties de ce livre comment programmer à l'aide de types abstraits. Pour l'instant, il suffit de dire que certaines opérations sont faciles (i.e., rapides) ou difficiles (i.e., lentes) selon le type abstrait choisi. Avec la définition 2, il sera par exemple facile de compter le nombre d'arêtes du graphe, alors qu'il sera difficile de trouver toutes les arêtes incidentes à un sommet donné.

Il existe d'autres façons de définir un graphe; la définition 4.3 en est une.

Définition 4.3   Un graphe est un triplet $(V,E,\phi)$, où $V$ est un ensemble d'éléments appelés les sommets du graphe, $E$ est un ensemble d'éléments appelés les arêtes du graphe et $\phi$ est une fonction $\phi : V \longrightarrow {\cal P}(E)$ telle que $\forall e \in E, \vert \{s \in V,  e \in \phi(s) \} \vert \in \{1, 2\}$

Alors que cette définition est entièrement équivalente à la définition 4.2 (dans le sens qu'elle engendre les mêmes objets), le rôle de la fonction $\phi$ est totalement différent. Dans la définition 4.3, son domaine est l'ensemble des sommets et son image est l'ensemble des parties de l'ensemble des arêtes. Elle donne pour un sommet $s$ l'ensemble des arêtes incidentes à $s$. La restriction nous garantit qu'une arête figure soit dans un seul (dans le cas d'une boucle) soit dans deux de ces ensembles.

Nous allons voir dans la deuxième partie de ce livre comment traduire ces différentes définitions en types abstraits.