col*_*sar 10
这是关于如何解决问题的建议.
先决条件
- 符号:
g图,g.v图顶点v,w,z:个别顶点e:个人优势n:顶点数
- 无向树g和给定节点gv的任何组合唯一地确定具有根gv的有向树(可通过归纳证明)
理念
g通过在g节点处的局部计算补充由有意树和未被找到的根节点中的方向的边缘g.- 这些方向将代表节点之间的子父关系(
v -> w:vchild,wparent). - 完全标记的树将包含一个outdegree 0的唯一节点,它是所需的根节点.您可能最终得到0个或多个根节点.
算法
假设图形/树结构的标准表示(例如邻接列表)
- 所有顶点
g.v最初都标记为未访问,未完成. 以任意顺序访问所有顶点.跳过标记为"已完成"的节点.
让我们v成为当前访问过的顶点.- 2.1扫描
v顺时针连接的所有边缘e_0,以边缘角度的顺序随机选择e_0. 2.2.定向相邻边缘
e_1=(v,w_1), e_2(v,w_2),包围锐角.
相邻:wrt根据它们所包围的角度进行排序e_0.[注意:不保证存在这样的一对,见第2条评论和最后评论.如果没有锐角,请在2.下一个节点处继续.]
2.2.1边缘的方向
e_1, e_2是已知的:w_1 -> v -> w_2:不可能,因为祖父母 - 儿童部分会包围一个锐角w_1 <- v <- w_2:不可能,同样的道理w_1 <- v -> w_2:不可能,树中的outdegree> 1没有节点w_1 -> v <- w_2:
只有一对可能的方向.e_1, e_2以前可能已经定位过了.如果先前的方向违反了当前的分配,则问题实例没有解决方案.
2.2.2这个赋值意味着子图上的树结构由在
w_1(w_2不包括e_1 (e_2`)的路径上的()可到达的所有顶点引起.将两个诱导子树中的所有顶点标记为已完成[注意:子树结构可能违反角度约束.在这种情况下,问题没有解决方案.]
2.3标记
v访问.在顶点完成步骤2.2后v,检查nc连接尚未分配方向的边数.nc = 0:这是您一直在寻找的根 - 但您必须检查解决方案是否与您的约束兼容.nc = 1:让这个优势(v,z).
当你在树上时,这条边的方向是v-> z.标记v完成.- 2.3.1检查
z是否标记完成.如果不是,请检查nc2连接的无定向边数z.nc2= 1:重复步骤2.3通过取z为v.
- 2.3.1检查
- 2.1扫描
如果您还没有找到根节点,则您的问题实例是不明确的:随意定向剩余的未定向边.
备注
终止:每个节点最多访问4次:
- 每步骤一次2
- 每步最多两次2.2.2
- 每步最多一次2.3
正确性:
- 所有包围锐角的边缘都按步骤2.2.1定向
复杂性(时间):
- 访问每个节点:O(n);
顺时针扫过连接给定顶点的所有边需要对这些边进行排序.
因此你需要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(通过施加拉格朗日优化可证).[注意:如果你的树有一个由常数限定的度数,你理论上会在每个受影响的节点上按时间排序; 在这种情况下总计:
O(n)]子树标记:
如果实现为dfs,则通过此过程最多访问图中的每个节点2次.因此是O(n)调用该子程序的总计.总共:
O(n * lg n)
复杂性(空间):
O(n)用于排序(顶点度不是常量限制的).
问题可能是定义不明确的:
- 多种解决方案:例如steiner树
- 没有解决方案:例如形状像双尖箭头的图形(< - >)