Probleme – Biparti si et seulement si aucun cycle impair

1. La réciproque. Supposons $G$ sans cycle impair. Il suffit de traiter une composante connexe, puis de réunir les parties obtenues.

Soit donc $G$ connexe, et $s$ un sommet quelconque. Notons $\delta (u)$ la distance de $s$ à $u$ — le nombre minimal d'arêtes d'un chemin de $s$ à $u$ —, définie pour tout $u$ par connexité. Posons

$$X=\{u:\delta (u)\text{ pair}\},Y=\{u:\delta (u)\text{ impair}\}.$$

Ces deux ensembles partagent $S$. Montrons que toute arête relie $X$ à $Y$.

Soit $\{u,v\}$ une arête. D'abord $|\delta (u)-\delta (v)|\le 1$ : un chemin optimal vers $u$ prolongé par l'arête donne un chemin vers $v$, donc $\delta (v)\le \delta (u)+1$, et symétriquement. Il reste à écarter $\delta (u)=\delta (v)$.

Supposons $\delta (u)=\delta (v)=\ell$. Prenons un chemin optimal $P_u$ de $s$ à $u$ et un chemin optimal $P_v$ de $s$ à $v$. Le long d'un chemin optimal, la distance croît strictement de $1$ à chaque pas : le $i$-ième sommet de $P_u$ est à distance $i$. Soit alors $w$ le sommet commun aux deux chemins de plus grande distance $\delta (w)$ — il en existe, $s$ étant commun.

Les portions de $P_u$ et de $P_v$ allant de $w$ à $u$ et de $w$ à $v$ ne se rencontrent qu'en $w$ : un autre sommet commun serait à distance strictement supérieure à $\delta (w)$, contredisant le choix de $w$. Leurs longueurs valent $\ell -\delta (w)$ chacune, un sous-chemin d'un chemin optimal étant optimal, et $\ell -\delta (w)\ge 1$ car $w=u$ entraînerait $w=v$, donc $u=v$. En concaténant les deux portions et l'arête $\{u,v\}$, on obtient un cycle de longueur

$$2(\ell -\delta (w))+1\ge 3,$$

qui est impair — et c'est bien un cycle, sans répétition d'arête, les deux portions étant disjointes hors de $w$. Contradiction. Donc $\delta (u)\ne \delta (v)$, d'où $|\delta (u)-\delta (v)|=1$ et les deux extrémités sont de parités différentes : l'arête relie $X$ à $Y$.

2. L'algorithme. La démonstration est effective : elle donne la bipartition, $\delta$ se calcule par un parcours en largeur, et la contradiction est un test.

(* Renvoie Some couleur si g est biparti (couleur.(u) vaut 0 ou 1),
   None sinon. n sommets, listes d'adjacence g. Complexité : Theta(n + m). *)
let bicolorer n g =
  let couleur = Array.make n (-1) in
  let biparti = ref true in
  for s = 0 to n - 1 do
    if couleur.(s) = -1 then begin        (* une composante non encore vue *)
      couleur.(s) <- 0;
      let f = Queue.create () in
      Queue.push s f;
      while not (Queue.is_empty f) do
        let u = Queue.pop f in
        List.iter (fun v ->
          if couleur.(v) = -1 then begin
            couleur.(v) <- 1 - couleur.(u);      (* on ALTERNE *)
            Queue.push v f
          end
          else if couleur.(v) = couleur.(u) then biparti := false) g.(u)
      done
    end
  done;
  if !biparti then Some couleur else None

Correction : l'invariant du parcours est couleur.(u) $=\delta (u)\mathrm{mod}2$ pour tout sommet colorié — vrai à l'initialisation, et conservé puisqu'on colorie chaque nouveau sommet de la couleur opposée à celle de son découvreur, et que le parcours en largeur découvre chaque sommet par un chemin optimal. Le test couleur.(v) = couleur.(u) détecte donc exactement une arête entre deux sommets de même parité, c'est-à-dire, par la démonstration ci-dessus, un cycle impair.

Complexité : chaque sommet est empilé une fois et chaque arête examinée deux fois — une par extrémité —, soit $\Theta (n+m)$ en temps et $\Theta (n)$ en mémoire. C'est le coût d'un simple parcours, et il faut le mesurer à l'aune de l'alternative : chercher un cycle impair en énumérant les cycles serait exponentiel. Une caractérisation combinatoire ne donne pas toujours un algorithme ; celle-ci, si, et c'est ce qui la rend précieuse.

3. Ce que l'algorithme rend en cas d'échec. L'arête fautive $\{u,v\}$ est un certificat : en remontant les arbres du parcours depuis $u$ et depuis $v$ jusqu'à leur ancêtre commun, on reconstruit un cycle impair explicite. C'est une qualité qu'il faut exiger d'un algorithme de décision : répondre « non » sans preuve oblige l'utilisateur à faire confiance ; répondre « non, voici pourquoi » se vérifie en $O(n)$.

4. Les mises à l'épreuve. Mesuré, chaque réponse confrontée à une recherche indépendante de cycle impair :

Les deux colonnes centrales sont toujours opposées : la caractérisation est confirmée sur les six cas. Deux remarques que ce tableau suggère. Tout arbre est biparti — il n'a aucun cycle, donc aucun cycle impair, et la bipartition est le partage par la parité de la profondeur. Et les cycles pairs $C_4$, $C_6$, … sont bipartis tandis que $C_3$, $C_5$, … ne le sont pas : ce sont les exemples minimaux des deux côtés.

À quoi cela sert. La bipartition est le modèle de tout appariement : étudiants et stages, tâches et machines, offres et demandes. Savoir en $\Theta (n+m)$ si un graphe est biparti, c'est savoir si le problème d'appariement s'y pose — et le programme cite la bicolorabilité au chapitre chap:parcours précisément à ce titre.