Нахождение связующего дерева, которое минимизирует сумму глубин узлов

Question

У меня есть ненаправленный связный граф с невзвешенными ребрами. Как построить связующее дерево (решение может быть не уникальным) таким образом, чтобы сумма глубин всех узлов была минимизирована? Это, очевидно, не нахождение минимального остовного дерева, так как "вес" ребер на самом деле варьируется в зависимости от глубины ребенка.

Я думаю, что при заданном корне дерево с минимальной суммой глубин может быть сформировано путем жадного соединения всего, что вы можете соединить как дочерние, с каждым узлом в порядке первого порядка. Поэтому я собираюсь найти дерево с минимальной общей глубиной, применяя эту же процедуру N раз, назначая каждый из N узлов корневым и выбирая минимальный из N кандидатов. Это действительный алгоритм? Пожалуйста, укажите, если это не так, или если существует что-то более эффективное.

Answer 1

Это действительный алгоритм?

Да, алгоритм правильный.

Данный узел R то есть считается корнем связующего дерева, глубиной узла N в связующем дереве по крайней мере длина кратчайшего пути из R в N в графе, таким образом, сумма глубин, по крайней мере, является суммой длин кратчайших путей (из R).

Дерево, построенное по алгоритму, соединяет каждый узел с R с одним из самых коротких путей, поэтому сумма глубин является суммой расстояний, которые мы видели выше, является нижней границей.

В качестве небольшой оптимизации, если число узлов составляет не менее 3, нет необходимости рассматривать узлы со степенью 1 как корень дерева. (Для дерева с корнем в узле R со степенью 1, рассмотрим тот же граф, рассматриваемый как дерево с корнем в Rсосед. Глубина R увеличивается на 1, глубина всех остальных узлов уменьшается на 1, поэтому сумма глубин уменьшается на number_of_nodes - 2.)