Eliminating vertices from a graph [closed]

问题:

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.

回答1:

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.