Минимальное опалубочное дерево с листьями?

Меня попросили написать алгоритм, который найдет минимальное связующее дерево в графе G, но с условием, что каждая вершина из G является отступом в охватывающем дереве T. Как это возможно, если граф имеет больше, чем 2 элемента? Пусть G содержит вершины a, b и c, Spanning tree может что-то вроде a-b-c, поэтому в этом случае b не является листом.Минимальное опалубочное дерево с листьями?

Я не ищу решение алгоритма, я хочу только понять, как Spanning Tree может состоять исключительно из листьев.

Вот точная формулировка вопроса

Спасибо за помощь

источник

2016-02-14 user1354784

Комментируя здесь, чтобы другие не беспокоились: я не вижу в заявлении проблемы, что затраты c_e должны быть разными. Если бы это было так, то проблема была без проблем, потому что есть уникальный MST, и ваш aproach будет работать. Тем не менее, я не думаю, что именно так должна быть проблема. – ead

вопрос гласит, что S является подмножеством вершин V в графе. Могут быть нелистовые узлы. Однако вы должны убедиться, что эти внутренние узлы не находятся в S. Если S будет равно V, вы были бы правы.

источник

2016-02-14 21:11:31 lex82

Спасибо, что я закончил делать с помощью Boruvka, чтобы получить MST, а затем итерации через каждый узел и сравнения их с вершинами в наборе. Если они одинаковы, я проверяю, нет ли у узла дочерних элементов, иначе MST не представляется возможным. – user1354784

@ user1354784 Я не думаю, что ваш подход будет работать, потому что MST не уникален, и вы не можете быть уверены, что Boruvka (или любой стандартный алгоритм еще) выберет правильный MST. Могут быть некоторые MST, которые выполняют ограничение относительно листьев, а некоторые - нет. – ead

Я думаю, мы можем предположить, что все ребра имеют различные значения – user1354784

Минимальное опалубочное дерево с листьями?

ответ

Смежные вопросы