从图中消除顶点 [英] Eliminating vertices from a graph

问题描述

从Skiena的书中，设计一个线性时间算法，通过将边（u，v）和（v）替换为图2中的每个顶点v， ，w）由边（u，w）表示。我们还试图通过用单个边替换它们来消除多个边的副本。请注意，删除边的多个副本可能会创建一个新度数为2的顶点，必须将其移除，并且删除度数为2的顶点可能会创建多个边，这些边也必须移除。

一般来说，我至少有一个办法，对于这个问题，我很无奈。这不是Hw，而仅仅是我自己的面试准备。

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

基于此，我的总体思路如下。我们维护一个需要处理的顶点队列。如果一个顶点的outdogree为2，或者它有一个或多个其他顶点的多个边，则必须处理该顶点。当发现它们时，顶点被放置在队列中。一个顶点被发现，当一个边被添加到它或从中移除。

处理顶点

从队列中移除顶点 v 。
如果它的度数为2（即2个邻居），请删除它的邻居 u 和 w （O（1） ）。
如果此边不存在（O（1）），则在 u 和 w 之间添加边。
如果 u 现在的等级为2并且不在队列中，请将其添加到队列的前面。对 w 做同样的事情。 （每个O（1））

 算法ProcessVertex（v，Q）
从Q中删除v; （v）== 2和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 =空队列; 
 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调用。
  
  

  From Skiena's Book,

  Design a linear-time algorithm to eliminate each vertex v of degree 2 from a graph by replacing edges (u,v) and (v,w) by an edge (u,w). We also seek to eliminate multiple copies of edges by replacing them with a single edge. Note that removing multiple copies of an edge may create a new vertex of degree 2, which has to be removed, and that removing a vertex of degree 2 may create multiple edges, which also must be removed.

  Generally, I at least have an approach, for this question, I am helpless. This is NOT Hw, but merely my own preparation for an interview.

  解决方案

  There are two clues in this question - the linear time requirement, and the multiple-copies insight. The first suggests that no vertex should be processed more than a fixed number of times, and the second suggests a queue needs to be maintained to decide which vertex to visit next.

  Based on this, my general idea is as follows. We maintain a queue of vertices that need to be processed. A vertex must be processed if either it has an outdegree of 2, or it has multiple edges to one or more other vertices. Vertices are placed on the queue as they are discovered. A vertex is discovered when an edge is added to it or removed from it.

  To process a vertex

  Remove the vertex v from the queue. If it has degree 2 (i.e. 2 neighbors), remove the edges to its neighbors u and w (O(1)). Add an edge between u and w if such an edge does not already exist (O(1)). If u now has a degree of 2 and is not already in the queue, add to the front of the queue. Do the same for w. (O(1) for each)

  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);
  

  The algorithm

  Iterate through the list of vertices. For each vertex, if it has a degree of 2, add it to the queue; else do nothing.

  While the queue is not empty, process the front vertex.

  Algorithm EliminateVertices(G)
    Q = empty queue;
    FOR v in G
      IF Degree(v) == 2
        EnqueueFront(v,Q);
  
    WHILE !IsEmpty(Q)
      ProcessVertex(Front(Q), Q);
  

  Proof of linear complexity

  • We can check in O(1) time whether an edge already exists between two vertices i and j. This is achieved using an adjacency matrix representation. It is also easy to keep track of the degree of each node in O(1) time - just increment or decrement the count when an edge is added to/removed from a node respectively. Hence each ProcessVertex call takes O(1) time.
  • Each vertex will be processed at most once. Proof: A vertex no longer exists once it is removed from the queue. We can also ensure efficiently (O(1)) that a vertex cannot be added to the queue more than once (mark in each vertex whether it is already in the queue, and do not add it if it is). Hence there are at most O(n) ProcessVertex calls.

  这篇关于从图中消除顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！