Graphes sans cycle

Un cas particulier intéressant est celui du graphe sans cycle. La raison principale est que les algorithmes sur un tel graphe sont plus rapides. Si l'on est certain que le graphe est sans cycle, on peut obtenir des programmes plus efficaces. Dans cette section nous allons définir la notion de cycle ainsi que celle de graphe sans cycle.

Tout d'abord, nous allons définir la notion de chemin (en anglais : directed path) dans un graphe orienté.

Définition 7.2   Un chemin dans un graphe orienté est une suite non vide (i.e., contenant au moins un arc) $P = a_1, a_2, \ldots, a_n$ d'arcs telle que
$\forall i, 1 \le i < n, H(a_i) = T(a_{i+1})$.

Cette définition nous dit d'abord qu'un chemin est une suite d'arcs.

Puis, la définition nous dit que la suite d'arcs ne doit pas être une suite arbitraire, mais que l'extrémité finale d'un arc doit être l'extrémité initiale de l'arc suivant dans la suite.

Définition 7.3   Un circuit dans un graphe orienté est un chemin
  $P = a_1, a_2, \ldots, a_n$ tel que $H(a_n) = T(a_1)$.

Cette définition nous donne le critère qui détermine si un chemin est un circuit, à savoir que éxtrémité initiale du premier arc doit être identique à l'extrémité finale du dernier.

Dans la figure 7.2, la suite $a,b,c$ est un circuit, de même que la suite $a,b,c,d$, la suite $a,b,c,d,d,a,b,c$, etc.

Définition 7.4   Un circuit est simple si et seulement si tout sommet du circuit est l'extrémité finale d'au plus un arc du circuit.

Le circuit $a,b,c$ de la figure 7.2 est donc simple, ainsi que le circuit $d$. Par contre, le circuit $a,b,c,d$ n'est pas simple, car le sommet $C$ est l'extrémité finale à la fois de l'arc $c$ et de l'arc $d$ dans la suite.

Figure: Circuits dans un graphe orienté

En général, un graphe orienté peut avoir des circuits. Mais si ce n'est pas le cas, on parle alors de graphe sans circuit.

Définition 7.5   Un graphe sans circuit est un graphe orienté dans lequel il n'y a pas de circuit.

C'est une définition qui paraît triviale, mais il faut savoir que c'est la première fois que nous avons une définition du concept graphe sans circuit. En informatique fondamentale (et en mathématique), on ne peut pas compter sur la langue française pour fournir ces définitions automatiquement. Le fait que le français nous indique que sans circuit est la même chose que n'ayant pas de circuit ne nous donne pas le droit d'omettre la définition formelle.

La figure 7.3 montre un graphe sans circuit. En anglais un tel graphe est appelé ``Directed Acyclic Graph'' ou ``DAG''. Cette Cette abréviation anglaise ``DAG'' est souvent utilisée dans la littérature française.

Figure 7.3: Un graphe sans circuit (DAG)