无向图的平衡生成树 (T)
我已经连接了无向图。 我正在寻找构建图的平衡生成树（T）的方法
关于平衡生成树的具体信息，我可以定义如下：
- 如果树的根是 r .All 节点可以分为 级别。即所有节点 到 r 的距离（在 T 中）是 j 是 在Lj级等。
- 对于每个节点 w 可以定义为 T 的子树 T_w，使得 w 是它的 根。
- 目标是定义生成树 以这样的方式对于每个级别 Li,对于每两个节点 u 和 v 级别 Li 中的节点数 T_u 和 T_v 最大程度等价。
有人可以建议任何算法来构建这种“相对”平衡的生成树吗？
先感谢您。
I have connected undirected graph.
I am looking for the way to construct the balanced spanning tree (T) of a graph
The specific about balanced spanning tree, I could define as follows:
- If the root of the tree is r .All
nodes could be divided to the
levels.I.e all the nodes which
distance from the r (in T) is j are
in the level Lj,etc. - For each node w one can define for a
sub-tree T_w of T,such that w is its
root. - The goal is to define spanning tree
in such a way that for each level
Li,for every two nodes u and v in
level Li the number of nodes in the
T_u and T_v is maximally equivalent.
Does anybody can advice any algorithm/s for building such “relatively” balanced spanning tree?
Thank you in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我不确定你的表达“最大等效”。
这个问题可能没有完美的解决方案，所以显而易见的是我们能做得更好吗？
一般来说，这个问题似乎是 NP 完全问题。如果幸运的话，一些贪婪的方法可能会导致恒定的近似算法。
I am not sure about your expression "maximally equivalent."
This problem may not have a perfect solution, so the obvious thing is how much better can we do?
This problem in generality seems to be NP-Complete. Some greedy approaches might result in constant approx algorithms, if you are lucky.
这似乎是微不足道的。让 G 成为你的图。它是相连的，因此每对顶点之间都有一条边。使用该定义，构造一个与 G 具有相同顶点数的任意平衡生成树 G'。从 G' 中的 r 和 G 中任意选择的顶点开始，将 G' 中的每个顶点映射到G 中的顶点。删除 G 中所有在 G' 中没有对应边的边。
生成的图（称为“更新的 G”的 U）——通过构造具有与 G' 相同数量的顶点，并且进一步通过构造，当且仅当 G' 中存在相应的边时，U 中存在一条边。因此U=G'并且由此得出U是平衡生成树。
This appears to be trivial. Let G be your graph. It is connected, so there is an edge between each pair of vertices. Using the definition, construct an arbitrary balanced spanning tree G' with the same number of vertices as G. Starting at r in G' and an arbitrarily chosen vertex of G, map each vertex in G' to a vertex in G. Delete all edges in G that don't have a corresponding edge in G'.
The resulting graph -- call it U for "updated G" -- by construction has the same number of vertices as G', and further by construction, an edge exists in U iff the corresponding edge exists in G'. Thus U=G' and it follows that U is a balanced spanning tree.
您希望将树构建为 AVL 树。
您可以从此 PDF 文档的 第 12 页开始找到用于实现它的其他信息和代码。
此 PowerPoint 文档 有一些漂亮的图片来帮助解释正在发生的事情，并且包括 AVL 树数据类型的 Java 实现。
You want to construct your tree as an AVL tree.
You can find additional information and code used to implement it starting on page 12 of this PDF document.
This PowerPoint document has some pretty pictures to help explain what's going on and also includes a Java implementation of the AVL Tree data type.