Le problèmes d’ordonnancement sont définis par la donnée d’un certain nombre d’opérations (les tâches) et des contraintes de succession entre ces tâches (la tâche $b$ ne peut commencer qu’après que la tâche $a$ soit terminée), ainsi que les durées de chacune de ces tâches.

Scheduling problems are defined by data consisting of a certain number of operations (tasks) and constraints on the ordering of these tasks (task $b$ can not start until task $a$ has finished) as well as the duration of each of these tasks.

Définir un ordonnancement consiste à attribuer à chacune des tâches une date d’exécution de manière à ce que l’ensemble des tâches soit terminé au plus tôt. Une des méthodes pour résoudre ce problème est la méthode PERT [1, 2]. Le premier pas de cette méthode consiste à construire un graphe (graphe PERT ou américain) dont les arcs représentent les tâches et où les relations de succession entre les tâches sont traduites ainsi : $b$ est successeur de $a$ si et seulement si il existe dans le graphe un chemin dont le premier arc est $a$ et le dernier $b$. La construction n’est en général possible que si l’on introduit de nouvelles tâches, dites virtuelles, de durée nulle.

Creating a schedule consists of assigning each task a date of execution so that all tasks are completed as early as possible. One of the methods for solving this problem is the PERT method [1, 2]. The first step of this method is to construction a graph (PERT or American graph) whose arcs represent the tasks and where the succession relations between tasks is translated as follows: $b$ is the successor of $a$ if and only if there exists a path in the graph whose first arc is $a$ and last one is $b$. The construction is usually possible only if we introduce new tasks, called virtuals, that are of zero duration.

Kelley [3] note qu’il est avantageux pour réduire la longueur des calculs suivants de construire un graphe PERT ayant le nombre minimal possible de sommets.

Le problème ainsi posé par Kelley a été abordé avec plus ou moins de succès par un certain nombre d’auteurs:

Hayes [4] donne un ensemble de recettes pour construire un graphe PERT. Sa méthode ne produit pas, en général, le graphe minimal.

Dimsdale [5] propose un algorithme de construction du graphe PERT minimal.

Fisher, Liebman, Nemhauser [6] montrent que l’algorithme de Dimsdale est faux; ils en donnent un nouveau qui est exact; leur article ne contient pas de preuve mathématique conformément au style du journal (C.A.C.M.).

Cantor et Dimsdale [7] donnent, avec démonstration, un algorithme exact. Leur méthode qui s’applique à un problème qui englobe les problèmes d’ordonnancement, gagne en généralité mais donne lieu, pour notre cas particulier, à des calculs inutilement longs.

Syslo [8] cherche à minimiser le nombre des arcs virtuels ce qui est un autre problème.

Dans le présent article notre contribution est la suivante : comme dans [6] nous ne considérons que le problème d’ordonnancement (ceci implique en particulier que les relations de succession entre tâches réelles ne peuvent pas former de circuit). Nous reprenons certaines notions des articles ci-dessus ou nous en définissons d’autres qui sont voisines. Nous démontrons certaines propriétés (notamment le théorème 1) qui ont échappé aux auteurs précédents et qui permettent finalement de donner un algorithme de construction du graphe PERT minimal réduisant le nombre des calculs.

Kelley [3] notes that it is advantageous to reduce the length of the following calculations by constructing a PERT graph that has the minimal possible number of vertices.

The problem thus posed by Kelley has been addressed with varying degrees of success by a certain number of authors:

Hayes [4] gives a set of recipes for constructing a PERT graph. His method does not produce, in general, the minimal graph.

Dimsdale [5] proposes an algorithm for the construction of the minimal PERT graph.

Fisher, Liebman, Nemhauser [6] show that Dimsdale’s algorithm is false; they give a new one that is exact; their article does not contain a mathematical proof that complies with the journal style (C.A.C.M).

Cantor and Dimsdale [7] give, with demonstration, an exact algorithm. Their method, which applies to a problem that includes scheduling problems, works in general, but gives rise to unnecessarily long calculations for our particular case.

Syslo [8] tries to minimise the number of virtual arcs which is another problem.

In this article our contribution is as follows: as in [6] we only consider the scheduling problem (this implies in particular that the successive relations between real tasks can not form a circuit). We take up some notions from the above articles or we define other related ones. We demonstrate certain properties (in particular Theorem 1) that have escaped the previous authors and finally allow us to give an algorithm for the construction of the minimal PERT graph that reduces the number of calculations.

