Тема: Максимальное бинарное дерево
Задача: В заданном ориентированном графе построить бинарное дерево, которое будет содержать максимальное количество вершин.
Re: Максимальное бинарное дерево
А итоговое бинарное дерево должно быть ориентированно от корня? или какую роль играет вообще ориентация этого графа? есть ли в нем циклы?
Re: Максимальное бинарное дерево
Граф произвольный. Из него надо убрать некоторые рёбра и вершины, чтобы в итоге получилось бинарное дерево. В дереве все рёбра должны идти сверху вниз, т.е. от отцов к сыновьям.
Re: Максимальное бинарное дерево
SkyterX пишет:
В дереве все рёбра должны идти сверху вниз, т.е. от отцов к сыновьям.
Что имеется ввиду сверху вниз?
Ведь мы как дерево не построй, оно всегда будет сверху вниз , если мы возьмем за верх любую вершину.
Есть ссылка на задачу? Или это чисто теоретический вопрос?
Re: Максимальное бинарное дерево
Сверху вниз имеется ввиду, что рёбра должны идти от корня дерева к листьям.
Переформулирую задачу:
В данном произвольном ориентированном графе необходимо выбрать максимальное множество рёбер, такое что:
1) В каждую вершину ведёт не больше одного ребра.
2) Из каждой вершины выходит не больше 2 рёбер.
3) Граф содержащий только это множество рёбер и только соответствующие им вершины связен. ( Хотя это условие вытекает из 1 и 2)
Есть ли какие-либо решения кроме полного перебора всех множеств рёбер?
Re: Максимальное бинарное дерево
Если я не ошибаюсь, то можно перебирать корни, а потом жадным обходом строить дерево, а именно: на каждом шаге выбирать такие две вершины, что количество ещё не выбранных, достижимых из двух сыновей этих вершин максимально. Наверное, прийдётся делать рекурсивно, но сложность должна будет быть адекватной.
Re: Максимальное бинарное дерево
Легко найти пример для которого жадно выбирать вершину, из которой достижимо наибольшее количество других, нельзя: Рассмотрим дерево. Из корня выходят 3 ветки. 2 ветки - это цепи длины 5, а оставшаяся ветка состоит из цепи длины 2, на конце которой висит куст.
Re: Максимальное бинарное дерево
Ну так выбирать стоит не по размеру поддерева, очевидно, что это не верно, а рекурсивно.
9 2011-04-21 18:36:26 Отредактировано SkyterX (2011-04-21 20:24:28)
Re: Максимальное бинарное дерево
coder.ua пишет:
Ну так выбирать стоит не по размеру поддерева, очевидно, что это не верно, а рекурсивно.
Значит я не совсем понял, что вы имели ввиду. Опишите вашу идею подробнее.
У меня есть следущая идея:
Так как решить задачу в случае дерева можно за линейное время, то эту задачу можно свести к перебору всех деревьев в данном графе. Причём граф можно разбить на компоненты связности, и для каждой компоненты перебирать все остовные деревья. Но к сожалению в полном графе из N вершин количество таких деревьев будет N^(N-2).