Bloccato nel risolvere il problema del Minimal Spanning Tree

Question

Ho ridotto il mio problema alla ricerca dell'albero di copertura minimo nel grafico.Ma voglio avere un ulteriore vincolo: quello il grado totale per ciascun vertice non dovrebbe superare un certo fattore costante.Come modellizzo il mio problema?MST è la strada sbagliata?Conosci qualche algoritmo che mi possa aiutare?

Un altro problema:Il mio grafico ha pesi dei bordi duplicati, quindi esiste un modo per contare il numero di MST univoci?Esistono algoritmi che fanno questo?

Grazie.

Modificare:Per grado intendo il numero totale di spigoli che collegano il vertice.Per peso del bordo duplicato intendo che due bordi hanno lo stesso peso.

Answer 1

Questo documento mostra come trovare, in tempo polinomiale, un albero di copertura di massimo grado d + 1, che è almeno altrettanto buono come qualsiasi spanning tree di massimo grado d: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

// Modifica il link originale è attualmente inattiva, prova a http: // ricerca. microsoft.com/pubs/80193/mbdst.pdf .

Answer 2

Bene, è facile dimostrare che potrebbe non esserci una soluzione:rendi semplicemente il tuo grafico di input un albero che ha un vertice con un grado superiore al tuo limite.

Answer 3

Garey Johnson ha avuto questo problema ridurre al hamilton :( Quindi questo ci ha aiutato approssimare la prima:. http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt Tuttavia, i modelli di lavoro migliori sono apprezzati ...

Counting: http://mathworld.wolfram.com/SpanningTree.html . In base a questo, Mathematica ha una funzione. Ogni suggerimento in questo?