$G=\left(X,U\right)$ graphe orienté dont $X$ est l’ensemble des sommets et $U$ l’ensemble des arcs.

$\left(i,j\right)$ arc reliant le sommet $i$ au sommet $j$.

$u\to v$ indique qu’il existe un chemin dont le premier arc est $u$ et dont le dernier arc est $v$.

$\forall i\in X$ on note :

Arc redondant : l’arc $\left(i,j\right)$ est dit redondant s’il existe un chemin de longueur supérieure à un de $i$ vers $j$.

S’il existe une application $f\text{ injective }:X\to V$ telle que $\forall j,\forall i\in Xi\in \widetilde{𝒫}\left(j\right)\text{ ssi }f\left(i\right)\to f\left(j\right),$ $H$ sera dit graphe arc-dual de $G$ par l’application $f$.

(1)

$H$ peut être un multigraphe.

(2)

$H$ ne contient aucun circuit contenant au moins un arc de la forme $f\left(i\right)$ car sinon la tâche $i$ se succèderait à elle-même.

$G=\left(X,U\right)$ is a directed graph where $X$ is the set of vertices and $U$ is the set of arcs.

$\left(i,j\right)$: arc connecting the vertex $i$ to vertex $j$.

$u\to v$ indicates that there exists a path whose first arc is $u$ and whose last arc $v$.

$\forall i\in X$ we note:

Redundant arc: the arc $\left(i,j\right)$ is said to be redundant if there exists a path of greater length than the one from $i$ to $j$.

If it exists, a injective map $f:X\to V$ where $\forall j,\forall i\in Xi\in \widetilde{𝒫}\left(j\right)\text{ iff }f\left(i\right)\to f\left(j\right),$, $H$ is the dual-arc graph $G$ on the mapping of $f$.

(1)

$H$ is possible a multigraph.

(2)

$H$ does not contain any circuit containing at least an arc of form $f\left(i\right)$ because otherwise the task $i$ would follow itself.

A partir du graphe français $G=\left(X,U\right)$, sans circuit et ne contenant aucun arc redondant on construit un graphe $H_0=\left(Y_0,V_0\right)$ de la manière suivante:

• pour chaque sommet $i\in X$, on définit deux sommets $a_i$ et $b_i$,
• on pose donc $Y_0={\bigcup }_{i\in X}\left\{a_i\right\}\cup \left\{b_i\right\}$;
• $V_0$ est constitué des arcs $\left(a_i,b_i\right)$ pour tout $i\in X$, ainsi que des arcs $\left(b_i,a_j\right)$ si $i\in 𝒫\left(j\right)$ dans $G$.

Les arcs de la forme $\left(a_i,b_i\right)$ seront dits réels et ceux de la forme $\left(b_i,a_j\right)$ seront dits virtuels.

Posons $f\left(i\right)=\left(a_i,b_i\right)$.

Il est immédiat que $f\left(i\right)\to f\left(j\right)\text{ ssi }i\in \widetilde{𝒫}\left(j\right)$ et que $f$ est une application injective.

(a)

$H_0$ ne contient aucun circuit.

(b)

$H_0$ ne contient aucun arc redondant.

(c)

les différents chemins de $H_0$ sont formés d’arcs alternativement réels et virtuels.

(d)

$H_0$ contient $2\left|X\right|$ sommets.

From the French graph $G=\left(X,U\right)$ without circuits and not containing redundant arcs, we construct a graph $H_0=\left(Y_0,V_0\right)$ in the following manner:

• for each vertex $i\in X$, we define two vertices $a_i$ and $b_i$,
• we let $Y_0={\bigcup }_{i\in X}\left\{a_i\right\}\cup \left\{b_i\right\}$;
• $V_0$ is made of arcs $\left(a_i,b_i\right)$ for all $i\in X$, as well as arcs $\left(b_i,a_j\right)$ if $i\in 𝒫\left(j\right)$ in $G$.

The arcs of the form $\left(a_i,b_i\right)$ will be called real and those of form $\left(b_i,a_j\right)$ will be called virtual.

Let $f\left(i\right)=\left(a_i,b_i\right)$.

