OCaml (option informatique) · Chapitre 14 · Exercice de TD
Sommet isolé
Graphes : modélisation et représentations · niveau 3 (difficile)
É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 0On 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.
Exercices semblables
- Matrice vers listes corrigé
- Listes vers matrice corrigé
- Voisins communs corrigé
- Graphe complet corrigé
- Chemins de longueur 2 corrigé