Я ищу помощь, чтобы доказать следующий вопрос: данного неориентированное дерева с п вершинами со степенью каждого из них < = 3, (1) доказать, что существует ребро, которое, если мы удалим, получим два дерева с числом вершин в каждом из них - максимум (2 * n/3). (2) предлагает линейный алгоритм, который находит такое ребро в указанном выше деревесоотношения между степенями вершин и краями удаления
Выберите произвольный корень. Проведите обход после заказа, чтобы вычислить размер каждого поддерева. Спустившись из корня через дочерние элементы с поддеревьями, по меньшей мере, как их братья и сестры, найдите поддерево размера между (n-1)/3 включительно и 2 (n-1)/3 + 1 эксклюзивом (шкала степени держит размер от уменьшения более чем на один, разделенный на два). Разделите его родительский край.
Проблема в том, что это условие не требует, чтобы первое условие было истинным. (Я думаю) –
@ShihabShahriar Вы должны быть более конкретными. –
Если дерево является корнем только с тремя вершинами в качестве дочернего (всего 4), удовлетворяет ли это (1)? –
@ShihabShahriar Если (2 * n/3) термин был округлен, возможно, проблем не было бы. – Gassa
@ShihabShahriar Да, в вашем примере удаление любого края из них будет удовлетворять. – user3857787