5- Graphes avancés

Dans tout ce chapitre, les sommets d'un graphe à sommets sont numérotés de à , et le graphe est représenté par ses listes d'adjacence : un tableau g de type int list array, où g.(s) est la liste des voisins de s.

OCaml

Loading editor...

(* un graphe non orienté à 8 sommets, en deux morceaux *)
let g = [| [1; 2]; [0; 2; 3]; [0; 1]; [1; 4]; [3]; [6; 7]; [5; 7]; [5; 6] |];;
afficher_graphe g;;

I. Parcours

a) Parcours générique

Un parcours part d'un sommet, et visite de proche en proche tous les sommets accessibles. On garde en mémoire les sommets déjà vus, pour ne pas les visiter deux fois, et une structure contenant les sommets à traiter :

avec une file, on obtient le parcours en largeur (les sommets par distance croissante au départ) ;
avec une pile, ou avec des appels récursifs, le parcours en profondeur.

OCaml

Loading editor...

(* parcours en profondeur récursif : renvoie la liste des sommets dans l'ordre de visite *)
let profondeur (g : int list array) (depart : int) : int list =
  let vu = Array.make (Array.length g) false in
  let ordre = ref [] in
  let rec visiter s =
    if not vu.(s) then begin
      vu.(s) <- true;
      ordre := s :: !ordre;
      List.iter visiter g.(s)
    end
  in
  visiter depart;
  List.rev !ordre;;

(* parcours en largeur, avec une file (module Queue d'OCaml) *)
let largeur (g : int list array) (depart : int) : int list =
  let vu = Array.make (Array.length g) false in
  let file = Queue.create () in
  let ordre = ref [] in
  vu.(depart) <- true;
  Queue.add depart file;
  while not (Queue.is_empty file) do
    let s = Queue.pop file in
    ordre := s :: !ordre;
    List.iter (fun v -> if not vu.(v) then begin vu.(v) <- true; Queue.add v file end) g.(s)
  done;
  List.rev !ordre;;

animer_parcours g (profondeur g 0);;
animer_parcours g (largeur g 0);;

b) Arborescence d'un parcours

En notant, pour chaque sommet, le sommet depuis lequel on l'a découvert (son père), on obtient un arbre : l'arborescence du parcours, enracinée au sommet de départ.

Par exemple, pour le parcours en largeur depuis 0 du graphe ci-dessus, l'arborescence est formée des arêtes en rouge (les sommets 5, 6 et 7 ne sont pas accessibles depuis 0) :

OCaml

Loading editor...

let peres_largeur (g : int list array) (depart : int) : int array =
  let pere = Array.make (Array.length g) (-1) in
  let vu = Array.make (Array.length g) false in
  let file = Queue.create () in
  vu.(depart) <- true;
  Queue.add depart file;
  while not (Queue.is_empty file) do
    let s = Queue.pop file in
    List.iter (fun v ->
      if not vu.(v) then begin vu.(v) <- true; pere.(v) <- s; Queue.add v file end) g.(s)
  done;
  pere;;

let pere = peres_largeur g 0;;
let aretes = List.filter (fun (p, _) -> p >= 0) (List.init (Array.length g) (fun s -> (pere.(s), s)));;
animer_parcours ~aretes g (largeur g 0);;

Complexité

Chaque sommet accessible est traité une fois, et chacune de ses listes d'adjacence parcourue une fois : un parcours est en , où est le nombre de sommets et le nombre d'arêtes.

II. Applications des parcours

a) Composantes connexes

Dans un graphe non orienté, la composante connexe d'un sommet est l'ensemble des sommets accessibles depuis lui. On numérote les composantes en lançant un parcours depuis chaque sommet pas encore vu :

Par exemple, le graphe ci-dessus a deux composantes connexes :

OCaml

Loading editor...

let composantes (g : int list array) : int array =
  let comp = Array.make (Array.length g) (-1) in
  let rec visiter s c =
    if comp.(s) = -1 then begin
      comp.(s) <- c;
      List.iter (fun v -> visiter v c) g.(s)
    end
  in
  let nb = ref 0 in
  for s = 0 to Array.length g - 1 do
    if comp.(s) = -1 then begin visiter s !nb; incr nb end
  done;
  comp;;

composantes g;;

b) Recherche d'un cycle

