Disconnect all vertices in a graph

 

I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (ie the graph won't have any edges).

  • Is there such algorithm?
  • If not: Could you recommend some kind of heuristics to designate the vertices.

    • I have a basic knowledge of graph theory so please excuse any incorrectness.

    IIUC, this is the classic Minimum Vertex Cover problem, which is, unfortunately, NP Complete.

    Fortunately, the most intuitive and greedy possible algorithm is as good as it gets in this case.

    The greedy algorithm is a 2-approximation for vertex cover, which in theory, under the Unique Games Conjecture, is as good as it gets. In practice, solving a formulation of vertex cover as an integer program will most likely yield much better results. The program is 

    min sum_{v in V} x(v)
s.t.
forall {u, v} in E, x(u) + x(v) >= 1
forall v in V, x(v) in {0, 1}.

    Try this way:

  • Define a variable to count number of vertexes, starting by 0;
  • Create a Max-Heap of vertexes sorted by the length of the adjacent list of each vertex;
  • Remove all edges from the first vertex of the Heap (the one with biggest number of edges) and remove it from the Heap, adding 1 to the count;

  • Reorder the Heap now that number of edges of the vertexes changed, repeating the previous step until the length of the adjacent list from the first vertex is 0; 

    Heap Q
int count = 0

while(1){

    Q = Create_Heap(G)
    Vertex first = Q.pop
    if(first.adjacents.size() == 0) {
        break
    }

    for( Vertex v : first.adjacent ){
        RemoveEdge(first, v)
        RemoveEdge(v, first)    /* depends on the implementation */
    }

    count = count + 1

}

return count
    • 链接地址: http://www.djcxy.com/p/12196.html

    上一篇: 在n个硬币中查找假币的算法

    下一篇: 断开图中的所有顶点