It follows that $f\left(i\right)\to f\left(j\right)\iff i\in \widetilde{𝒫}\left(j\right)$ and that $f$ is an injective map.

(a)

$H_0$ does not contain any circuits.

(b)

$H_0$ does not contain any redundant arcs.

(c)

the different paths of $H_0$ are made up of either real or virtual arcs.

(d)

$H_0$ contains $2\left|X\right|$ vertices.

Dans le graphe $H_0$ on pose:

et

On vérifie aisément que les deux relations $R$ et $S$ sont des relations d’équivalence; soient ${ā}_0,\dots ,{ā}_L,{\bar{b}}_0,\dots ,{\bar{b}}_M$ les classes correspondantes sur $A$ et $B$.

On appelle contraction de type 1 l’opération qui consiste dans $H_0$ à contracter, en un sommet unique, tous les sommets d’une même classe.

In the graph $H_0$, we let

and

It is easy to verify that the two relations $R$ and $S$ are equivalence relations; ${ā}_0,\dots ,{ā}_L,{\bar{b}}_0,\dots ,{\bar{b}}_M$ are the corresponding classes on $A$ and $B$.

We call type 1 contraction the operation that contracts all vertices of $H_0$ of the same class to a single vertex.

Dans le graphe $H_0$ on effectue toutes les contractions possibles de type 1 et l’on note $H_1=\left(Y_1,V_1\right)$ le graphe obtenu.

L’application $f$ induit une application de $X\to V_1$ que l’on continue à noter $f$, pour simplifier les notations. Les sommets de $H_1$ seront notés ${ā}_1,\dots ,{ā}_L,{\bar{b}}_1,\dots ,{\bar{b}}_M$.

On vérifie aisément que les contractions de type 1 n’ont pas altéré les relations de succession et de non-succession du graphe $H_0$. D’autre part $f$ reste une application injective car si, par exemple, $f\left(i\right)$ et $f\left(j\right)$ ont, après contraction, même origine et même extrêmité, on les considère comme deux arcs différents. Au contraire si des arcs virtuels se trouvent doublés on ne les prend en compte qu’une seule fois.

(a)

$H_1$ ne contient ni circuit ni arc redondant.

(b)

Comme dans $H_0$, les chemins de $H_1$ sont constitués alternativement d’arcs réels et virtuels.

In the graph $H_0$, we perform all possible type 1 contractions and $H_1=\left(Y_1,V_1\right)$ is recorded as the obtained graph.

The mapping $f$ induces a mapping of $X\to V_1$ that we continue to note as $f$, to simplify the notation. The vertices of $H_1$ will be noted as ${ā}_1,\dots ,{ā}_L,{\bar{b}}_1,\dots ,{\bar{b}}_M$.

It is easy to verify that the type 1 contractions do not alter the succession and non-succession relations of graph $H_0$. On the other hand, $f$ remains an injective map if, for example, $f\left(i\right)$ and $f\left(j\right)$ are, after contraction, same origin and same destination, they are considered two different arcs. Contrarily, if the virtual arcs are duplicated, they are only taken into account once.

(a)

$H_1$ does not contain any circuits or redundant arcs.

(b)

Like in $H_0$, the paths of $H_1$ are either real arcs or virtual arcs.

Un arc $\left({\bar{b}}_i,{ā}_j\right)$ est un bon arc de $H_1\text{ ssi }$:

On appelle contraction de type 2 l’opération qui, dans $H_1$, consiste à contracter, en un sommet unique, le sommet origine et le sommet extrêmité d’un bon arc.

(a)

Montrons que ${\bar{b}}_i,{ā}_j$ et ${\bar{b}}_i,{ā}_l$ ne peuvent pas être simultanément deux bons arcs de $H_1$: (fig. 1).

Comme ${ā}_j$ et ${ā}_l$ sont deux sommets distincts de $H_1$, on a $𝒫\left(j\right)\ne 𝒫\left(l\right)$, donc il existe un sommet $h$ de $G$ tel que, par exemple, $h\in 𝒫\left(l\right)$ et $h\notin 𝒫\left(j\right)$. Ceci se traduit dans $H_1$ par l’existence de l’arc $\left({\bar{b}}_h,{ā}_l\right)$, alors qu’il n’existe pas d’arc $\left({\bar{b}}_h,{ā}_j\right)$.

