Quels bords ne figurent dans aucun MST

Question

Ceci est une question de devoirs. Je ne veux pas de solution - j'offre la solution à laquelle je pensais et je souhaite savoir si elle est bonne ou pourquoi elle est défectueuse. Ma motivation est de trouver quelles arêtes d'un graphe non pondéré, non orienté ne font partie d'aucun MST. Ce problème n'a de sens que lorsque plusieurs arêtes ont les mêmes valeurs, sinon le MST est unique.

Mon idée vient de l'algorithme de Prim avec un léger changement - au lieu d'ajouter le bord minimum de S à T sur toutes les étapes (où S et T étant les deux ensembles de vertex) - regardez plutôt le bord minimum et plus d'arêtes de la même valeur allant de S au sommet que le bord minimum va à. En faisant cela, (donc je suppose) nous recevrons un graphique contenant tous les bords qui apparaissent dans n'importe quel MST. Si cela est juste, je peux simplement XOR la ​​liste des bords avec la liste des arêtes de graphique d'origine pour trouver quels bords ne sont pas dans n'importe quel MST.

Merci d'avance.

Answer 1

Ajoutez-vous tous les bords que vous trouvez (= ceux qui ont un poids égal)? Si oui, vous perdrez des arêtes:

Considérons un pentagone avec des coûts de bordure égaux. Vous commencez avec 1 noeud et ajoutez les 2 bords aux 2 nœuds adjacents. Dans votre prochaine étape, vous ajouteriez les 2 bords allant de ces 2 nœuds adjacents aux 2 nœuds déconnectés et vous auriez terminé. Cependant, tous les bords ont le même coût et ils sont tous valides dans le MST. Le bord entre les 2 derniers nœuds n'est pas inclus par votre algorithme mais pourrait faire partie du MST.

C'est encore pire. Supposons que le dernier tronçon ait un coût inférieur. Votre algorithme ne l'inclut toujours pas, mais il est présent dans tous les MST. Vous ajoutez plusieurs arêtes par étape pour tenir compte de toutes les possibilités, mais l'ajout de ces arêtes change les étapes suivantes.