Bonjour à tous !
Voila... Je suis en L3 info, et nous avons eu des rattrapages en maths. Parmi ces rattrapages figurait un cour de maths sur les graphes. A un moment, le professeur nous a parlé d'un problème qui m'a fortement interessé:
Comment determiner le minimum des points a supprimer dans un graphe connexe pour que celui ne le soit plus ?
Il a ajouté que c'était un problème très complexe au sens algorithmique et que rien n'avait été trouvé qui soit rapide.
Avec mon culot d'éléphant, je me suis dit bon... On va trouver un algorithme alors... Et j'ai trouvé, preuve à l'appui.
Il y a donc maintenant deux possibilités:
1. - Je me suis trompé...
2. - Ce n'est pas un problème compliqué...
Pour le 1), j'ai vérifié et revérifié (je ne demande à personne de vérifier), ça fonctionne théoriquement.
Mais c'est le 2. qui m'amène a vous demander si vous connaitriez le meilleur algorithme qui fasse ceci en un temps optimal ?...
Merci à celui qui m'aidera parce que je ne trouve rien sur Internet...
-----