Discussion :

[dvp_zero]

Bonjour à tous,

j'aimerai savoir pour un graphe complet possédant 5 noeuds, quel est le nombre maximum de minimum spanning tree qu'il possède?

Je dirais 5 puisqu'il possède 5 noeuds. Et donc si on fait démarrer l'algorithme sur chacun des noeuds successivement, on obtient les 5 noeuds.

Au départ d'un même noeud on possède toujours le même MST je suppose?

Merci beaucoup

[Aleph69]

Bonjour,

d'après la formule de Cayley, il doit y avoir 5^3=125 spanning trees.

[dvp_zero]

Merci pour l'information.

Mais sur les 125 spanning tree possible combien sont minimum?

[Aleph69]

Ca dépend du poids de tes arêtes. Si toutes tes arêtes ont le même poids, alors tous les spanning trees sont minimaux.

[dvp_zero]

Dans mon cas, les arrêtes possèdent des poids différents.

J'aurais dit 5 arbres recouvrants minimums puisque, aussi bien l'algorithme de Prim que celui de Kruskal, l'élément déterminant est le noeud de départ.

Ensuite, la procédure reste identique. Je veux dire par là que, si on exécute deux fois l'algorithme avec le même noeud de départ, on obtiendra le même minimum spaning tree non?

C'est mon intuition mais j'aimerai avoir confirmation.

[Aleph69]

Si on suit ton raisonnement, un graphe à n noeuds possède n arbres couvrants minimaux dès lors que l'algorithme de Prim ou Kruskal trouve un tel arbre pour chaque noeud de départ... Mais, ce n'est pas parce que tu trouves un arbre couvrant minimal à partir d'un noeud que c'est le seul, quand bien même ton algorithme serait déterministe et trouverait toujours le même arbre pour un noeud de départ donné. La formule de Cayley te fournit plein de contre-exemples.

[dvp_zero]

Merci pour ton explication.


En fait je posais cette question car, j'ai un graphe possédant 5 noeuds et j'aimerais créer une population initiale d'arbre recouvrant (pour l'utiliser dans les algorithmes évolutionnaires).

Je me demande alors si je peux utiliser soit l'algorithme de Prim ou celui de Kruskal pour constituer ma population de minimum spanning tree.
Si je veux une population de taille 10, j'ai peur qu'en utiliser Prim ou Kruskal, je me retrouve avec des individus identiques (comme je n'ai que 5 noeuds et une population de 10 individus).

Est-ce que l'algorithme de Prim/Kruskal permet de "viser" un maximum de MST? Ou alors sont-ils déterministes et dans ce cas là j'obtiendrais 5 MST différents au plus (même s'il en existe plus)?

Merci