Forum de mathématiques - Bibm@th.net
Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
Discussion fermée
#1 16-04-2008 15:53:03
- radia
- Invité
un algo s'exécutant en temps polinomial [Résolu]
Bonjour,
J'ai un problème et j'aimerai bien être aider
Si j'ai soit B le problème de décision qui consiste à déterminer si un graphe connexe non-orienté et
valué G posséde un arbre minimal de recouvrement de valeur plus petite ou égale a une constante
donnée k. Comment montrer que B s'exécute en temps polinomial?
merci d'avance!
#2 17-04-2008 00:31:50
- Barbichu
- Membre actif
- Inscription : 15-12-2007
- Messages : 405
Re : un algo s'exécutant en temps polinomial [Résolu]
Hello,
pour cela, on dispose de l'algorithme de Kruskal qui est polynomial (cf http://en.wikipedia.org/wiki/Kruskal%27s_algorithm ou en français : http://fr.wikipedia.org/wiki/Algorithme_de_Kruskal). Il suffit ensuite de comparer le poids de l'arbre couvrant minimum et k.
++
Barbichu
Hors ligne
Pages : 1
Discussion fermée