Застрял в решении проблемы минимального связующего дерева

Question

Я свел свою проблему к поиску минимального остовного дерева на графике. Но я хочу иметь еще одно ограничение: общая степень для каждой вершины не должна превышать некоторый постоянный коэффициент . Как мне смоделировать мою проблему? MST - неправильный путь? Вы знаете какие-нибудь алгоритмы, которые мне помогут?

Еще одна проблема: у моего графа есть дублирующиеся веса ребер, так есть ли способ подсчитать количество уникальных MST? Есть ли алгоритмы, которые делают это?

Спасибо.

Редактировать: Под градусом я подразумеваю общее количество ребер, соединяющих вершину. Под двойным весом ребра я подразумеваю, что два ребра имеют одинаковый вес.

Answer 1

У Гэри Джонсона эта проблема сводилась к Гамильтону :( Так что этот помог. Приближенный к первому: http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt Тем не менее, лучшие рабочие модели приветствуются ...

Подсчет: http://mathworld.wolfram.com/SpanningTree.html. В соответствии с этим, Mathematica имеет функцию. Любые предложения в этом?

Answer 2

Что ж, легко доказать, что не может быть решения: просто сделайте ваш входной граф деревом, вершина которого имеет степень выше вашего предела.

Answer 3

В этой статье показано, как найти за полиномиальное время связующее дерево максимальной степени d + 1, которое по крайней мере так же хорошо, как любое остовное дерево максимальной степени d: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

// Редактировать Исходная ссылка в настоящее время неактивна, вместо нее попробуйте http://research.microsoft.com/pubs/80193/mbdst.pdf.