Supposons que $\left({\bar{b}}_i,{ā}_l\right)$ soit un bon arc de $H_1$. Alors $h\in \mathbf{P}\left(l\right)$ et $j\in \mathbf{Q}\left(i\right)$ implique $h\in \tilde{\mathbf{P}}\left(j\right)$. Compte tenu du fait que $h\notin \mathbf{P}\left(j\right)$, il existe alors dans $H_1$ un chemin dont le premier arc est $f\left(h\right)$ et le dernier est $f\left(j\right)$ et contenant au moins un autre arc réel. Soit $f\left(e\right)$ l’arc de ce chemin tel que $e\in \mathbf{P}\left(j\right)$ dans $G$.

Supposons que l’arc $\left({\bar{b}}_i,{ā}_j\right)$ soit aussi un bon arc de $H_1$. Alors, $e\in \mathbf{P}\left(j\right)$ et $l\in \mathbf{Q}\left(i\right)$ implique $e\in \tilde{\mathbf{P}}\left(l\right)$. D’où, dans $H_1:f\left(e\right)\to f\left(l\right)$. Comme $f\left(h\right)\to f\left(e\right)$, on a: $f\left(h\right)\to f\left(l\right)$. Ceci implique que l’arc $\left(h,l\right)$ est redondant dans $G$, contrairement à l’hypothèse.

(b)

On démontre de même que deux arcs $\left({\bar{b}}_i,{ā}_j\right)$ et $\left({\bar{b}}_h,{ā}_j\right)$ ne peuvent pas être simultanément deux bons arcs de $H_1$.

An arc $\left({\bar{b}}_i,{ā}_j\right)$ is an good arc of $H_1\iff$:

We call contraction de type 2 an operation where, in $H_1$, consists of contraction, in one unique vertex, the origin vertex and destination vertex of a good arc.

(a)

Let us show that ${\bar{b}}_i,{ā}_j$ and ${\bar{b}}_i,{ā}_l$ can not simultaneously be two good arcs of $H_1$: (fig. 1)

Since ${ā}_j$ and ${ā}_l$ are two distinct vertcies of $H_1$, we have $𝒫\left(j\right)\ne 𝒫\left(l\right)$, so there exists a vertex $h$ of $G$ such that, for example, $h\in 𝒫\left(l\right)$ and $h\notin 𝒫\left(j\right)$. This is expressed in $H_1$ by the existence of the arc $\left({\bar{b}}_h,{ā}_l\right)$, then the arc $\left({\bar{b}}_h,{ā}_j\right)$ does not exist.

Suppose that $\left({\bar{b}}_i,{ā}_l\right)$ is a good arc of $H_1$. Then $h\in \mathbf{P}\left(l\right)$ and $j\in \mathbf{Q}\left(i\right)$ implies $h\in \tilde{\mathbf{P}}\left(j\right)$. Given the fact that $h\notin \mathbf{P}\left(j\right)$, there then exists an path in $H_1$ whose first arc is $f\left(h\right)$ and last is $f\left(j\right)$ and containing at least one other real arc. Let $f\left(e\right)$ be the arc of this path such that $e\in \mathbf{P}\left(j\right)$ in $G$.

Suppose that the arc $\left({\bar{b}}_i,{ā}_j\right)$ is also a good arc of $H_1$. Then, $e\in \mathbf{P}\left(j\right)$ and $l\in \mathbf{Q}\left(i\right)$ implies $e\in \tilde{\mathbf{P}}\left(l\right)$. Hence, in $H_1:f\left(e\right)\to f\left(l\right)$. Since $f\left(h\right)\to f\left(e\right)$, we have $f\left(h\right)\to f\left(l\right)$. This implies that the arc $\left(h,l\right)$ is redundant in $G$, contrary to the hypothesis.

(b)

We also show that two arcs $\left({\bar{b}}_i,{ā}_j\right)$ and $\left({\bar{b}}_h,{ā}_j\right)$ can not simultaneously be two good arcs of $H_1$.

Dans le graphe $H_1=\left(Y_1,V_1\right)$ on effectue toutes les contractions possibles de type 2.

Soit $H_2=\left(Y_2,V_2\right)$ le graphe obtenu.

Dans le but de simplifier les notations:

