Le recasage, pas à pas

e0 : s0, s1     e1 : s0, s2     e2 : s1, s2     e3 : s2, s3     e4 : s3, s4

e0 : essaie s0 -- LIBRE                                  --> e0-s0
e1 : essaie s0 -- pris par e0 ; e0 se recase en s1       --> e0-s1, e1-s0
e2 : essaie s1 -- pris par e0 ; e0 essaie s0
                 -- pris par e1 ; e1 se recase en s2     --> e1-s2, e0-s0, e2-s1
e3 : essaie s2 -- pris par e1 ; e1 essaie s0
                 -- pris par e0 ; e0 essaie s1
                 -- pris par e2 ; e2 n'a plus rien       --> ECHEC de la branche
     essaie s3 -- LIBRE                                  --> e3-s3
e4 : essaie s3 -- pris par e3 ; e3 essaie s2 ... echec en cascade
     essaie s4 -- LIBRE                                  --> e4-s4

Résultat : $\{e_0{s}_0,e_2{s}_1,e_1{s}_2,e_3{s}_3,e_4{s}_4\}$, de cardinal $5$ — tout le monde est placé. Une force brute sur les $2^{10}$ sous-ensembles d'arêtes confirme que $5$ est le maximum.

Trois choses à observer.

Le recasage est récursif, et il l'est réellement : au traitement de $e_2$, la chaîne fait bouger deux étudiants. C'est un chemin augmentant de longueur $5$ : $e_2\to s_1\to e_0\to s_0\to e_1\to s_2$, alternant hors-couplage et dans-couplage.

Le tableau vu sert à ne pas tourner en rond. Au traitement de $e_3$, la première branche échoue précisément parce que $s_1$ a déjà été visité : sans ce marquage, $e_2$ redemanderait $s_1$ et l'on boucherait. C'est le même rôle que le tableau des sommets visités d'un parcours en profondeur — parce que c'en est un.

L'échec d'une branche n'est pas l'échec de l'étudiant. $e_3$ échoue sur $s_2$ et réussit sur $s_3$. On explore donc bien un arbre de choix, avec retour en arrière : c'est l'exploration du chapitre chap:exploration, appliquée à la recherche d'un chemin augmentant.