Напишите эффективный алгоритм, чтобы разделить дерево на связанные компоненты с не более чем V / 2 вершинами.

Question

Я ссылаюсь на ссылку ниже, чтобы попытаться написать алгоритм для поиска вершины в дереве, чтобы удаление этой вершины давало связанные компоненты с размером каждого компонента, не превышающим V / 2 вершин.

https://math.stackexchange.com/questions/1742440/you-can-always-delete-a-vertex-from-a-tree-g-such-that-the-remaining-connected

Я понимаю доказательство, данное в принятом ответе, в котором используются стрелки, чтобы найти эту вершину.Я не могу понять, как написать алгоритм для того же.

Answer 1

Я просто объясню доказательство, а затем дам псевдокод, чтобы вы могли легко понять код псевдо.Вершина, которую вы ищете, называется centroid .Таким образом, в основном нам нужно найти центроид дерева.

Прежде всего это должно быть ясно, что может быть только один узел, который удовлетворяет этому свойству.

Пусть заданным деревом будет T. Начните с любой вершины, утверждающей, что она является искомой.Затем проверьте, правда ли это или нет.Если это требуемая вершина, то ничего не нужно делать.Если это не вершина, тогда выберите следующую вершину, смежную с текущей вершиной, которая является частью поддерева, в котором было больше чем n / 2 вершин.Повторяйте процесс, пока не найдете ответ.

Теперь псевдокод.Вот значение используемых переменных.

v_centroid хранит центроид

v [i] хранит список всех узлов, которые подключены к i

size [i] хранит размер поддерева i.

v_centroid = any vertex
dfs(v_centroid,parent)   // v_centroid is the assumed centroid and parent is parent of the node processing. For initial call you can use -1 as parent or any other undefined value suitable.
v_centroid = findCentroid(v_centroid,v_centroid)


func dfs(int node, int parent) 
    size[node] := 1
    for i in v[node] 
        if(*i not equals parent) 
            dfs(*i, node)
            size[node] = size[node] + size[parent]
        end if
    end for
end func

func findCentroid(int node, int parent) 
    for i in v[node]
        if(i not equals parent and size[i]>MAX_SIZE/2)
            return findCentroid(i, node)
        end if
    end for
    return node
end func