• on continue à noter les sommets de $H_2$ comme ceux de $H_1$ ;
• on continue à noter $f$ l’application de $X\to V_2$ induite par $f:X\to V_1$.

(a)

Il est immédiat que $f:X\to V_2$ reste une application injective.

(b)

Montrons qu’il existe un chemin de $f\left(e\right)$ vers $f\left(k\right)$ si et seulement si $e\in \widetilde{𝒫}\left(k\right)$:

($\alpha$)

$e\in \widetilde{𝒫}\left(k\right)$ implique $f\left(e\right)\to f\left(k\right)$: ceci résulte de la remarque 2.2.2;

($\beta$)

$f\left(e\right)\to f\left(k\right)$ implique $e\in \widetilde{𝒫}\left(k\right)$: en effet, $f\left(e\right)\to f\left(k\right)$ implique qu’il existe dans $H_2$ un chemin dont le premier arc est $f\left(e\right)$ et le dernier arc est $f\left(k\right)$. A cause de la transitivité de la relation de succession, on peut supposer que les arcs de ce chemin entre $f\left(e\right)$ et $f\left(k\right)$ sont tous virtuels (fig. 2).

In the graph $H_1=\left(Y_1,V_1\right)$ we perform all the possible type 2 contractions.

$H_2=\left(Y_2,V_2\right)$ is the obtained graph.

In order to simplify the notation:

• we continue to note the vertices of $H_2$ as those of $H_1$ ;
• we continue to note the mapping $f$ of $X\to V_2$ induced by $f:X\to V_1$.

(a)

It follows that that $f:X\to V_2$ remains an injective map.

(b)

We show that there exists a path from $f\left(e\right)$ to $f\left(k\right)$ if and only if $e\in \widetilde{𝒫}\left(k\right)$:

($\alpha$)

$e\in \widetilde{𝒫}\left(k\right)$ implies $f\left(e\right)\to f\left(k\right)$: this follows from remark 2.2.2;

($\beta$)

$f\left(e\right)\to f\left(k\right)$ implies $e\in \widetilde{𝒫}\left(k\right)$: indeed, $f\left(e\right)\to f\left(k\right)$ implies that there exists in $H_2$ a path whose first arc is $f\left(e\right)$ and last arc is $f\left(k\right)$. Because of the transitivity of the succession relation, we can suppose that the arc of this path between $f\left(e\right)$ and $f\left(k\right)$ are all virtual (fig. 2).

Les sommets intermédiaires $c_1,\dots ,c_n$ proviennent de la contraction des bons arcs $\left({\bar{b}}_{i_1},{ā}_{j_1}\right),\dots ,\left({\bar{b}}_{i_m},{ā}_{j_m}\right),\dots ,\left({\bar{b}}_{i_n},{ā}_{j_n}\right)$ de $H_1$ (fig. 3).

The intermediate vertices $c_1,\dots ,c_n$ from the contraction of the good arcs $\left({\bar{b}}_{i_1},{ā}_{j_1}\right),\dots ,\left({\bar{b}}_{i_m},{ā}_{j_m}\right),\dots ,\left({\bar{b}}_{i_n},{ā}_{j_n}\right)$ of $H_1$ (fig. 3).

Comme $\left({\bar{b}}_{i_1},{ā}_{j_1}\right)$ est un bon arc, $e\in 𝒫\left(j_1\right)$ et $j_2\in 𝒬\left(i_1\right)$ implique $e\in \widetilde{𝒫}\left(j_2\right)$. Comme $\left(b_{i_2},a_{j_2}\right)$ est un bon arc, et d’après la remarque 2.2.3, $e\in \widetilde{𝒫}\left(j_2\right)$ et $j_3\in 𝒬\left(i_2\right)$ implique $e\in \widetilde{𝒫}\left(j_3\right)$. On démontre ainsi de proche en proche que $e\in \widetilde{𝒫}\left(j_m\right)$ jusqu’à $m=n$, et finalement $e\in \widetilde{𝒫}\left(k\right)$.

Montrons que, parmi les graphes arcs-duaux du graphe $G,H_2$ a le nombre minimal de sommets. Ce sera une conséquence du théorème suivant.

Démonstration : $1^{\circ }$ Construction de $h$.

