Bibm@th

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).

#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

Pied de page des forums