Вопрос: Пусть T будет деревом с n узлами, корнем которого является некоторый узел r.Мы хотим разместить как можно меньше защитных элементов в узлах T, так что каждое ребро T охраняется: ребро между родительским узлом v и его дочерним элементом w охраняется, если один из них устанавливает охрану хотя бы на один из этих двух узлов v., ш.Дайте O (n) временной алгоритм для нахождения оптимального решения проблемы.
Мой подход состоял в том, чтобы сделать обход по порядку после корня и установить охрану на узле, который является частью неохраняемого ребра, кроме случаев, когдаэтот узел является листом ... но этот алгоритм не сработал бы, если бы все узлы были расположены в линейной цепочке, потому что мой алгоритм установил бы охрану на каждом узле, кроме концов цепочки.
Я посмотрел онлайн и проверил решения DP, которые имеют смысл для меня, но мне было интересно, есть ли жадный алгоритм, чтобы найти покрытие вершины для дерева