Graphe complet

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

On vérifie qu'aucune paire (i, j) distincte n'est dépourvue d'arête. Un graphe complet à n sommets a $\frac{n(n-1)}{2}$ arêtes ; sa matrice n'a que des true hors diagonale.