Poster un commentaire à la suite de l’article...

dimanche 28 mars 2021
par  Alain BUSSER , Sébastien HOARAU

Capes NSI 2021 épreuve 1

Corrigé de ce sujet où la part accordée aux graphes est croissante.

En réponse à...

Logo de Louis Leskow
vendredi 4 février 2022 à 10h26 - par  Louis Leskow

La réponse à la question 44 ne me semble pas correcte.
Si on prend un graphe composé d’un carré, avec pour chacun de ces 4 sommets un sommet en plus qui est uniquement relié à ce sommet.
([ [4], [5], [6], [7], [0, 5, 7], [1, 4, 6], [2, 5, 7], [3, 4, 6]])

L’algorithme passe à côté de la composante connexe 4, 5, 6, 7 (le carré).

Ça ne me paraît pas sauvable de façon simple, si on enlève le sommet 3, ou si on lui ajoute un voisin uniquement relié à lui même, les comportements seront très différents.

modération a priori

Ce forum est modéré a priori : votre contribution n’apparaîtra qu’après avoir été validée par un administrateur du site.

Qui êtes-vous ?
Votre message

Pour créer des paragraphes, laissez simplement des lignes vides.