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

Question

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

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

Спасибо.

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

Answer 1

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

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

Answer 2

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

Answer 3

Гэри Джонсон свел эту проблему к Гамильтону :( Вот это помогло.Аппроксимация первого: http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.pptОднако более эффективные модели ценятся...

Подсчет: http://mathworld.wolfram.com/SpanningTree.html .Согласно этому, у математики есть функция.Есть какие-нибудь предложения по этому поводу?