Probleme – Affecter des étudiants à des stages

1. L'algorithme, rendant l'affectation.

(* Couplage de cardinal maximum dans un graphe biparti.
   Entrees : g.(u) = liste des stages souhaites par l'etudiant u (0 a p-1),
             q = nombre de stages.
   Sortie  : (cardinal, conj) ou conj.(v) = Some u si le stage v va a u.
   Complexite : O(p * m), m = nombre total de voeux. *)
let couplage g q =
  let p = Array.length g in
  let conj = Array.make q None in
  (* Cherche un chemin augmentant depuis u. vu.(v) : stage deja tente
     dans CETTE recherche -- sans lui, la recursion pourrait boucler. *)
  let rec augmenter vu u =
    List.exists (fun v ->
      if vu.(v) then false
      else begin
        vu.(v) <- true;
        match conj.(v) with
        | None -> conj.(v) <- Some u; true          (* stage libre : on prend *)
        | Some w ->                                 (* pris : w se recase ? *)
            if augmenter vu w then begin conj.(v) <- Some u; true end
            else false
      end) g.(u)
  in
  let cardinal = ref 0 in
  for u = 0 to p - 1 do
    if augmenter (Array.make q false) u then incr cardinal
  done;
  (!cardinal, conj)

2. Terminaison et correction.

Terminaison. La boucle extérieure fait $p$ tours. Pour augmenter, le variant est le nombre de stages non encore marqués dans vu : chaque appel récursif est précédé d'un vu.(v) <- true, donc ce nombre décroît strictement. Il est positif : la récursion s'arrête après au plus $q$ niveaux.

Invariant de la boucle extérieure : après le tour $u$, conj représente un couplage de cardinal maximum du sous-graphe induit par les étudiants $0,\dots ,u$.

Conservation. Deux points. D'abord, conj reste un couplage : une affectation conj.(v) <- Some u n'a lieu que si $v$ était libre, ou si son ancien occupant $w$ vient d'être recasé ailleurs. Ensuite, la maximalité : si augmenter réussit, le cardinal monte de $1$, ce qui est le maximum possible en ajoutant un sommet ; si elle échoue, c'est qu'il n'existe aucun chemin augmentant depuis $u$, et un théorème classique assure qu'alors le cardinal maximum n'a pas augmenté.

Conclusion. À la sortie, aucun chemin augmentant n'existe depuis aucun étudiant : par le théorème de Berge du chapitre, le couplage est de cardinal maximum.

Vérification : sur $5000$ graphes bipartis tirés au hasard, le cardinal rendu coïncide avec celui d'une force brute sur tous les sous-ensembles d'arêtes — aucun désaccord.

3. Complexité. Une recherche de chemin augmentant visite chaque stage au plus une fois (grâce à vu) et parcourt, pour chaque étudiant rencontré, sa liste de vœux : $O(m)$. Il y a $p$ recherches. Total $O(pm)$, soit $O(nm)$ avec les notations du chapitre.

Sur l'exemple à cinq étudiants de l'exercice « Le recasage, pas à pas », l'affectation obtenue est

$$e_0\to s_0,e_2\to s_1,e_1\to s_2,e_3\to s_3,e_4\to s_4,$$

de cardinal $5$ : tout le monde est placé. La trace de cet exercice montre que ce résultat exige deux recasages en cascade — un glouton l'aurait manqué.

4. Quand tout le monde n'est pas plaçable. Il ne faut pas répondre « impossible » : il faut répondre pourquoi. L'ensemble $S$ des étudiants visités lors de la dernière recherche infructueuse vérifie $|N(S)|<|S|$ : c'est le certificat de Hall de l'exercice « Hall et König ». Le service apprend ainsi quels stages manquent, et de combien.

C'est un principe général et il vaut d'être retenu : un algorithme d'optimisation qui échoue doit rendre un certificat d'impossibilité, pas un simple refus. Ici le certificat est gratuit — il est déjà calculé.