Introduction et graphes de tests

Dans tout ce sujet de TP, on considère des graphes sur \(\{0,1,\dots,n-1\}\) donnés par leurs listes d'adjacence (voir le chapitre sur les graphes). Un graphe non orienté est représenté par son graphe orienté symétrique : chaque arête \(x - y\) apparaît dans la liste de \(x\) et dans celle de \(y\).

Ainsi, on a :

type graphe = int list array

Question 1. Écrire des fonctions

val cycle : int -> graphe
val complet : int -> graphe

qui renvoient les graphes non orientés \(C_n\) (pour \(n \ge 3\)) et \(K_n\).

Corrigé

let cycle n =
    (* on suppose n >= 3 *)
    let v = Array.make n [] in
    for i = 0 to n-1 do
        v.(i) <- [ (i+1) mod n;
            (i+n-1) mod n ]
    done;
    v

let complet n =
    let v = Array.make n [] in
    for i = 0 to n-1 do
        v.(i) <- 
            List.init n Fun.id
            |> List.filter ((<>)i)
    done;
    v

Question 2. Écrire des fonctions

val vers_bin : int -> int -> bool list
val depuis_bin : bool list -> int
val compte_diff : 'a list -> 'a list -> int
val hypercube : int -> graphe

telles que

• vers_bin n p renvoie la représentation binaire de p sur n bits sous forme de liste avec en tête le bit de poids le plus faible (Exemple : vers_bin 4 14 -> [false;true;true;true])
• depuis_bin l prend une telle représentation et renvoie l'entier correspondant
• compte_diff l1 l2 renvoie le nombre d'éléments différents au même rang dans deux listes de même longueur
• hypercube n renvoie \(H_n\).

Corrigé

let rec vers_bin n p =
    if n = 0
    then []
    else (p mod 2 = 1) 
        :: vers_bin (n-1) (p / 2)

let rec depuis_bin l =
    match l with
    | [] -> 0
    | t :: q ->
        2 * depuis_bin q
        + (if t then 1 else 0)

let rec pow2 n =
    if n = 0 then 1 else 2 * pow2 (n-1)

let compte_diff l1 l2 =
    List.combine l1 l2
    |> List.filter
        (fun (a,b) -> a <> b)
    |> List.length

let hypercube n =
    let p2 = pow2 n in
    let v = Array.make p2 [] in
    for i = 0 to p2 - 1 do
        for j = i+1 to p2 - 1 do
            let bi, bj = 
                vers_bin n i, vers_bin n j in
            if compte_diff bi bj = 1
            then begin
                v.(i) <- j :: v.(i);
                v.(j) <- i :: v.(j)
            end
        done
    done;
    v

Question 3. Écrire une fonction

val aleatoire : int -> int -> graphe

telle que aleatoire n p crée un graphe non orienté aléatoire à n sommets et p arêtes (avec \(p \le \frac{n(n-1)}{2}\)), où l'ensemble des p arêtes est choisi uniformément parmi les ensembles de p arêtes possibles.

Corrigé

On tire une arête uniformément parmi les \(\frac{n(n-1)}{2}\) arêtes possibles, et on recommence si elle est déjà présente. Pour tirer b uniforme et distinct de a, on tire c dans \(\range{0}{n-2}\) et on décale de 1 les valeurs \(\ge a\).

