Тема: Максимальное бинарное дерево
Задача: В заданном ориентированном графе построить бинарное дерево, которое будет содержать максимальное количество вершин.
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Максимальное бинарное дерево
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Задача: В заданном ориентированном графе построить бинарное дерево, которое будет содержать максимальное количество вершин.
А итоговое бинарное дерево должно быть ориентированно от корня? или какую роль играет вообще ориентация этого графа? есть ли в нем циклы?
Граф произвольный. Из него надо убрать некоторые рёбра и вершины, чтобы в итоге получилось бинарное дерево. В дереве все рёбра должны идти сверху вниз, т.е. от отцов к сыновьям.
В дереве все рёбра должны идти сверху вниз, т.е. от отцов к сыновьям.
Что имеется ввиду сверху вниз?
Ведь мы как дерево не построй, оно всегда будет сверху вниз , если мы возьмем за верх любую вершину.
Есть ссылка на задачу? Или это чисто теоретический вопрос?
Сверху вниз имеется ввиду, что рёбра должны идти от корня дерева к листьям.
Переформулирую задачу:
В данном произвольном ориентированном графе необходимо выбрать максимальное множество рёбер, такое что:
1) В каждую вершину ведёт не больше одного ребра.
2) Из каждой вершины выходит не больше 2 рёбер.
3) Граф содержащий только это множество рёбер и только соответствующие им вершины связен. ( Хотя это условие вытекает из 1 и 2)
Есть ли какие-либо решения кроме полного перебора всех множеств рёбер?
Если я не ошибаюсь, то можно перебирать корни, а потом жадным обходом строить дерево, а именно: на каждом шаге выбирать такие две вершины, что количество ещё не выбранных, достижимых из двух сыновей этих вершин максимально. Наверное, прийдётся делать рекурсивно, но сложность должна будет быть адекватной.
Легко найти пример для которого жадно выбирать вершину, из которой достижимо наибольшее количество других, нельзя: Рассмотрим дерево. Из корня выходят 3 ветки. 2 ветки - это цепи длины 5, а оставшаяся ветка состоит из цепи длины 2, на конце которой висит куст.
Ну так выбирать стоит не по размеру поддерева, очевидно, что это не верно, а рекурсивно.
Ну так выбирать стоит не по размеру поддерева, очевидно, что это не верно, а рекурсивно.
Значит я не совсем понял, что вы имели ввиду. Опишите вашу идею подробнее.
У меня есть следущая идея:
Так как решить задачу в случае дерева можно за линейное время, то эту задачу можно свести к перебору всех деревьев в данном графе. Причём граф можно разбить на компоненты связности, и для каждой компоненты перебирать все остовные деревья. Но к сожалению в полном графе из N вершин количество таких деревьев будет N^(N-2).
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Максимальное бинарное дерево