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