algorithm - 从图中消除顶点

Question

<分区>

Answer 1

这个问题有两条线索——线性时间要求和多副本洞察力。第一个建议任何顶点的处理次数不应超过固定次数，第二个建议需要维护一个队列来决定接下来访问哪个顶点。

基于此，我的大致思路如下。我们维护一个需要处理的顶点队列。如果一个顶点的出度为 2，或者它有多条边到一个或多个其他顶点，则必须对其进行处理。顶点在被发现时被放置在队列中。当向顶点添加或从中删除边时，就会发现顶点。

处理一个顶点

从队列中移除顶点v。 如果它的度数为 2(即 2 个邻居)，则移除到其邻居 u 和 w 的边 (O(1))。 在 u 和 w 之间添加一条边，如果这样的边尚不存在 (O(1))。 如果 u 现在的度数为 2 并且不在队列中，则添加到队列的前面。对 w 做同样的事情。 (每个 O(1))

Algorithm ProcessVertex(v, Q)
  Remove v from Q;
  IF Degree(v) == 2 and Seen(v) == False:
    Seen(v) = True
    u = Adj(v).first;
    RemoveEdge(u,v);
    w = Adj(v).first;
    RemoveEdge(u,w);
    IF !IsEdge(u,w)
      AddEdge(u,w);

算法

遍历顶点列表。对于每个顶点，如果度数为2，则将其加入队列；否则什么都不做。

趁队列不为空，处理前面的顶点。

Algorithm EliminateVertices(G)
  Q = empty queue;
  FOR v in G
    IF Degree(v) == 2
      EnqueueFront(v,Q);

  WHILE !IsEmpty(Q)
    ProcessVertex(Front(Q), Q);

线性复杂度的证明

• 我们可以在 O(1) 时间内检查两个顶点 i 和 j 之间是否已经存在边。这是使用邻接矩阵表示来实现的。在 O(1) 时间内跟踪每个节点的度数也很容易——只需在分别向节点添加边或从节点删除边时增加或减少计数。因此，每个 ProcessVertex 调用都需要 O(1) 时间。
• 每个顶点最多处理一次。证明:一个顶点一旦从队列中移除就不再存在。我们还可以高效地 (O(1)) 确保一个顶点不能多次添加到队列中(在每个顶点中标记它是否已经在队列中，如果是则不添加)。因此最多有 O(n) 次 ProcessVertex 调用。