Chaîne

Il nous sera souvent utile de savoir si dans un graphe donné, il est possible d'aller d'un sommet à un autre sommet en suivant des arêtes. Une telle suite d'arêtes est appelée une chaîne (en anglais : path). Dans cette section, nous allons examiner plusieurs définitions possibles du concept de chaîne, jusqu'à trouver à la bonne.

Définition 5.3 (attention : cette définition n'est pas bonne)   . Une chaîne dans un graphe est une suite $C = s_1, s_2, \ldots, s_n$ de sommets du graphe, telle que $\forall i, 1 \le i < n$, il y a une arête entre $s_i$ et $s_{i+1}$.

Cette définition ne marche pas très bien lorsque le graphe a plusieurs arêtes entre deux sommets. Par exemple, dans le graphe de la figure 5.2 la chaîne (selon la définition ci-dessus) $C = A, B$ est ambiguë. On ne sait pas s'il faut passer par l'arête $a$ ou l'arête $b$. Dans certaines applications, cela peut-être problématique.

Figure: Illustration du concept de chaîne

Voici une deuxième tentative :

Définition 5.4 (attention : cette définition n'est pas bonne)   . Une chaîne dans un graphe est une suite $C = e_1, e_2, \ldots, e_n$ d'arêtes du graphe, telle que $\forall i, 1 \le i < n$, $e_i$ et $e_{i+1}$ partagent un sommet.

Cette définition ne marche malheureusement pas très bien non plus. Le problème est que la suite $a,b,c$ de la figure 5.3 sera considérée comme une chaîne selon cette définition. La raison est que les arêtes $a$ et $b$ partagent le sommet $B$ et les arêtes $b$ et $c$ partagent aussi le sommet $B$. Pourtant, on ne souhaite pas considérer la suite $a,b,c$ comme une chaîne.

Un autre problème avec cette définition est que l'on ne sait toujours pas par quel sommet la chaîne commence.

Figure: Illustration du concept de chaîne

Il y a plusieurs façons de corriger les définitions ci-dessus. Ici, nous allons utiliser la solution suivante :

Définition 5.5   Une chaîne dans un graphe est une suite

$$C = s_1, e_1, s_2, e_2, \ldots, s_n, e_n, s_{n+1}$$

de $n+1$ sommets et $n$ arêtes en alternance, telle que $\forall i, 1 \le i \le n$, les extrémités de $e_i$ sont $s_i$ et $s_{i+1}$. On dit alors que $C$ est une chaîne entre $s_1$ et $s_{n+1}$.

Cette définition permet d'éviter l'ambiguïté de la figure 5.2. Il suffit de préciser soit la suite $A,a,B$, soit la suite $A,b,B$.

Les problèmes de la deuxième définition sont également résolus.