Un graphe non orienté contient un cycle si et seulement si un parcours en profondeur rencontre un sommet déjà vu, qui n'est pas le père du sommet courant.

Dans le graphe ci-dessous, le parcours en profondeur depuis 0 visite 0, puis 1, puis 2 ; depuis 2, il rencontre 0, déjà vu, qui n'est pas le père de 2 : il y a un cycle (en rouge).

OCaml

Loading editor...

let a_un_cycle (g : int list array) : bool =
  let vu = Array.make (Array.length g) false in
  let cycle = ref false in
  let rec visiter s pere =
    vu.(s) <- true;
    List.iter (fun v ->
      if not vu.(v) then visiter v s
      else if v <> pere then cycle := true) g.(s)
  in
  for s = 0 to Array.length g - 1 do
    if not vu.(s) then visiter s (-1)
  done;
  !cycle;;

a_un_cycle g;;
a_un_cycle [| [1]; [0; 2]; [1; 3]; [2] |];;

Pour construire le cycle, il suffit de remonter les pères depuis le sommet courant jusqu'au sommet déjà vu.

c) Bicolorabilité

Un graphe est biparti (ou bicolorable) si on peut colorier ses sommets avec deux couleurs, de sorte que deux sommets voisins aient toujours des couleurs différentes. On colorie pendant un parcours : chaque voisin reçoit la couleur opposée ; s'il a déjà la même couleur, c'est impossible.

Plus généralement, un graphe est bicolorable si et seulement s'il ne contient pas de cycle de longueur impaire.

OCaml

Loading editor...

let bicolore (g : int list array) : int array option =
  let couleur = Array.make (Array.length g) (-1) in
  let possible = ref true in
  let rec visiter s c =
    couleur.(s) <- c;
    List.iter (fun v ->
      if couleur.(v) = -1 then visiter v (1 - c)
      else if couleur.(v) = c then possible := false) g.(s)
  in
  for s = 0 to Array.length g - 1 do
    if couleur.(s) = -1 then visiter s 0
  done;
  if !possible then Some couleur else None;;

let carre = [| [1; 3]; [0; 2]; [1; 3]; [0; 2] |];;
bicolore carre;;
bicolore g;;   (* 0, 1, 2 forment un triangle *)

d) États accessibles d'un automate

Un automate est un graphe orienté (les transitions sont les arcs). Les états accessibles sont les sommets atteints par un parcours depuis les états initiaux ; les autres états peuvent être supprimés sans changer le langage reconnu.

OCaml

Loading editor...

(* transitions : (départ, lettre, arrivée) *)
let accessibles (n : int) (initiaux : int list) (transitions : (int * string * int) list) : int list =
  let g = Array.make n [] in
  List.iter (fun (q, _, q') -> g.(q) <- q' :: g.(q)) transitions;
  let vu = Array.make n false in
  let rec visiter q = if not vu.(q) then begin vu.(q) <- true; List.iter visiter g.(q) end in
  List.iter visiter initiaux;
  List.filter (fun q -> vu.(q)) (List.init n (fun q -> q));;

let transitions = [(0, "a", 1); (1, "b", 0); (2, "a", 1); (3, "b", 3)];;
afficher_automate 4 [0] [1] transitions;;
accessibles 4 [0] transitions;;

e) Plus courts chemins à distance unitaire

Quand toutes les arêtes ont le même poids, le parcours en largeur visite les sommets par distance croissante au départ : il calcule les plus courts chemins (en nombre d'arêtes), en , sans avoir besoin de l'algorithme de Dijkstra.

OCaml

Loading editor...

let distances (g : int list array) (depart : int) : int array =
  let dist = Array.make (Array.length g) (-1) in
  let file = Queue.create () in
  dist.(depart) <- 0;
  Queue.add depart file;
  while not (Queue.is_empty file) do
    let s = Queue.pop file in
    List.iter (fun v ->
      if dist.(v) = -1 then begin dist.(v) <- dist.(s) + 1; Queue.add v file end) g.(s)
  done;
  dist;;

distances g 0;;   (* -1 : sommet non accessible *)

f) Tri topologique