Soit $i\in X$, avec $g\left(i\right)=\left({\alpha }_i,{\beta }_i\right)$ et $f\left(i\right)=\left({ā}_i,{\bar{b}}_i\right)$ on pose $h\left({\alpha }_i\right)={ā}_i$ et $h\left({\beta }_i\right)={\bar{b}}_i$.

$2^{\circ }$ Montrons que $h$ est bien définie.

Soit $j\in X,j\ne i$, avec $g\left(j\right)=\left({\alpha }_j,{\beta }_j\right)$ et $f\left(j\right)=\left({ā}_j,{\bar{b}}_j\right)$; posons $h\left({\alpha }_j\right)={ā}_j$ et $h\left({\beta }_j\right)={\bar{b}}_j$

(a) Montrons que si ${\alpha }_j={\alpha }_i$ dans $H$ alors ${ā}_j={ā}_i$ dans $H_2$. Il faut donc montrer que $𝒫\left(i\right)=𝒫\left(j\right)$ dans $G$. Soit $k\in 𝒫\left(i\right)$. Comme $H$ est arc-dual de $G$, on a $g\left(k\right)\to g\left(i\right)$. Comme $g\left(i\right)$ et $g\left(j\right)$ ont la même origine, on a $g\left(k\right)\to g\left(j\right)$, d’où $k\in \widetilde{𝒫}\left(j\right)$ dans $G$. Si on avait $k\notin 𝒫\left(j\right)$, il existerait un sommet $l$ de $G$ tel que $l\in 𝒫\left(j\right)$ et $k\in \widetilde{𝒫}\left(l\right)$ (fig. 4).

Since $\left({\bar{b}}_{i_1},{ā}_{j_1}\right)$ is a good arc, $e\in 𝒫\left(j_1\right)$ and $j_2\in 𝒬\left(i_1\right)$ implies $e\in \widetilde{𝒫}\left(j_2\right)$. Since $\left(b_{i_2},a_{j_2}\right)$ is a good arc, and according to remark 2.2.3, $e\in \widetilde{𝒫}\left(j_2\right)$ and $j_3\in 𝒬\left(i_2\right)$ implies $e\in \widetilde{𝒫}\left(j_3\right)$. We thus prove step by step that $e\in \widetilde{𝒫}\left(j_m\right)$ up to $m=n$, and finally $e\in \widetilde{𝒫}\left(k\right)$.

We show that, among the dual-arc graphs of $G$, $H_2$ has the minimal number of vertices. This will be a consequence of the following theorem.

Demonstration : $1^{\circ }$ Construction of $h$.

Let $i\in X$, with $g\left(i\right)=\left({\alpha }_i,{\beta }_i\right)$ and $f\left(i\right)=\left({ā}_i,{\bar{b}}_i\right)$ we pose $h\left({\alpha }_i\right)={ā}_i$ and $h\left({\beta }_i\right)={\bar{b}}_i$.

$2^{\circ }$ Let us show that $h$ is well-defined.

Let $j\in X,j\ne i$, with $g\left(j\right)=\left({\alpha }_j,{\beta }_j\right)$ and $f\left(j\right)=\left({ā}_j,{\bar{b}}_j\right)$; let us pose $h\left({\alpha }_j\right)={ā}_j$ and $h\left({\beta }_j\right)={\bar{b}}_j$

(a) Let us show that if ${\alpha }_j={\alpha }_i$ in $H$ then ${ā}_j={ā}_i$ in $H_2$. We must therefore show that $𝒫\left(i\right)=𝒫\left(j\right)$ in $G$. Let $k\in 𝒫\left(i\right)$. Since $H$ is a dual-arc of $G$, we have $g\left(k\right)\to g\left(i\right)$. Since $g\left(i\right)$ and $g\left(j\right)$ have the same origin, we have $g\left(k\right)\to g\left(j\right)$, hence $k\in \widetilde{𝒫}\left(j\right)$ in $G$. If we had $k\notin 𝒫\left(j\right)$, there would exist a vertex $l$ of $G$ such that $l\in 𝒫\left(j\right)$ and $k\in \widetilde{𝒫}\left(l\right)$ (fig. 4).

Comme ci-dessus, du fait que $l\in 𝒫\left(j\right)$ et que $g\left(i\right)$ et $g\left(j\right)$ ont la même origine, on a $g\left(l\right)\to g\left(i\right)$, et $l\in 𝒫\left(i\right)$. L’arc $\left(k,i\right)$ serait alors redondant dans $G$, contrairement à l’hypothèse. Donc $k\in 𝒫\left(j\right)$, et $𝒫\left(i\right)=𝒫\left(j\right)$.

