Je pense intuitivement que si l'on utilise l'algorithme de Prim pour trouver un arbre de graphique minimum de graphique, peu importe que le nœud racine est cueilli - le MST résultant aura le même poids, peu importe. Est-ce correct?
3 Réponses :
c'est correct. Choisir un autre noeud de départ pourrait vous donner un arbre de survol différent, mais il aura toujours le même poids: le minimal possible.
Ceci est dû à Unicité des minima forts>. Suppose there are 2 "different" minimum weights W1 and W2
W1 is minimum
W2 is minimum
W1 != W2
This leads to contradiction because
if W1 != W2 then
W1 < W2 -> W1 is minima
or
W1 > W2 -> W2 is minima
Hence if W1 must equal W2.
Le poids / coût de l'arborescence sera le même quel que soit le noeud / sommet de départ; Cependant, la forme de l'arbre peut différer. Lorsque deux arêtes à la candidature ont le même poids qui finit par être le minimum actuel, le choix dépend de la mise en œuvre. Sauf s'il y a une véritable étape de cravate (qui est peu probable; dans des graphiques avec de nombreux bords de poids égal, cela pourrait prendre jusqu'à O (n), sans aucun gain réel), il est probablement «d'abord trouvé». Cela signifie que l'ordre dans lequel des nœuds / sommets sont ajoutés et visités des questions pour la déchirure et le nœud de départ / sommet peut donc affecter la forme.
Deuxièmement, cela pourrait affecter les performances, mais c'est difficile à contrôler. Alors que les opérations de tas deviennent plus chères de leur taille, vous voudrez ajouter le moins de bord possible, surtout tôt. On pourrait utiliser cela comme une justification pour donner la priorité à des sommets à faible degré. Cependant, il est peu probable que cela compte beaucoup au-delà du premier nœud / sommet.
TL; DR: Pour le coût total / poids: Non. Pour la forme: Oui, s'il existe plusieurs MST.