Conditions nécessaires et suffisantes de non-blocage

A la suite de la première étape, nous nous trouvons avec deux suites d'expressions de la forme citée précédemment, à savoir

$$C(b, b^{\prime}) = \left \lbrace \begin{array}{cc} (\Delta(b... ...hcal{B}_{ij} \times \mathcal{B}_{ji} & (2) \end{array} \right.$$

Le graphe est sans circuits si et seulement si, quels que soient $b$ et $b^{\prime}$ tels que $b \not= b^{\prime}$, $C(b, b^{\prime })$ est vrai[2]. Il convient, pour obtenir une solution réalisable, de trouver une interprétation de l'application $\Delta$ satisfaisant toutes les expressions. Remarquons au passage que les expressions de type $(1)$ sont un cas particulier des expressions du type $(2)$, c'est-à-dire $C(b, b^{\prime}) = (\Delta(b)\geq x_{1})\wedge(\Delta(b^{\prime})\geq y_{1})$ où $l=1$.