(b) On démontre de même que si ${\beta }_j={\beta }_i$, alors ${\bar{b}}_j={\bar{b}}_i$.

(c) Montrons que si ${\beta }_i={\alpha }_j$ dans $H$ alors ${\bar{b}}_i={ā}_j$ dans $H_2$. Montrons d’abord que ${\beta }_i={\alpha }_j$ dans $H$ implique que $i\in 𝒫\left(j\right)$ dans $G$. En effet, on a $g\left(i\right)\to g\left(j\right)$, d’où $i\in \widetilde{𝒫}\left(j\right)$. Si on avait $i\notin 𝒫\left(j\right)$, il existerait $e$ tel que $e\in 𝒫\left(j\right)$ et $i\in \widetilde{𝒫}\left(e\right)$ dans $G$ (fig. 5).

As above, since $l\in 𝒫\left(j\right)$ and since $g\left(i\right)$ and $g\left(j\right)$ have the same origin, we have $g\left(l\right)\to g\left(i\right)$, and $l\in 𝒫\left(i\right)$. The arc $\left(k,i\right)$ would then be redundant in $G$, contrary to the hypothesis. So $k\in 𝒫\left(j\right)$, and $𝒫\left(i\right)=𝒫\left(j\right)$.

(b) We prove in the same way that if ${\beta }_j={\beta }_i$, then ${\bar{b}}_j={\bar{b}}_i$.

(c) Let us show that if ${\beta }_i={\alpha }_j$ in $H$ then ${\bar{b}}_i={ā}_j$ in $H_2$. Let us first show that ${\beta }_i={\alpha }_j$ in $H$ implies that $i\in 𝒫\left(j\right)$ in $G$. Indeed, we have $g\left(i\right)\to g\left(j\right)$, hence $i\in \widetilde{𝒫}\left(j\right)$. If we had $i\notin 𝒫\left(j\right)$, there would exist $e$ such that $e\in 𝒫\left(j\right)$ and $i\in \widetilde{𝒫}\left(e\right)$ in $G$ (fig. 5).

D’où, dans $H$, $g\left(i\right)\to g\left(e\right)$ et $g\left(e\right)\to g\left(j\right)$, ce que entraînerait l’existence dans $H$ d’un circuit contenant l’arc réel $g\left(e\right)$, contrairement à la remarque 1.1. On a donc $i\in 𝒫\left(j\right)$, donc $\left({\bar{b}}_i,{ā}_j\right)$ est un arc virtuel de $H_1$.

Pour montrer que ${\bar{b}}_i={ā}_j$ dans $H_2$, il reste donc à montrer que $\left({\bar{b}}_i,{ā}_j\right)$ est un bon arc de $H_1$. Soit donc $k\in 𝒫\left(j\right)$ et $l\in 𝒬\left(i\right)$. Alors, $g\left(k\right)\to g\left(j\right)$ et $g\left(i\right)\to g\left(l\right)$. Comme l’origine de $g\left(j\right)$ est aussi l’extrémité de $g\left(i\right)$, on a $g\left(k\right)\to g\left(l\right)$, d’où $k\in \widetilde{𝒫}\left(l\right)$.

Hence, in $H$, $g\left(i\right)\to g\left(e\right)$ and $g\left(e\right)\to g\left(j\right)$ would entail the existence in $H$ of a circuit containing the real arc $g\left(e\right)$, contradicting remark 1.1. So we have $i\in 𝒫\left(j\right)$, so $\left({\bar{b}}_i,{ā}_j\right)$ is a virtual arc of $H_1$.

To show that ${\bar{b}}_i={ā}_j$ in $H_2$, it remains to show that $\left({\bar{b}}_i,{ā}_j\right)$ is a good arc of $H_1$. So let $k\in 𝒫\left(j\right)$ and $l\in 𝒬\left(i\right)$. Then, $g\left(k\right)\to g\left(j\right)$ and $g\left(i\right)\to g\left(l\right)$. Since the origin of $g\left(j\right)$ is also the destination of $g\left(i\right)$, we have $g\left(k\right)\to g\left(l\right)$, hence $k\in \widetilde{𝒫}\left(l\right)$.

