Сбалансированное связующее дерево (T) из неориентированного графа

Question

Я подключил неориентированный граф. Я ищу способ построения сбалансированного связующего дерева (T) графа

Конкретно о сбалансированном связующем дереве я могу определить следующим образом:

1. Если корень дерева r .Все узлы могут быть разделены на уровни. Т.е. все узлы, которые Расстояние от r (в T) составляет j на уровне Lj и т. д.
2. Для каждого узла w можно определить для поддерево T_w T, такое, что w является его корень.
3. Цель состоит в том, чтобы определить связующее дерево таким образом, что для каждого уровня Li, для каждых двух узлов u и v в Уровень Li количество узлов в T_u и T_v максимально эквивалентны.

Кто-нибудь может посоветовать какой-либо алгоритм (ы) для построения такого «относительно» сбалансированного связующего дерева?

Заранее спасибо.

Answer 1

Я не уверен насчет вашего выражения "максимально эквивалентно".

Эта проблема может не иметь идеального решения, поэтому очевидно, насколько лучше мы можем сделать?

Эта проблема в общем, кажется, NP-Complete. Некоторые жадные подходы могут привести к постоянным приблизительным алгоритмам, если вам повезет.

Answer 2

Вы хотите построить свое дерево как AVL дерево .

Вы можете найти дополнительную информацию и код, используемый для его реализации, начиная со страницы этого документа PDF .

Этот документ PowerPoint содержит несколько симпатичных картинок, помогающих объяснить происходящее, а также включает в себя реализацию Java типа данных AVL Tree.

Answer 3

Это кажется тривиальным. Пусть G будет вашим графом. Это связано, так что между каждой парой вершин есть ребро. Используя определение, создайте произвольное сбалансированное остовное дерево G 'с тем же числом вершин, что и G. Начиная с r в G' и произвольно выбранной вершины G, отобразите каждую вершину в G 'на вершину в G. Удалите все ребра в G, у которых нет соответствующего ребра в G '.

Результирующий граф - назовите его U для «обновленного G» - по построению имеет то же число вершин, что и G ', и далее по построению ребро существует в U, если соответствующее ребро существует в G'. Таким образом, U = G 'и из этого следует, что U является сбалансированным остовным деревом.