Fest auf die Minimal Spanning Tree Problemlösung

Question

Ich habe mein Problem reduziert den minimalen Spanning-Tree in der Grafik zu finden. Aber ich möchte noch eine Einschränkung haben, das ist, dass die Gesamtgrad für jeden Vertex shouldnt einen bestimmten konstanten Faktor überschreiten . Wie kann ich mein Problem modellieren? Ist MST den falschen Weg? Kennen Sie Algorithmen, die mir helfen?

Ein weiteres Problem: Mein Graph hat doppelte Kantengewichte so ist es eine Möglichkeit, die Anzahl der eindeutigen MSTs zu zählen? Gibt es Algorithmen, die dies tun?

Danke.

Edit: Mit dem Abschluss habe ich die Gesamtzahl der Kanten bedeuten den Scheitelpunkt verbindet. Durch die doppelte Kantengewicht meine ich, dass zwei Kanten das gleiche Gewicht haben.

Answer 1

Dieses Papier zeigt, wie zu finden, in polynomialer Zeit, einen Spanning-Tree von maximalen Grad d + 1, die mindestens so gut wie ist eine beliebige Spanning Tree maximaler Grad d: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

// bearbeitet Der Original-Link ist derzeit inaktiv, versucht http: // Forschung. microsoft.com/pubs/80193/mbdst.pdf statt.

Answer 2

Nun, es ist leicht zu beweisen, dass es keine Lösung sein kann: einfach Ihre Eingabe grafische Darstellung eines Baumes machen, die einen Scheitelpunkt mit dem Grad hat höher als Ihr Limit ..

Answer 3

Garey Johnson hatte dieses Problem reduziert hamilton :( Also das half Annähern die ersten:. http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt Jedoch bessere Arbeitsmodelle geschätzt ...

Zählen: http://mathworld.wolfram.com/SpanningTree.html . Nach diesem hat Mathematica eine Funktion. Irgendwelche Vorschläge in diesem?