Bicolorabilité par un parcours en largeur

(* Renvoie (couleurs, temoin) : temoin vaut Some (u, v) si l'arete u-v joint
   deux sommets de meme couleur, None si le graphe est biparti.
   Precondition : g non oriente, connexe depuis s.
   Complexite : Theta(n + m), celle du parcours. *)
let bicolore g s =
  let n = Array.length g in
  let coul = Array.make n (-1) in
  let f = Queue.create () in
  coul.(s) <- 0; Queue.push s f;
  let temoin = ref None in
  while not (Queue.is_empty f) do
    let u = Queue.pop f in
    List.iter (fun v ->
      if coul.(v) = -1 then begin
        coul.(v) <- 1 - coul.(u);            (* la couleur OPPOSEE *)
        Queue.push v f
      end else if coul.(v) = coul.(u) then temoin := Some (u, v)) g.(u)
  done;
  (coul, !temoin)

Mesures :

C6 : couleurs 0 1 0 1 0 1 ; BIPARTI
C5 : couleurs 0 1 0 0 1   ; PAS biparti (arete 3-2)

Pourquoi cela décide. Le parcours donne $\mathrm{coul}(v)=d(v)\mathrm{mod}2$ : chaque sommet reçoit la parité de sa distance à la source. Deux cas.

• Si aucune arête ne joint deux sommets de même couleur, la partition en classes de parité est une bicoloration : le graphe est biparti.
• Si une arête $\{u,v\}$ joint deux sommets de même parité, alors le chemin de $s$ à $u$ dans l'arborescence, l'arête $\{u,v\}$, et le chemin de $v$ à $s$ forment une promenade fermée de longueur $d(u)+1+d(v)$, impaire puisque $d(u)$ et $d(v)$ ont même parité. Or une promenade fermée impaire contient toujours un cycle impair. Et un graphe contenant un cycle impair n'est pas biparti : en parcourant ce cycle, les couleurs devraient alterner et revenir au point de départ, ce qui exige une longueur paire.

L'algorithme rend donc un certificat dans les deux sens : une coloration si le graphe est biparti, une arête fautive sinon — et de cette arête on tire un cycle impair explicite. C'est la réciproque annoncée au chapitre chap:graphes, rendue effective en $\Theta (n+m)$.

Un détail à ne pas manquer : sur $C_5$, le témoin mesuré est l'arête $3-2$, et les couleurs sont $[0;1;0;0;1]$ — la faute apparaît entre deux sommets tous deux déjà coloriés. Un algorithme qui ne testerait la couleur qu'au moment de la découvrir ne verrait jamais rien : c'est le test du else if qui décide, pas celui du if.