let aleatoire n p =
    (* on suppose p <= n(n-1)/2 *)
    assert (2 * p <= n * (n-1));
    let v = Array.make n [] in
    let nb = ref 0 in
    while !nb < p do
        (* a et b uniformes et distincts *)
        let a = Random.int n in
        let b =
            let c = Random.int (n-1) in
            if c >= a then c+1 else c in
        (* on recommence si l'arête existe déjà *)
        if not (List.mem b v.(a))
        then begin
            v.(a) <- b :: v.(a);
            v.(b) <- a :: v.(b);
            incr nb
        end
    done;
    v

Quand p est proche de \(\frac{n(n-1)}{2}\), les tirages rejetés deviennent nombreux, mais cela reste raisonnable pour les tailles de ce TP.

Principe du parcours récursif

Pour explorer un graphe, on va reprendre le principe du parcours récursif vu pour les arbres.

Parcours(x) :

• Si x n'a pas déjà été traité
  • On traite x (appel d'une fonction sur x, changement de valeurs…)
  • Pour chaque voisin y de x
    • On appelle Parcours(y)

Ainsi, la fonction parcours devra prendre en entrée :

• le graphe sous forme de listes d'adjacence ;
• le sommet de départ x ;
• une structure permettant de gérer le parcours pour s'assurer de ne pas traiter deux fois un sommet (un visites : bool array suffit) ou pour rajouter des informations supplémentaires.

Question 4. Écrire une fonction

val parcours : graphe -> bool array -> int -> unit

telle que parcours g visites x effectue ce parcours récursif en se contentant de placer true dans visites.(x) pour le traiter.

Corrigé

let rec parcours g visites x =
    if not visites.(x)
    then begin
        visites.(x) <- true;
        List.iter (parcours g visites) g.(x)
    end

Question 5. En déduire une fonction

val taille_composante : graphe -> int -> int

telle que taille_composante g x renvoie le nombre de sommets de la composante connexe de x dans un graphe non orienté.

Corrigé

let taille_composante g x =
    let n = Array.length g in
    let visites = Array.make n false in
    parcours g visites x;
    Array.map 
        (fun x -> if x then 1 else 0) 
        visites
        |> Array.fold_left (+) 0

Question 6. En déduire une fonction

val connexe : graphe -> bool

qui indique si un graphe non orienté (ayant au moins un sommet) est connexe.

Corrigé

let connexe g =
    taille_composante g 0 
        = Array.length g

Question 7. On va considérer ici \(n\) sommets et, pour chaque \(p\) entre \(0\) et \(p_{max}\), on va compter la proportion \(C_p\) de graphes non orientés connexes obtenus pour \(100\) générations de graphes aléatoires à \(p\) arêtes.

Écrire la fonction

val proportions : int -> int -> float list

telle que proportions n pmax renvoie la liste des \(C_p\) pour \(p\) croissant.

Tracer cela pour différentes valeurs, avec matplotlib par exemple.

Corrigé

On s'arrête à \(\frac{n(n-1)}{2}\) arêtes si \(p_{max}\) est plus grand.

let proportions n pmax =
    List.init
        (min pmax (n * (n-1) / 2) + 1)
        (fun p ->
            let r = ref 0 in
            for i = 1 to 100 do
                if connexe (aleatoire n p)
                then incr r
            done;
            float_of_int !r /. 100.)

Extraction des composantes connexes

On peut adapter le parcours précédent pour obtenir l'ensemble des composantes connexes d'un graphe non orienté ainsi :

• On commence à \(k = 0\)
• Tant que \(G\) a un sommet non visité \(x\) :
  • On incrémente \(k\)
  • On lance un parcours depuis \(x\)
  • On attribue à chacun des sommets visités lors de ce parcours la composante connexe d'indice \(k\)

On peut se contenter d'un unique tableau pour indiquer la composante connexe d'un sommet tout en permettant de définir la notion de visite : il suffit de mettre 0 à tous en numéro de composante puis de lancer un parcours tant qu'il y a un sommet associé à 0.

Question 8. Écrire une fonction

val composantes : graphe -> int list list

qui renvoie la liste des composantes connexes écrites sous forme de listes d'entiers (l'ordre importe peu).

Note comme souvent dans ces questions, il va falloir refaire un parcours adapté en fonction auxiliaire.

Corrigé

let indices v x =
    let ind = ref [] in
    for i = 0 to Array.length v - 1 do
        if v.(i) = x
        then ind := i :: !ind
    done;
    !ind

let composantes g =
    let n = Array.length g in
    let k = ref 0 in
    let comp = Array.make n 0 in 
    let rec dfs x =
        if comp.(x) = 0
        then begin
            comp.(x) <- !k;
            List.iter dfs g.(x)
        end
    in
    for x = 0 to n-1 do
        if comp.(x) = 0
        then begin
            incr k;
            dfs x
        end
    done;
    List.init !k
        (fun k -> indices comp (k+1))

Chemins

Dans un parcours, on dit que le sommet \(x\) qui effectue un appel récursif sur un de ses voisins \(y\) est le père de \(y\).

Les sommets pour lesquels cela ne se produit pas n'ont pas de père. Parmi ceux-ci le cas du sommet de départ est à part.

Pour obtenir le chemin depuis un sommet de départ vers un sommet \(z\) de père défini, il suffit de remonter de père en père jusqu'à retomber sur le sommet de départ.

Question 9. Écrire une fonction

val chemin : int option array -> int -> int -> int list option

telle que chemin peres x y renvoie un chemin de x à y s'il en existe un, donné par le tableau peres des pères.

Corrigé

let chemin peres x y =
    let rec aux pre y =
        match peres.(y) with
        | None -> None
        | Some z ->
            if z = x 
            then Some (z :: pre)
            else aux (z :: pre) z
    in aux [y] y

Question 10. Modifier la fonction de parcours pour obtenir

val parcours_ex : graphe -> bool array -> int option array -> int -> unit

telle que parcours_ex g visites peres x effectue un parcours récursif en remplissant le tableau des pères.

Corrigé

let rec parcours_ex g visites peres x =
    if not visites.(x)
    then begin
        visites.(x) <- true;
        List.iter (fun y ->
            if peres.(y) = None
            then peres.(y) <- Some x;
            parcours_ex g visites peres y) g.(x)
    end

(* Qu'on peut utiliser ainsi par exemple : *)
let test_parcours_ex =
    let n = 8 in
    let g = hypercube 3 in
    let peres = Array.make n None in
    let visites = Array.make n false in
    parcours_ex g visites peres 0;
    List.map (chemin peres 0) (List.init n Fun.id)

Le sommet de départ \(x\) n'a pas de père au début du parcours. S'il possède un prédécesseur \(z\) accessible depuis \(x\), la ligne peres.(y) <- Some x lui donne le père \(z\) quand on examine l'arête \(z \rightarrow x\) : chemin peres x x renvoie alors un cycle passant par \(x\). C'est ce qu'on exploite à la question suivante.

Question 11. À l'aide de la fonction précédente, écrire une fonction

val cyclique_oriente : graphe -> bool

qui indique si un graphe orienté est cyclique.

Écrire une version non orientée en faisant attention aux possibles pièges dans ce cas.

Corrigé

(* Une version simple revient à lancer un parcours depuis 
   chaque sommet et à étudier l'existence d'un chemin depuis 
   ce sommet vers lui même.

   On verra bientôt une version directe depuis le parcours.
*)
let cyclique_oriente g =
    let n = Array.length g in
    let cyclique = ref false in
    for x = 0 to n-1 do
        let peres = Array.make n None in
        let visites = Array.make n false in
        parcours_ex g visites peres x;
        match chemin peres x x with
        | None -> ()
        | Some p -> cyclique := true
    done;
    !cyclique

Dans le cas non orienté, la fonction précédente répond toujours true dès qu'il y a une arête, puisque \(x \rightarrow y \rightarrow x\) est un cycle du graphe orienté symétrique. Il faut ignorer l'arête qui ramène au père :

(* Dans un graphe non orienté, chaque arête x - y donne x -> y et y -> x :
   le chemin x -> y -> x n'est pas un cycle. On détecte un cycle quand on
   rencontre un sommet déjà visité qui n'est pas le père du sommet courant.
   On suppose le graphe sans boucle ni arête multiple. *)
let cyclique_non_oriente g =
    let n = Array.length g in
    let visites = Array.make n false in
    let cyclique = ref false in
    let rec dfs pere x =
        visites.(x) <- true;
        List.iter (fun y ->
            if not visites.(y)
            then dfs x y
            else if y <> pere
            then cyclique := true) g.(x)
    in
    for x = 0 to n-1 do
        if not visites.(x)
        then dfs (-1) x
    done;
    !cyclique

Autonomie : Kosaraju

Question 12. Documentez-vous et implémentez l'algorithme de Kosaraju pour obtenir les composantes fortement connexes d'un graphe orienté.

Corrigé

L'algorithme est présenté dans le chapitre sur les graphes avancés et mis en œuvre dans le TP Kosaraju et 2-SAT.