Dans un graphe orienté acyclique, un tri topologique est un ordre des sommets tel que, pour chaque arc , est avant . Par exemple, pour des tâches avec des dépendances ("il faut faire avant "), c'est un ordre dans lequel on peut faire les tâches.

On l'obtient avec un parcours en profondeur : un sommet est terminé quand tous ses successeurs le sont. L'ordre inverse des fins de traitement est un tri topologique.

Par exemple, "se lever, déjeuner, se doucher, s'habiller, partir" est un tri topologique de ces tâches ; "se lever, s'habiller, se doucher..." n'en est pas un.

OCaml

Loading editor...

let tri_topologique (g : int list array) : int list =
  let vu = Array.make (Array.length g) false in
  let ordre = ref [] in
  let rec visiter s =
    if not vu.(s) then begin
      vu.(s) <- true;
      List.iter visiter g.(s);
      ordre := s :: !ordre   (* s est terminé : on l'ajoute devant *)
    end
  in
  for s = 0 to Array.length g - 1 do visiter s done;
  !ordre;;

(* 0 : se lever, 1 : se doucher, 2 : s'habiller, 3 : déjeuner, 4 : partir *)
let taches = [| [1; 3]; [2]; [4]; [4]; [] |];;
afficher_graphe ~oriente:true taches;;
tri_topologique taches;;

III. Arbre couvrant de poids minimal

Soit un graphe non orienté, connexe, pondéré. Un arbre couvrant de est un sous-graphe qui contient tous les sommets, et qui est un arbre (connexe et sans cycle). On cherche un arbre couvrant de poids minimal : par exemple, pour relier des villes par un réseau le moins cher possible.

Algorithme de Kruskal

On trie les arêtes par poids croissant.
On part d'un graphe sans arête, et on considère les arêtes dans l'ordre : on ajoute une arête si elle ne crée pas de cycle, c'est-à-dire si ses deux extrémités ne sont pas déjà dans la même composante connexe.

C'est un algorithme glouton : à chaque étape, on prend la meilleure arête possible, sans revenir en arrière. Contrairement à beaucoup d'algorithmes gloutons, il donne toujours la solution optimale.

Par exemple, avec les arêtes triées par poids croissant : on garde (poids 1), (2), (3) ; on rejette (4), qui fermerait le cycle ; on garde (5). Tous les sommets sont alors reliés : l'arbre obtenu (en rouge) a un poids total de 11.

OCaml

Loading editor...

let kruskal (n : int) (aretes : (int * int * int) list) : (int * int * int) list =
  let triees = List.sort (fun (_, _, w1) (_, _, w2) -> compare w1 w2) aretes in
  (* composante.(s) : un numéro de la composante de s ; on fusionne en renumérotant *)
  let composante = Array.init n (fun s -> s) in
  List.filter (fun (a, b, _) ->
    let ca = composante.(a) and cb = composante.(b) in
    if ca = cb then false
    else begin
      Array.iteri (fun s c -> if c = cb then composante.(s) <- ca) composante;
      true
    end) triees;;

let aretes = [(0, 1, 4); (0, 2, 1); (1, 2, 2); (1, 3, 5); (2, 3, 8); (3, 4, 3); (2, 4, 9)];;
let arbre = kruskal 5 aretes;;
let g_pondere = Array.make 5 [];;
List.iter (fun (a, b, w) -> g_pondere.(a) <- (b, w) :: g_pondere.(a); g_pondere.(b) <- (a, w) :: g_pondere.(b)) aretes;;
afficher_graphe_pondere ~aretes_rouges:(List.map (fun (a, b, _) -> (a, b)) arbre) g_pondere;;

Avec la renumérotation ci-dessus, chaque fusion coûte ; le tri coûte . On peut faire mieux avec une file de priorité et une structure unir-trouver (voir le chapitre précédent).

IV. Couplages dans un graphe biparti

a) Définitions

Un graphe biparti a ses sommets séparés en deux ensembles et , et toutes ses arêtes relient un sommet de à un sommet de . Par exemple : des élèves () et des projets (), avec une arête si l'élève accepte le projet.

Définition : couplage

Un couplage est un ensemble d'arêtes qui n'ont deux à deux aucune extrémité commune. On cherche un couplage de cardinal maximum (le plus d'élèves possible ont un projet, chaque projet est pris au plus une fois).

b) Chemins augmentants

Définition : chemin augmentant

Soit un couplage. Un chemin augmentant est un chemin qui part d'un sommet libre (qui n'est extrémité d'aucune arête de ), arrive sur un autre sommet libre, et dont les arêtes sont alternativement hors de et dans .

En "inversant" les arêtes d'un chemin augmentant (celles hors de entrent dans , et inversement), on obtient un couplage avec une arête de plus.

Théorème (Berge)

Un couplage est de cardinal maximum si et seulement s'il n'existe pas de chemin augmentant.

Par exemple, avec le couplage (en rouge), le chemin est augmentant : et sont libres, et les arêtes sont alternativement hors de et dans . En l'inversant, on obtient un couplage à deux arêtes :

D'où l'algorithme : tant qu'on trouve un chemin augmentant (par un parcours en profondeur depuis un sommet libre de ), on augmente le couplage. Chaque recherche coûte , et il y a au plus augmentations : .

OCaml

Loading editor...

(* g.(a) : les sommets de B voisins de a (A et B sont numérotés à partir de 0) *)
let couplage_maximum (g : int list array) (nb : int) : int array =
  let partenaire_b = Array.make nb (-1) in   (* partenaire_b.(b) : le sommet de A couplé à b, ou -1 *)
  (* cherche un chemin augmentant depuis a ; vu : sommets de B déjà essayés *)
  let rec augmenter a vu =
    List.exists (fun b ->
      if vu.(b) then false
      else begin
        vu.(b) <- true;
        (* b est libre, ou son partenaire peut être recouplé ailleurs *)
        if partenaire_b.(b) = -1 || augmenter partenaire_b.(b) vu then begin
          partenaire_b.(b) <- a;
          true
        end else false
      end) g.(a)
  in
  Array.iteri (fun a _ -> ignore (augmenter a (Array.make nb false))) g;
  partenaire_b;;

(* 4 élèves (A), 4 projets (B) *)
let voeux = [| [0; 1]; [0]; [1; 2]; [2] |];;
couplage_maximum voeux 4;;

Le résultat se lit : le projet est attribué à l'élève partenaire_b.(b). Seuls 3 projets (0, 1 et 2) sont demandés, pour 4 élèves : au plus 3 élèves peuvent obtenir un projet, et c'est le cas ici.

Exercices

Exercice 1

Écrire une fonction chemin (g : int list array) (s : int) (t : int) : int list qui renvoie un plus court chemin (en nombre d'arêtes) de s à t, en utilisant peres_largeur.

OCaml

Loading editor...

let chemin (g : int list array) (s : int) (t : int) : int list =
  let pere = peres_largeur g s in
  let rec remonter v acc = if v = s then s :: acc else remonter pere.(v) (v :: acc) in
  if t <> s && pere.(t) = -1 then failwith "non accessible" else remonter t [];;

Exercice 2

Le tri topologique ci-dessus suppose le graphe acyclique. Comment détecter un cycle dans un graphe orienté avec un parcours en profondeur ?

On utilise trois états : non vu, en cours (le parcours depuis ce sommet n'est pas terminé), terminé. Il y a un cycle si et seulement si on rencontre un sommet en cours : on est revenu sur un sommet dont on est un descendant.

Exercice 3

Montrer qu'un arbre est toujours bicolorable.

On colorie chaque sommet selon la parité de sa profondeur (sa distance à une racine choisie). Deux sommets voisins sont père et fils : leurs profondeurs diffèrent de 1, donc leurs couleurs sont différentes.