Discussion :

[yaris20]

Bonjour.
L'algorithme de Prim permet-il de trouver tout arbre couvrant minimal d'un graphe. Si oui, comment le prouver ? Sinon, quelqu'un a t-il un contre-exemple ?

Merci.

[benDelphic]

mais bien sur voyons ... les deux algorithmes convergent ( Prim et Kruskal ) .
je me souviens avoir eu cette question dans un examen ... la démonstration ( très classique ) n'est pas vraiment très difficile ( voir le principe d'optimisation de bellman ).

[yaris20]

mais bien sur voyons ... les deux algorithmes convergent ( Prim et Kruskal ) .
je me souviens avoir eu cette question dans un examen ... la démonstration ( très classique ) n'est pas vraiment très difficile ( voir le principe d'optimisation de bellman ).

Serait-il possibe d'avoir plus de détails ?

[benDelphic]

la démonstration est la même pour les deux algorithmes car ces deux là ne différent que dans le moyen d'empêcher la création d'un cycle . Kruskal détermine si l 'arête en cours crée un cycle ... Prim , en faisant une contraction des sommets élimine le voisinage du sommet en cours .
Donc le résultat obtenu est nécessairement une arborescence puisque c'est un graphe connexe sans cycles ...
pour ce qui est de l'optimalité ... c'est un cas très spécial d'heuristique qui pour ce problème donne toujours une solution optimale ... car si on prend les arêtes de moindre cout tout en maintenant une propriété P n'est pas forcément une bonne solution ( essayer avec le problème d'affectation ).