来自无向图的平衡生成树(T)

Question

我连接了无向图.我正在寻找构建图的平衡生成树(T)的方法

具体关于平衡生成树,我可以定义如下:

1. 如果树的根是r.所有节点都可以被划分为级别.所有与r(在T中)的距离为j的节点都在级别Lj等中.
2. 对于每个节点w,可以为T的子树T_w定义,使得w是其根.
3. 目标是以这样的方式定义生成树:对于每个级别Li,对于级别Li中的每两个节点u和v,T_u和T_v中的节点的数量是最大等效的.

是否有人可以建议任何算法用于构建这种"相对"平衡的生成树？

先感谢您.

Answer 1

我不确定你的表达“最大等效”。

这个问题可能没有完美的解决方案，所以显而易见的是我们能做得更好吗？

一般来说，这个问题似乎是 NP 完全问题。如果幸运的话，一些贪婪的方法可能会导致恒定的近似算法。