Graphes : modélisation et représentations

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>14.1 Introduction et motivation

Réseaux routiers, liens entre pages web, amis d'un réseau social, dépendances entre tâches : une foule de problèmes se modélisent par un graphe — des sommets reliés par des arêtes. Avant d'explorer un graphe (parcours, plus courts chemins, aux chapitres suivants), il faut savoir le représenter en machine. Ce chapitre installe le vocabulaire et les deux représentations fondamentales en OCaml : la matrice d'adjacence et les listes d'adjacence, leurs forces respectives, et comment passer de l'une à l'autre.

On y mobilise tout l'arsenal des chapitres précédents : tableaux (chapitre 5) pour la matrice, listes (chapitre 2) pour les voisinages, et le raisonnement de complexité pour choisir la bonne structure selon la densité du graphe.

14.2 Vocabulaire

14.3 La matrice d'adjacence

On code le graphe par une matrice carrée n$\times$n de booléens : m.(i).(j) vaut true s'il y a une arête de i vers j.

let matrice_vide n = Array.make_matrix n n false

let ajoute_arete m i j =          (* graphe NON orienté : symétrique *)
  m.(i).(j) <- true;
  m.(j).(i) <- true

Pour un graphe orienté, on ne pose que m.(i).(j) <- true. Pour un graphe pondéré, on remplace les booléens par des entiers (le poids, une valeur convenue signalant l'absence d'arête).

14.4 Les listes d'adjacence

On code le graphe par un tableau de listes : adj.(i) est la liste des voisins de i.

let listes_vides n = Array.make n []

let ajoute_arc adj i j = adj.(i) <- j :: adj.(i)    (* orienté : i -> j *)

let ajoute_arete adj i j =                          (* non orienté *)
  adj.(i) <- j :: adj.(i);
  adj.(j) <- i :: adj.(j)

14.5 Degrés et conversions

(* matrice *)
let degre_mat m i =
  let d = ref 0 in
  for j = 0 to Array.length m - 1 do
    if m.(i).(j) then d := !d + 1
  done;
  !d

(* listes : c'est la longueur de la liste des voisins *)
let degre_adj adj i = List.length adj.(i)

On passe d'une représentation à l'autre par un double parcours :

let vers_listes m =
  let n = Array.length m in
  let adj = Array.make n [] in
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do
      if m.(i).(j) then adj.(i) <- j :: adj.(i)
    done
  done;
  adj

let vers_matrice adj =
  let n = Array.length adj in
  let m = Array.make_matrix n n false in
  for i = 0 to n - 1 do
    List.iter (fun j -> m.(i).(j) <- true) adj.(i)
  done;
  m

(L'ordre des voisins dans vers_listes est décroissant, ce qui est sans importance.)

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>14.6 Exercices résolus

Niveau $\star$ (application directe du cours)

let g = matrice_vide 5
let () =
  ajoute_arete g 0 1; ajoute_arete g 0 2; ajoute_arete g 1 2;
  ajoute_arete g 2 3; ajoute_arete g 3 4
(* g.(0).(3) vaut false : 0 et 3 ne sont pas voisins *)

let degre_mat m i =
  let d = ref 0 in
  for j = 0 to Array.length m - 1 do
    if m.(i).(j) then d := !d + 1
  done;
  !d

let g = listes_vides 5
let () =
  ajoute_arete g 0 1; ajoute_arete g 0 2; ajoute_arete g 1 2;
  ajoute_arete g 2 3; ajoute_arete g 3 4
(* degre_adj g 2 = List.length g.(2) = 3 *)

Niveau $\star \star$ (raisonnement intermédiaire)

let nb_aretes m =
  let n = Array.length m in
  let c = ref 0 in
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do
      if m.(i).(j) then c := !c + 1
    done
  done;
  !c / 2

let vers_listes m =
  let n = Array.length m in
  let adj = Array.make n [] in
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do
      if m.(i).(j) then adj.(i) <- j :: adj.(i)
    done
  done;
  adj

let vers_matrice adj =
  let n = Array.length adj in
  let m = Array.make_matrix n n false in
  for i = 0 to n - 1 do
    List.iter (fun j -> m.(i).(j) <- true) adj.(i)
  done;
  m

Niveau $\star \star \star$ (approfondissement)

let voisins_communs m i j =
  let n = Array.length m in
  let c = ref 0 in
  for k = 0 to n - 1 do
    if m.(i).(k) && m.(j).(k) then c := !c + 1
  done;
  !c

let est_complet m =
  let n = Array.length m in
  let ok = ref true in
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do
      if i <> j && not m.(i).(j) then ok := false
    done
  done;
  !ok

let isole m =
  let n = Array.length m in
  let rec cherche i =
    if i = n then None
    else if degre_mat m i = 0 then Some i
    else cherche (i + 1)
  in
  cherche 0

let chemins_deux m =
  let n = Array.length m in
  let r = Array.make_matrix n n 0 in
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do
      let c = ref 0 in
      for k = 0 to n - 1 do
        if m.(i).(k) && m.(k).(j) then c := !c + 1
      done;
      r.(i).(j) <- !c
    done
  done;
  r

14.7 Exercices d'entraînement

Légende : $\star$ application directe, $\star \star$ raisonnement intermédiaire, $\star \star \star$ approfondissement ; $⧫$ signale un classique incontournable. La numérotation prolonge celle des dix exercices résolus.

Thème A — Construction et degrés.

• [11.] $\star$ Écrire degres_tous m : le tableau des degrés de tous les sommets.
• [12.] $\star \star$ $⧫$ Vérifier sur un graphe que la somme des degrés est paire et vaut 2 * nb_aretes m.
• [13.] $\star \star$ Écrire les versions orientées : degre_sortant et degre_entrant d'un sommet (matrice).

Thème B — Propriétés.

• [14.] $\star \star$ est_symetrique m : la matrice représente-t-elle un graphe non orienté ?
• [15.] $\star \star \star$ a_boucle m : existe-t-il une arête d'un sommet vers lui-même (m.(i).(i)) ?
• [16.] $\star \star \star$ $⧫$ degre_max adj : le degré maximal (listes d'adjacence).

Thème C — Représentations pondérées.

• [17.] $\star \star$ Représenter un graphe pondéré par int array array (poids, et une valeur convenue pour l'absence d'arête) ; écrire poids m i j.
• [18.] $\star \star \star$ Représenter un graphe pondéré par listes : (int * int) list array (voisin, poids) ; écrire voisins adj i.
• [19.] $\star \star$ matrice_grille p q : la matrice d'adjacence d'une grille $p\times q$ (chaque case reliée à ses voisines orthogonales).

Thème D — Chemins par la matrice.

• [20.] $\star \star \star$ Écrire produit a b (produit de deux matrices d'entiers) et en déduire chemins_deux par produit m m.
• [21.] $\star \star \star$ chemins_p m p : nombre de chemins de longueur p (élever m à la puissance p).
• [22.] $\star \star$ $⧫$ Discuter : pour un réseau social de $10^7$ membres ayant chacun $\sim 200$ amis, quelle représentation choisir et pourquoi ?