Adloun

Sommet isolé

Exercice · OCaml (option informatique), chapitre 14 — Graphes : modélisation et représentations

Énoncé

Écrire isole m : existe-t-il un sommet de degré ? Renvoyer son numéro en option.

Corrigé

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

On parcourt les sommets et l'on renvoie le premier de degré nul (Some i), ou None si chacun a au moins un voisin. Un sommet isolé est inatteignable : sa présence change la connexité du graphe.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.