Preso em resolver o problema Minimal Spanning Tree

Question

Eu reduzi o meu problema de encontrar a árvore de extensão mínima no gráfico. Mas eu quero ter mais uma restrição que é a o grau total para cada vértice não deve exceder um determinado fator constante . Como faço para modelar o meu problema? MST é o caminho errado? Você conhece algum algoritmos que vão me ajudar?

Mais um problema: Meu gráfico tem pesos das arestas duplicadas assim há uma maneira de contar o número de MSTs únicas? Existem algoritmos que fazem isso?

Obrigado.

Editar: Por grau, quer dizer o número total de arestas que ligam o vértice. Por peso borda duplicado quero dizer que duas arestas têm o mesmo peso.

Answer 1

Este artigo mostra como encontrar, em tempo polinomial, uma árvore geradora de grau máximo d + 1 que é pelo menos tão boa como qualquer árvore geradora de grau máximo d: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

// editar o link original é atualmente inativa, tente http: // pesquisa. microsoft.com/pubs/80193/mbdst.pdf .

Answer 2

Bem, é fácil provar que não pode haver uma solução: basta fazer o seu gráfico de entrada uma árvore que tem um vértice com grau mais elevado do que o seu limite ..

Answer 3

Garey Johnson teve este problema reduzir a hamilton :( Então este ajudou a aproximar a primeira:. http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt No entanto, os modelos de melhor trabalho são apreciados ...

Counting: http://mathworld.wolfram.com/SpanningTree.html . De acordo com este, mathematica tem uma função. Todas as sugestões em um presente?