Graphe de Kahn

Le graphe (orienté) de Kahn[1] $\mathcal{G=(V, E)}$ est défini de la sorte :

$$\left\lbrace\begin{array}{l} \mathcal{V = T} \\ \mathcal{E = B} \end{array}\right.$$

Cela signifie que les sommets correspondent aux tâches et les arcs aux buffers. L'existence d'un arc (orienté) $(V_{i}, V_{j})$ signifie qu'il existe un buffer $b$ dans lequel $T_{i}$ écrit et $T_{j}$ lit.

Par exemple, l'instance suivante du problème :

$$\left\lbrace\begin{array}{l} \mathcal{T} = \lbrace T_{1}, T_... ..._{1}, T_{2}), b_{3}=( T_{2}, T_{1} ) \rbrace \end{array}\right.$$

se représente comme dans la figure 1.3.

Figure 1.3: Exemple d'un graphe de Kahn[1]

Ce graphe ne dévoile cependant pas la décomposition de chaque tâche en opérations.