Добрый день!
Пожалуйста, помогите разобраться с такой проблемой. Известна задача про мин. остовное дерево с ограничениями на степень, когда для некоторого набора вершин требуют чтобы степень была не выше заданной. Она нп-трудная, как известно. Я ищу решение задачи с противоположным условием, она явно попроще, но все равно запутался
Есть граф (неориентированный, связный, не мульти, иррефлексивный, ребра неотриц. длины). Некоторые вершины назовем терминалами (пусть будет штейнеровская терминология). Требуется найти mst с условием чтобы нетерминалы имели степень не менее 2. (результирующее дерево должно охватить все вершины, как терминалы так и нетерминалы).
Ясно что если есть нетерминалы степени 1 то нет такого дерева. В случае если есть нетерминалы степени 2 то такого дерева может не быть. Для случая когда все нетерминалы - степени не менее 3, я не знаю такого исходного графа чтобы не было mst указанного вида, но не могу это доказать. Пожалуйста, помогите найти хотя бы алгоритм проверки есть ли произвольное охватывающее дерево нужного вида - тогда я может сам найду как искать минимум. Что-то торможу
Заранее спасибо
31.08.2007, 10:32 
