无向图的顶点覆盖是其顶点的子集，因此对于图的每一条边（u，v），要么“u”要么“v”在顶点覆盖中。虽然名称为顶点覆盖，但集合覆盖给定图形的所有边。 给定一个无向图，顶点覆盖问题就是寻找最小大小的顶点覆盖 . 以下是一些例子。
null
顶点覆盖问题 这是一个已知的 NP完全问题 ，即，除非P=NP，否则没有多项式时间解。不过，有一些近似的多项式时间算法可以解决这个问题。下面是一个简单的近似算法，改编自 CLRS手册 .
天真的方法：
逐个考虑顶点的所有子集，并找出它是否覆盖图的所有边。例如，在只有3个顶点的图中，由顶点组合组成的集合是：{0,1,2，{0,1}，{0,2}，{1,2}，{0,1,2}，{0,1,2}。使用该集合的每个元素检查这些顶点是否覆盖了图形的所有边。因此，更新最佳答案。因此，打印具有最小顶点数的子集，该子集也覆盖了图的所有边。
顶点覆盖的近似算法：
1) Initialize the result as {}2) Consider a set of all edges in given graph. Let the set be E.3) Do following while E is not empty...a) Pick an arbitrary edge (u, v) from set E and add 'u' and 'v' to result...b) Remove all edges from E which are either incident on u or v.4) Return result
下图显示了上述近似算法的执行情况：
上述算法的性能如何？ 可以证明，上述近似算法从未找到大小超过最小可能顶点覆盖大小两倍的顶点覆盖（参考 这 （为了证明） 实施： 下面是C++和java实现的上述近似算法。
C++
// Program to print Vertex Cover of a given undirected graph #include<iostream> #include <list> using namespace std; // This class represents a undirected graph using adjacency list class Graph { int V; // No. of vertices list< int > *adj; // Pointer to an array containing adjacency lists public : Graph( int V); // Constructor void addEdge( int v, int w); // function to add an edge to graph void printVertexCover(); // prints vertex cover }; Graph::Graph( int V) { this ->V = V; adj = new list< int >[V]; } void Graph::addEdge( int v, int w) { adj[v].push_back(w); // Add w to v’s list. adj[w].push_back(v); // Since the graph is undirected } // The function to print vertex cover void Graph::printVertexCover() { // Initialize all vertices as not visited. bool visited[V]; for ( int i=0; i<V; i++) visited[i] = false ; list< int >::iterator i; // Consider all edges one by one for ( int u=0; u<V; u++) { // An edge is only picked when both visited[u] and visited[v] // are false if (visited[u] == false ) { // Go through all adjacents of u and pick the first not // yet visited vertex (We are basically picking an edge // (u, v) from remaining edges. for (i= adj[u].begin(); i != adj[u].end(); ++i) { int v = *i; if (visited[v] == false ) { // Add the vertices (u, v) to the result set. // We make the vertex u and v visited so that // all edges from/to them would be ignored visited[v] = true ; visited[u] = true ; break ; } } } } // Print the vertex cover for ( int i=0; i<V; i++) if (visited[i]) cout << i << " " ; } // Driver program to test methods of graph class int main() { // Create a graph given in the above diagram Graph g(7); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(3, 4); g.addEdge(4, 5); g.addEdge(5, 6); g.printVertexCover(); return 0; } |
JAVA
// Java Program to print Vertex // Cover of a given undirected graph import java.io.*; import java.util.*; import java.util.LinkedList; // This class represents an undirected // graph using adjacency list class Graph { private int V; // No. of vertices // Array of lists for Adjacency List Representation private LinkedList<Integer> adj[]; // Constructor Graph( int v) { V = v; adj = new LinkedList[v]; for ( int i= 0 ; i<v; ++i) adj[i] = new LinkedList(); } //Function to add an edge into the graph void addEdge( int v, int w) { adj[v].add(w); // Add w to v's list. adj[w].add(v); //Graph is undirected } // The function to print vertex cover void printVertexCover() { // Initialize all vertices as not visited. boolean visited[] = new boolean [V]; for ( int i= 0 ; i<V; i++) visited[i] = false ; Iterator<Integer> i; // Consider all edges one by one for ( int u= 0 ; u<V; u++) { // An edge is only picked when both visited[u] // and visited[v] are false if (visited[u] == false ) { // Go through all adjacents of u and pick the // first not yet visited vertex (We are basically // picking an edge (u, v) from remaining edges. i = adj[u].iterator(); while (i.hasNext()) { int v = i.next(); if (visited[v] == false ) { // Add the vertices (u, v) to the result // set. We make the vertex u and v visited // so that all edges from/to them would // be ignored visited[v] = true ; visited[u] = true ; break ; } } } } // Print the vertex cover for ( int j= 0 ; j<V; j++) if (visited[j]) System.out.print(j+ " " ); } // Driver method public static void main(String args[]) { // Create a graph given in the above diagram Graph g = new Graph( 7 ); g.addEdge( 0 , 1 ); g.addEdge( 0 , 2 ); g.addEdge( 1 , 3 ); g.addEdge( 3 , 4 ); g.addEdge( 4 , 5 ); g.addEdge( 5 , 6 ); g.printVertexCover(); } } // This code is contributed by Aakash Hasija |
Python3
# Python3 program to print Vertex Cover # of a given undirected graph from collections import defaultdict # This class represents a directed graph # using adjacency list representation class Graph: def __init__( self , vertices): # No. of vertices self .V = vertices # Default dictionary to store graph self .graph = defaultdict( list ) # Function to add an edge to graph def addEdge( self , u, v): self .graph[u].append(v) # The function to print vertex cover def printVertexCover( self ): # Initialize all vertices as not visited. visited = [ False ] * ( self .V) # Consider all edges one by one for u in range ( self .V): # An edge is only picked when # both visited[u] and visited[v] # are false if not visited[u]: # Go through all adjacents of u and # pick the first not yet visited # vertex (We are basically picking # an edge (u, v) from remaining edges. for v in self .graph[u]: if not visited[v]: # Add the vertices (u, v) to the # result set. We make the vertex # u and v visited so that all # edges from/to them would # be ignored visited[v] = True visited[u] = True break # Print the vertex cover for j in range ( self .V): if visited[j]: print (j, end = ' ' ) print () # Driver code # Create a graph given in # the above diagram g = Graph( 7 ) g.addEdge( 0 , 1 ) g.addEdge( 0 , 2 ) g.addEdge( 1 , 3 ) g.addEdge( 3 , 4 ) g.addEdge( 4 , 5 ) g.addEdge( 5 , 6 ) g.printVertexCover() # This code is contributed by Prateek Gupta |
C#
// C# Program to print Vertex // Cover of a given undirected // graph using System; using System.Collections.Generic; // This class represents an // undirected graph using // adjacency list class Graph{ // No. of vertices public int V; // Array of lists for // Adjacency List Representation public List< int > []adj; // Constructor public Graph( int v) { V = v; adj = new List< int >[v]; for ( int i = 0; i < v; ++i) adj[i] = new List< int >(); } //Function to add an edge // into the graph void addEdge( int v, int w) { // Add w to v's list. adj[v].Add(w); //Graph is undirected adj[w].Add(v); } // The function to print // vertex cover void printVertexCover() { // Initialize all vertices // as not visited. bool []visited = new bool [V]; // Consider all edges one // by one for ( int u = 0; u < V; u++) { // An edge is only picked // when both visited[u] // and visited[v] are false if (visited[u] == false ) { // Go through all adjacents // of u and pick the first // not yet visited vertex // (We are basically picking // an edge (u, v) from remaining // edges. foreach ( int i in adj[u]) { int v = i; if (visited[v] == false ) { // Add the vertices (u, v) // to the result set. We // make the vertex u and // v visited so that all // edges from/to them would // be ignored visited[v] = true ; visited[u] = true ; break ; } } } } // Print the vertex cover for ( int j = 0; j < V; j++) if (visited[j]) Console.Write(j + " " ); } // Driver method public static void Main(String []args) { // Create a graph given in // the above diagram Graph g = new Graph(7); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(3, 4); g.addEdge(4, 5); g.addEdge(5, 6); g.printVertexCover(); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript Program to print Vertex // Cover of a given undirected graph // This class represents an undirected // graph using adjacency list class Graph { // Constructor constructor(v) { this .V=v; this .adj = new Array(v); for (let i = 0; i < v; ++i) this .adj[i] = []; } // Function to add an edge into the graph addEdge(v, w) { this .adj[v].push(w); // Add w to v's list. this .adj[w].push(v); //Graph is undirected } // The function to print vertex cover printVertexCover() { // Initialize all vertices as not visited. let visited = new Array( this .V); for (let i = 0; i < this .V; i++) visited[i] = false ; // Consider all edges one by one for (let u = 0; u < this .V; u++) { // An edge is only picked when both visited[u] // and visited[v] are false if (visited[u] == false ) { // Go through all adjacents of u and pick the // first not yet visited vertex (We are basically // picking an edge (u, v) from remaining edges. for (let i = 0; i < this .adj[u].length; i++) { let v = this .adj[u][i]; if (visited[v] == false ) { // Add the vertices (u, v) to the result // set. We make the vertex u and v visited // so that all edges from/to them would // be ignored visited[v] = true ; visited[u] = true ; break ; } } } } // Print the vertex cover for (let j = 0; j < this .V; j++) if (visited[j]) document.write(j+ " " ); } } // Driver method // Create a graph given in the above diagram let g = new Graph(7); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(3, 4); g.addEdge(4, 5); g.addEdge(5, 6); g.printVertexCover(); // This code is contributed by patel2127 </script> |
输出：
0 1 3 4 5 6
上述算法的时间复杂度为O（V+E）。 精确算法： 虽然该问题是NP完全问题，但对于以下类型的图，它可以在多项式时间内求解。 1) 二部图 2) 树形图 如果k以O（LogV）为界，那么检查是否存在小于或等于给定数k的顶点覆盖的问题也可以在多项式时间内解决（参见 这 ) 我们将很快讨论顶点覆盖的精确算法。 本文由 舒巴姆 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
