graph - 无向图转换为树

Question

给定一个undirected graph，其中每个节点在空间中具有一棵树的一般形状的笛卡尔坐标，是否存在一种算法将图转换为树并找到合适的根节点？

请注意，我们对“树”的定义要求分支不要以锐角偏离父节点。

请参见下面的示例图。我们如何找到红色节点？

Answer 1

这是关于如何解决您的问题的建议。

先决条件


符号：

g图，g.v图顶点
v,w,z：单个顶点
e：单个边缘
n：顶点数

无向树g和给定节点g.v的任何组合唯一地确定根g.v的有向树（通过归纳证明）


理念


通过g节点所隐含的有向树中的方向和尚未被发现的根节点来补充g的边缘。
这些方向将表示节点（g：v -> w子级，v父级）之间的子级-父级关系。
完全标记的树将包含一个以0度为外的唯一节点，这是所需的根节点。您可能最终得到0个或多个根节点。


算法

假定图形/树结构的标准表示形式（例如，邻接表）


w中的所有顶点最初都标记为未访问，未完成。
按任意顺序访问所有顶点。跳过标记为“完成”的节点。
令g.v为当前访问的顶点。


2.1从随机选择的v开始按顺时针方向依次链接v的所有边缘，其顺序为边缘与e_0的角度。
2.2。将相邻的边缘e_0定向为锐角。
相邻：根据e_1=(v,w_1), e_2(v,w_2)包围的角度排序。

[注意：不能保证有这样的一对，请参阅第二条评论和最后一句话。如果没有锐角，则从2.下一个节点继续。 ]


2.2.1边缘e_0的方向是已知的：


e_1, e_2：不可能，因为祖父母-儿童段将围成一个锐角
w_1 -> v -> w_2：不可能，原因相同
w_1 <- v <- w_2：不可能，树中没有度数大于1的节点
w_1 <- v -> w_2：
唯一可能的一对方向。 w_1 -> v <- w_2以前可能已经被定位。如果先前的方向违反了当前的分配，则问题实例没有解决方案。

2.2.2这种分配意味着在子图上的树结构是由在不包含e_1, e_2 e_2`的路径上从w_1（w_2）可到达的所有顶点所诱导的。将两个诱导子树中的所有顶点标记为完成

[注意：子树结构可能违反角度约束。在这种情况下，问题无法解决。 ]

2.3标记e_1 (已访问。在顶点v中完成步骤2.2之后，检查尚未分配方向的连接边数v。


nc：这是您一直在寻找的根源-但您必须检查解决方案是否与您的约束兼容。
nc = 0：将此边设为nc = 1。
就像在树上一样，该边的方向是v-> z。将v标记为完成。


2.3.1检查(v,z)是否标记为完成。
如果不是，请检查连接z的未定向边缘的数量nc2。
z = 1：对nc2取z，重复步骤2.3。



如果尚未找到根节点，则问题实例是不确定的：
随意调整其余未定向的边缘。


备注


终止：
每个节点最多访问4次：


每步骤2次
每步最多两次两次2.2.2
每步最多一次2.3

正确性：


按照步骤2.2.1定向所有包含锐角的边缘

复杂度（时间）：


访问每个节点：O（n）;
顺时针扫描通过连接给定顶点的所有边需要对这些边进行排序。
因此，您需要在v约束下的O( sum_i=1..m ( k_i * lg k_i ) )顶点处使用m <= n。

总的来说，这需要sum_i=1..m k_i = n，因为对于任何O ( n * lg n)，sum_i=1..m ( k_i * lg k_i ) <= n * lg n都指定了sum_i=1..m k_i = n（可通过应用滞后范围优化来证明）。

[注意：如果您的树木的度数受常数限制，则理论上您会在受影响的每个节点上按恒定的时间排序；在这种情况下总计：m <= n]
子树标记：
如果实现为dfs，则此过程最多可访问图形中的每个节点2次。因此，用于调用此子例程的O(n)总计。

总计：O(n)

复杂度（空间）：


O(n * lg n)进行排序（顶点度不恒定）。

问题可能不明确：


多种解决方案：例如斯坦纳树
没有解决方案：例如形状像双箭头（<->）的图形