Pegado a la solución del problema del árbol de expansión mínimo

Question

He reducido mi problema de encontrar el árbol de expansión mínimo en el gráfico. Pero yo quiero tener una restricción mayor que la que es el grado total para cada vértice shouldnt superar un determinado factor constante . ¿Cómo puedo modelar mi problema? MST es el camino equivocado? ¿Conoce algún algoritmos que me ayude?

Uno de los problemas más: Mi gráfico tiene pesos de las aristas duplicados Entonces, ¿hay una manera de contar el número de MSTs únicas? ¿Hay algoritmos que hacen esto?

Gracias.

Edit: Por grado, es decir el número total de aristas que conectan el vértice. Por peso borde duplicado quiero decir que dos bordes tienen el mismo peso.

Answer 1

Este documento muestra cómo encontrar, en tiempo polinómico, un árbol de expansión de grado máximo d + 1 que es al menos tan bueno como cualquier árbol de expansión de grado máximo d: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

// Editar El enlace está inactivo, prueba a http: // investigación. microsoft.com/pubs/80193/mbdst.pdf lugar.

Answer 2

Bueno, es fácil demostrar que no puede haber una solución: basta con hacer su entrada gráfico de un árbol que tiene un vértice con grado superior a su límite ..

Answer 3

Garey Johnson tuvo este problema a reducir a Hamilton :( Así que éste ayudó a la aproximación de la primera de ellas:. http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt Sin embargo, los modelos de trabajo mejores son apreciados ...

Recuento: http://mathworld.wolfram.com/SpanningTree.html . De acuerdo con esto, Mathematica tiene una función. Cualquier sugerencia en esta?