Comment éviter le cyclage ?

On va voir, qu'un choix judicieux des arcs sortants permet d'éliminer tout risque de cyclage.

Théorème (Linear Programming de Vasek Chvátal p. 308)
On fixe un noeud quelconque comme racine pour toutes les itérations. Si lors de chaque situation dégénérée l'arc entrant n'est pas dirigé vers la racine, alors l'algorithme ne cycle pas.

Démonstration
On appelle T_i l'i-ième arbre solution. Soit r la racine de tous les T_i. On note z(T) le coût de l'arbre solution T. Enfin on définit f(T) par la formule suivante :

$$\begin{eqnarray*}f(T) &=& \sum_{k = 1}^{n}(c[k] - c[r])\\ \end{eqnarray*}$$

On suppose que l'hypothèse du théorème est vérifiée, c'est à dire que lors de toute itération dégénérée, l'arc entrant n'est pas dirigé vers r.

Dans un premier temps, considérons l'arbre T_i et supposons que l'i-ème itération est dégénérée. Soit c = c[b] - c[a] - c(a,b) si (a,b) est l'arc entrant. Notons c'[k] le coût relatif du noeud k dans l'arbre T_{i + 1}. Alors on a : c'[k] = c[k] - c si k appartient au sous-arbre de racine b et c[k] sinon. Donc : f(T_{i + 1}) < f(T_i)

À présent, on suppose par l'absurde qu'il existe i et j tel que T_i = T_j. Donc z(T_i) = z(T_j). Les étapes i, i + 1, ...,j - 1 sont dégénérées. Donc d'après ce que l'on a vu précédemment : f(T_j) < f(T_{j - 1}) < ... < f(T_i). Ceci contredit l'hypothèse T_i = T_j. Donc le théorème est vérifié.

Définition
Appelons bon arbre, un arbre dont aucun arc de poids zéro n'est dirigé vers la racine.

Corollaire évident du théorème
Si on se fixe une racine, et si durant l'algorithme tous les arbres sont bons, alors il n'y a pas cyclage.

Tactique pour éviter le cyclage de W. H. Cunningham (1976)
On part d'un bon arbre. Ensuite, il faut choisir correctement l'arc sortant pour chaque itération. On appelle J le noeud du cycle de plus faible profondeur, c'est à dire le noeud le plus "proche" de la racine. J peut éventuellement être la racine.

Cas non dégénéré
En considérant la figure 2.2, l'arc sortant est l'arc candidat à la sortie le plus haut dans la partie gauche du cycle.

 

Figure 2.2: Exemple

Cas dégénéré
En considérant la figure 2.3, l'arc sortant est l'arc nul le plus bas dans la partie droite du cycle.

 

Figure 2.3: Exemple