Représentation graphique d'une relation

Lorsque l'ensemble des objets est fini (et ne contient pas trop d'éléments), il est possible de représenter une relation sur cet ensemble par un dessin ou graphe. Une telle représentation est souvent utile pour mieux comprendre un problème.

Le plus souvent, les objets de l'ensemble sont dessinés sous forme de cercles, et les couples de la relation sous forme de segments de droites ou de courbes reliant deux cercles.

Figure: Les cousins d'un repas de Noël

La figure 2.1 montre une représentation d'un graphe dans lequel les objets sont des personnes assistant à un repas de Noël et la relation contient tous les couples de cousins. Dans cet exemple, Jean et Isabelle sont cousins, de même qu'Isabelle et Luc, Anne et Jacques, Jacques et Pierre. Marie et Olivier n'ont aucun cousin présent au repas.

On remarque qu'une figure de ce type ne peut pas exprimer les relations ``ancêtre'' ou ``parent'' ci-dessus, car deux objets d'un couple de la relation ne sont pas distingués. Autrement dit, le graphe de cette figure ne peut illustrer que des relations symétriques. Un tel graphe (où la relation est forcément symétrique) est appelé un graphe non orienté. Les relations ``ancêtre'' et ``parent'' n'étant pas symétriques, elles ne peuvent pas être représentées par un dessin de ce type.

Figure: Les parents d'un repas de Noël

La figure 2.2 montre une représentation d'un graphe dans lequel les objets sont des personnes assistant à un repas de Noël et la relation contient tous les couples $(p_1, p_2)$ tels que $p_1$ est parent de $p_2$. Pour distinguer les deux personnes, on a dessiné une flèche pointant sur $p_1$. Dans cet exemple, Luc et Jean sont les fils de Anne et de Jacques. Isabelle est la fille de Pierre (la mère d'Isabelle n'est pas présente). Marie et Olivier sont les parents de Anne et de Pierre et sont donc les grand-parents de Luc, Jean et Isabelle. Un graphe de ce type (où la relation n'est pas forcément symétrique) est appelé graphe orienté.

Figure: Une molécule sous la forme de graphe

La figure 2.3 montre un graphe représentant une molécule organique. Afin d'illustrer les différents types d'atomes, nous avons dessiné les objets de la collection avec des cercles de différentes tailles et nous avons marqué chaque objet d'une lettre indiquant le symbole chimique.