On décrit maintenant les constructions précédentes sous form algorithmique. Les sections 1, 2, et 3 correspondent à la construction de $H_0$ et $H_1$. La section 4 correspond à la détermination des bons arcs. La section 4.2 est facultative, mais permet une économie d’opérations quand elle vient à être utilisée. L’utilisation de la liste $T$ dans 4.2 et 4.3 permet d’exploiter la propriété démontrée dans le théorème 1. La section 4.5 donne la description finale du graphe $H_2$ cherché.

On suppose donné le graphe français $G$, done les arcs redondants ont été supprimés (par exemple en utilisant les parties I et II de l’algorithme donné dans [6]). Les sommets de $G$ (les tâches) sont représentés par les entiers $i=1,\dots ,N$. Pour tout $i$, on connait les listes $𝒫\left(i\right),𝒬\left(i\right),\text{ et }\widetilde{𝒫}\left(i\right)$.

2. On détermine la partition $\left\{1,\dots ,N\right\}$ en classes $D_1,\dots ,D_M$ $i$ et $j$ appartiennent à la même classe si et seulement si $𝒬\left(i\right)=𝒬\left(j\right)$. On dresse une liste $j_1,\dots ,j_M$ constituée d’un représentant dans chaque classe.

3. Pour tout $l$, $1\le l\le L$, on consitue la liste:

et la liste:

Pour tout $m,1\le m\le M$, on constitue la liste:

4. On pose $m=0$. On utilise une liste $T$, indexée de $1$ à $M$, vide au départ.

4.1 Augmenter $m$ d’une unité; si $m>M$ aller en 4.5.

Si $W\left(j_m\right)=\varnothing$ aller en 4.1.

Si $\left|W\left(j_m\right)\right|=1$, soit $\left\{i_l\right\}=W\left(j_m\right)$, aller en 4.4.

4.2 Soit $E={\left(\cap V\left(s\right)\right)}_{s\in W\left(j_m\right)}$. S’il existe $i_l\in W\left(j_m\right)$ tel que $V\left(i_l\right)=E$ et $i_l$ ne figure pas dans $T$, alors aller en 4.4.

4.3 Soit $F={\left(\cap \tilde{V}\left(s\right)\right)}_{s\in W\left(j_m\right)}$. S’il existe $i_l\in W\left(j_m\right)$ tel que $V\left(i_l\right)\subset F$ et $i_l$ ne figure pas dans $T$, alors aller en 4.4, sinon aller en 4.1.

4.4 On pose $T\left(m\right)=i_l$.

Aller en 4.1.

4.5 L’ensemble des sommets du graphe cherché $H_2$ est l’ensemble des entiers: $\left\{2j_1,\dots ,2j_M\right\}\cup \left\{2i_l+1|i_l\text{ ne figure pas dans }T,1\le l\le L\right\}$.

L’ensemble des arcs des $H_2$ est:

Arcs réels : Pour tout $i\in \left\{1,\dots ,N\right\}$, soient $l$ et $m$ tels que $i\in C_l$ et $i\in D_m$:

• $\mathrm{arc}\left(2i_l+1,2j_m\right)$ si $i_l$ ne figure pas dans $T$;
• $\mathrm{arc}\left(2j_k,2j_m\right)$ si $i_l=T\left(k\right)$.

Arc virtuels : Pour tout $m\in \left\{1,\dots ,M\right\}$ et tout $i_l\in W\left(j_m\right)$ :

• $\mathrm{Arc}\left(2j_m,2i_l+1\right)$ si $i_l$ ne figure pas dans $T$;
• $\mathrm{arc}\left(2j_m,2j_k\right)$ si $i_l=T\left(k\right),k\ne m$.

Pour cela il suffit de remarquer que, lorsque la section 4.2 est utilisée et qu’il existe $i_l\in W\left(j_m\right)$ tel que $V\left(i_l\right)=E$, $i_l$ ne figurant pas dans $T$, alors les arcs $\left(j_k,i_s\right)$, $\forall j_k\in V\left(i_l\right)-\left\{j_m\right\},\forall i_s\in W\left(j_m\right)-\left\{i_l\right\}$, deviennent redondants dans la contraction de type 2 relative au bon arc $\left(j_m,i_l\right)$. Il est alors possible de retirer: