Coincé sur la résolution du problème Minimal Spanning Tree

Question

Je réduit mon problème à trouver l'arbre couvrant minimal dans le graphique. Mais je veux avoir une autre contrainte qui est que le degré total pour chaque shouldnt sommet dépasse un certain facteur constant . Comment puis-je modélise mon problème? Est MST le mauvais chemin? Connaissez-vous des algorithmes qui me aider?

Un autre problème: Mon graphique a double poids des arêtes est si il un moyen de compter le nombre de uniques MST? Les algorithmes sont là qui font cela?

Merci.

Edit: Par degré, je veux dire le nombre total d'arêtes reliant le sommet. En poids de bord en double, je veux dire que deux bords ont le même poids.

Answer 1

Cet article montre comment trouver, en temps polynomial, un arbre couvrant de degré maximal d + 1 qui est au moins aussi bon que any arbre couvrant de degré maximal d: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

// Modifier le lien d'origine est actuellement inactif, essayez http: // recherche. microsoft.com/pubs/80193/mbdst.pdf à la place.

Answer 2

Eh bien, il est facile de prouver qu'il ne peut être une solution: il suffit de faire votre entrée graphique un arbre qui a un sommet avec un degré supérieur à votre limite ..

Answer 3

Garey Johnson a eu ce problème réduit à hamilton :( Donc, celui-ci a aidé Approximation le premier. http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt Cependant, les modèles de travail meilleures sont appréciés ...

Comptage: http://mathworld.wolfram.com/SpanningTree.html . Selon cette étude, Mathematica a une fonction. Toutes les suggestions contenues dans celui-ci?