无向图转换为树 [英] Undirected graph conversion to tree

问题描述

给出一个无向图，其中每个节点在空间中具有笛卡尔坐标，并且具有树的一般形状，是否有一种算法可以将图形转换成树，并找到合适的根节点?

Given an undirected graph in which each node has a Cartesian coordinate in space that has the general shape of a tree, is there an algorithm to convert the graph into a tree, and find the appropriate root node?

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

Note that our definition of a "tree" requires that branches do not diverge from parent nodes at acute angles.

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

See the example graphs below. How do we find the red node?

推荐答案

这是有关如何解决问题的建议.

here is a suggestion on how to solve your problem.

• 符号:
  
  • g图，g.v图顶点
  • v,w,z:单个顶点
  • e:单个边缘
  • n:顶点数
  • notation:
    
    • g graph, g.v graph vertices
    • v,w,z: individual vertices
    • e: individual edge
    • n: number of vertices
    • 通过g所隐含的有向树中的方向和g的节点处的局部计算来补充g的边缘.
    • 这些方向将表示节点(v -> w:v子级，w父级)之间的父子关系.
    • 完全标记的树将包含一个度数为0的唯一节点，这是所需的根节点.您可能最终得到0个或多个根节点.
    • complement the edges of g by orientations in the directed tree implied by g and the yet-to-be-found root node by local computations at the nodes of g.
    • these orientations will represent child-parent-relationsships between nodes (v -> w: v child, w parent).
    • the completely marked tree will contain a sole node with outdegree 0, which is the desired root node. you might end up with 0 or more than one root node.

    假设图形/树结构(例如，邻接表)的标准表示形式

    assumes standard representation of the graph/tree structure (eg adjacency list)

    1. g.v中的所有顶点最初都标记为未访问，尚未完成.

    2. 以任意顺序访问所有顶点.跳过标记为完成"的节点.
       设v为当前访问的顶点.

    1. all vertices in g.v are marked initially as not visited, not finished.

    2. visit all vertices in arbitrary sequence. skip nodes marked as 'finished'.
       let v be the currently visited vertex.

    • 2.1从所有随机选择的e_0开始的顺时针方向依次扫描v的边缘，按边缘与e_0的角度顺序.

    • 2.2.将相邻的边缘e_1=(v,w_1), e_2(v,w_2)定向为锐角.
      相邻:根据它们与e_0包围的角度排序.

    • 2.1 sweep through all edges linking v clockwise starting with a randomly chosen e_0 in the order of the edges' angle with e_0.

    • 2.2. orient adjacent edges e_1=(v,w_1), e_2(v,w_2), that enclose an acute angle.
      adjacent: wrt being ordered according to the angle they enclose with e_0.

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

    [ note: the existence of such a pair is not guaranteed, see 2nd comment and last remark. if no angle is acute, proceed at 2. with next node. ]

    • 2.2.1边缘e_1, e_2的方向是已知的:

    • w_1 -> v -> w_2:不可能，因为祖父母-儿童段会围成一个锐角
    • w_1 <- v <- w_2:不可能，原因相同

    • w_1 <- v -> w_2:不可能，树中没有度数大于1的节点

    • w_1 -> v -> w_2: impossible, as a grandparent-child-segment would enclose an acute angle
    • w_1 <- v <- w_2: impossible, same reason

    • w_1 <- v -> w_2: impossible, there are no nodes with outdegree >1 in a tree

    w_1 -> v <- w_2:
    唯一可能的一对方向. e_1, e_2以前可能已经被定位.如果先前的方向违反了当前的分配，则问题实例没有解决方案.

    w_1 -> v <- w_2:
    only possible pair of orientations. e_1, e_2 might have been oriented before. if the previous orientation violates the current assignment, the problem instance has no solution.

    2.2.2这种分配意味着子图上的树结构，该子图由从w_1(w_2)到达的不包含e_1 ( e_2`的路径上的所有顶点所诱导.将两个诱导子树中的所有顶点标记为已完成

    2.2.2 this assignment implies a tree structure on the subgraphs induced by all vertices reachable from w_1 (w_2) on a path not comprising e_1 (e_2`). mark all vertices in both induced subtrees as finished

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

    [ note: the subtree structure might violate the angle constraints. in this case the problem has no solution. ]

    2.3标记v.在顶点v完成步骤2.2之后，检查尚未分配方向的连接边数nc.

    2.3 mark v visited. after completing steps 2.2 at vertex v, check the number nc of edges connecting that have not yet been assigned an orientation.

    • nc = 0:这是您一直在寻找的根-但您必须检查解决方案是否与您的约束兼容.

    • nc = 1:将此边设为(v,z).
      就像在树上一样，这条边的方向是v-> z.将v标记为完成.

    • nc = 0: this is the root you've been searching for - but you must check whether the solution is compatible with your constraints.

    • nc = 1: let this edge be (v,z).
      the orientation of this edge is v->z as you are in a tree. mark v as finished.

    • 2.3.1检查z是否标记为完成. 如果不是，请检查连接z的未定向边缘的数量nc2. nc2 = 1:对v取z，重复步骤2.3.
    • 2.3.1 check z whether it is marked finished. if it is not, check the number nc2 of unoriented edges connecting z. nc2 = 1: repeat step 2.3 by taking z for v.

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

    if you have not yet found a root node, your problem instance is ambiguous: orient the remaining unoriented edges at will.

    备注

    1. 终止: 每个节点最多访问4次:

    1. termination: each node is visited at max 4 times:

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

    正确性:

    • 围绕锐角的所有边缘均按步骤2.2.1定向

    复杂度(时间):

    • 访问每个节点:O(n);

    • 在连接给定顶点的所有边上进行顺时针扫描需要对这些边进行排序.
      因此，您需要在约束sum_i=1..m k_i = n下的m <= n顶点处的O( sum_i=1..m ( k_i * lg k_i ) ).

    • visiting every node: O(n);

    • the clockwise sweep through all edges connecting a given vertex requires these edges to be sorted.
      thus you need O( sum_i=1..m ( k_i * lg k_i ) ) at m <= n vertices under the constraint sum_i=1..m k_i = n.

    总共需要O ( n * lg n)，对于任何m <= n，给定sum_i=1..m k_i = n的sum_i=1..m ( k_i * lg k_i ) <= n * lg n(可通过应用滞后范围优化来证明).

    in total this requires O ( n * lg n), as sum_i=1..m ( k_i * lg k_i ) <= n * lg n given sum_i=1..m k_i = n for any m <= n (provable by applying lagrange optimization).

    [注意:如果您的树的度数受常数限制，则理论上您会在受影响的每个节点上按恒定的时间进行排序；在这种情况下总计:O(n)]

    [ note: if your trees have a degree bounded by a constant, you theoretically sort in constant time at each node affected; grand total in this case: O(n) ]

    子树标记:
    如果实现为dfs，则此过程最多可访问图形中的每个节点2次.因此，用于调用此子例程的O(n)总计.

    subtree marking:
    each node in the graph is visited at max 2 times by this procedure if implemented as a dfs. thus a grand total of O(n) for the invocation of this subroutine.

    总计:O(n * lg n)

    复杂度(空格):

    • O(n)用于排序(顶点度不是常数约束).
    • O(n) for sorting (with vertex-degree not constant-bound).

    问题可能定义不清:

    • 多种解决方案:例如斯坦纳树
    没有解决方案:例如形状像双尖箭头(<->)的图形
    • multiple solutions: e.g. steiner tree
    • no solution: e.g. graph shaped like a double-tipped arrow (<->)

    这篇关于无向图转换为树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！