c++.de :: Graphen...

Grohool Mitglied 04:34:09 06.07.2009 Titel:

Ich hab einen gewichteten Graphen G und eine Funktion g die jedem Knoten im Graphen eine natürliche Zahl zuordnet.
Jetzt such ich einen Algorithmus der mir einen aufspannenden Baum B ausgibt dessen Summe der Längen der (kürzesten) Wege von einem bestimmten Knoten zu jedem anderen möglichst minimal ist... ausserdem darf kein Knoten K im Baum mehr als g(K) Söhne haben.

Kennt jemand so einen Algorithmus oder muss ich mir selbst irgendwas ausdenken?

Christoph Moderator 10:29:38 06.07.2009 Titel:

Das wird schwierig, schätze ich, denn mit dem von dir geforderten Algorithmus könntest du das NP-vollständige Problem "hat der Graph einen hamiltonschen Pfad?" lösen:

1. Nimm einen beliebigen Graphen G, setze alle Kantengewichte und alle g(v) auf 1 für alle Knoten v.
2. Wende deinen Algorithmus an.
3a. Liefert er einen Spannbaum, ist dieser Spannbaum ein hamiltonscher Pfad, weil jeder Knoten maximal 1 Nachfolger hat, der Baum also zum Pfad entartet ist.
3b. Liefert er keinen Spannbaum, gibt es keinen hamiltonschen Pfad.

Jester Moderator 16:09:40 06.07.2009 Titel:

Zumindest für bounded degree spanning tree (also gegeben einen Graphen, finde einen spannenden Baum mit kleinstem maximalen Knotengrad) gibt es eine Approximation, die höchstens um 1 schlechter ist als die optimale Lösung. Das ist eine Arbeit von Fürer. Damit sollte sich das eigentlich finden lassen. Vielleicht kannst Du einige Ideen davon übernehmen?

Grohool Mitglied 16:41:19 06.07.2009 Titel:

Ich guck mal ob ich dazu was finde. Aber das bringt mir eigentlich nichts. Intuitiv würde ich sagen, dass es besser ist, wenn die Knoten einen möglichst hohen Knotengrad haben.

Jester Moderator 17:00:26 06.07.2009 Titel:

Groß... aber begrenzt durch g(k). Das Problem ist, dass Du für jeden Knoten eine andere Grenze hast. Das kannst Du aber vermutlich folgendermaßen loswerden. Sei g_max = max_k g(k) der größte dieser Werte. Nun hänge an jeden Knoten k noch g_max-g(k) neue Blätter dran. Da die auch angebunden werden müssen bei einem Spannbaum bleiben Dir nachdem die neuen Blätter angebunden sind noch genau g(k) erlaubte Söhne übrig. Das heißt, Du suchst nun nach einem Spannbaum mit Maximalgrad g_max. Das ist also schon ein verwandtes Problem. Die Gewichte hast Du so allerdings noch nicht dabei.