顶点覆盖

Table of content
上一个
下一个

顶点覆盖

无向图G = (V, E)的顶点覆盖是顶点的一个子集V' ⊆ V，使得如果边(u, v)是G的一条边，那么u属于V或v属于V'或两者都属于。

在给定的无向图中找到最大大小的顶点覆盖。这个最优顶点覆盖是NP完全问题的优化版本。但是，找到一个接近最优的顶点覆盖并不太难。

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G] 
while E' is not empty do 
   Let (u, v) be an arbitrary edge of E' c ← c U {u, v} 
   Remove from E' every edge incident on either u or v 
return c

示例

给定图的边集为：

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

Set Edges

现在，我们从选择任意边(1,6)开始。我们消除所有与顶点1或6关联的边，并将边(1,6)添加到覆盖中。

Arbitrary Edge

在下一步中，我们随机选择另一条边(2,3)。

Another Edge

现在我们选择另一条边(4,7)。

Select Another Edge

我们选择另一条边(8,5)。

Edge

因此，该图的顶点覆盖为{1,2,4,5}。

分析

很容易看出该算法的运行时间为O(V + E)，使用邻接表来表示E'。

实现

以下是上述方法在各种编程语言中的实现：

C C++ Java Python
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
int graph[MAX_VERTICES][MAX_VERTICES];
bool included[MAX_VERTICES];
// Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm
void approxVertexCover(int vertices, int edges) {
   bool edgesRemaining[MAX_VERTICES][MAX_VERTICES];
   for (int i = 0; i < vertices; i++) {
      for (int j = 0; j < vertices; j++) {
         edgesRemaining[i][j] = graph[i][j];
      }
   }
   while (edges > 0) {
      int u, v;
      for (int i = 0; i < vertices; i++) {
         for (int j = 0; j < vertices; j++) {
            if (edgesRemaining[i][j]) {
               u = i;
               v = j;
               break;
            }
         }
      }
      included[u] = included[v] = true;
      for (int i = 0; i < vertices; i++) {
         edgesRemaining[u][i] = edgesRemaining[i][u] = false;
         edgesRemaining[v][i] = edgesRemaining[i][v] = false;
      }
      edges--;
   }
}
int main() {
   int vertices = 8;
   int edges = 10;
   int edgesData[10][2] = {{1, 6}, {1, 2}, {1, 4}, {2, 3}, {2, 4},
                           {6, 7}, {4, 7}, {7, 8}, {3, 5}, {8, 5}};
   for (int i = 0; i < edges; i++) {
      int u = edgesData[i][0];
      int v = edgesData[i][1];
      graph[u][v] = graph[v][u] = 1;
   }
   approxVertexCover(vertices, edges);
   printf("Vertex Cover: ");
   for (int i = 1; i <= vertices; i++) {
      if (included[i]) {
         printf("%d ", i);
      }
   }
   printf("\n");
   return 0;
}

输出

Vertex Cover: 1 3 4 5 6 7 

#include <iostream>
#include <vector>
using namespace std;
const int MAX_VERTICES = 100;
vector<vector<int>> graph(MAX_VERTICES, vector<int>(MAX_VERTICES, 0));
vector<bool> included(MAX_VERTICES, false);
// Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm
void approxVertexCover(int vertices, int edges) {
   vector<vector<bool>> edgesRemaining(vertices, vector<bool>(vertices, false));
   for (int i = 0; i < vertices; i++) {
      for (int j = 0; j < vertices; j++) {
         edgesRemaining[i][j] = graph[i][j];
      }
   }
   while (edges > 0) {
      int u, v;
      for (int i = 0; i < vertices; i++) {
         for (int j = 0; j < vertices; j++) {
            if (edgesRemaining[i][j]) {
               u = i;
               v = j;
               break;
            }
         }
      }
      included[u] = included[v] = true;
      for (int i = 0; i < vertices; i++) {
         edgesRemaining[u][i] = edgesRemaining[i][u] = false;
         edgesRemaining[v][i] = edgesRemaining[i][v] = false;
      }
      edges--;
   }
}
int main() {
   int vertices = 8;
   int edges = 10;
   int edgesData[10][2] = {{1, 6}, {1, 2}, {1, 4}, {2, 3}, {2, 4},
                           {6, 7}, {4, 7}, {7, 8}, {3, 5}, {8, 5}};
   for (int i = 0; i < edges; i++) {
      int u = edgesData[i][0];
      int v = edgesData[i][1];
      graph[u][v] = graph[v][u] = 1;
   }
   approxVertexCover(vertices, edges);
   cout << "Vertex Cover: ";
   for (int i = 1; i <= vertices; i++) {
      if (included[i]) {
         cout << i << " ";
      }
   }
   cout << endl;
   return 0;
}

输出

Vertex Cover: 1 3 4 5 6 7 

import java.util.Arrays;
public class VertexCoverProblem {
   static final int MAX_VERTICES = 100;
   static int[][] graph = new int[MAX_VERTICES][MAX_VERTICES];
   static boolean[] included = new boolean[MAX_VERTICES];
   // Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm
   static void approxVertexCover(int vertices, int edges) {
      int[][] edgesRemaining = new int[vertices][vertices];
      for (int i = 0; i < vertices; i++) {
         edgesRemaining[i] = Arrays.copyOf(graph[i], vertices);
      }
      while (edges > 0) {
         int u = -1, v = -1;
         for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
               if (edgesRemaining[i][j] == 1) {
                  u = i;
                  v = j;
                  break;
               }
            }
         }
         // Check if there are no more edges remaining
         if (u == -1 || v == -1) {
            break;
         }
         included[u] = included[v] = true;
         for (int i = 0; i < vertices; i++) {
            edgesRemaining[u][i] = edgesRemaining[i][u] = 0;
            edgesRemaining[v][i] = edgesRemaining[i][v] = 0;
         }
         edges--;
      }
   }
public static void main(String[] args) {
   int vertices = 8;
   int edges = 10;
   int[][] edgesData ={{1, 6}, {1, 2}, {1, 4}, {2, 3}, {2, 4},
                       {6, 7}, {4, 7}, {7, 8}, {3, 5}, {8, 5}};
   for (int i = 0; i < edges; i++) {
      int u = edgesData[i][0];
      int v = edgesData[i][1];
      graph[u][v] = graph[v][u] = 1;
   }
   approxVertexCover(vertices, edges);
   System.out.print("Vertex Cover: ");
   for (int i = 1; i <= vertices; i++) {
      if (included[i]) {
         System.out.print(i + " ");
      }
   }
   System.out.println();
   }
}

输出

Vertex Cover: 1 3 4 5 6 7 

MAX_VERTICES = 100
graph = [[0 for _ in range(MAX_VERTICES)] for _ in range(MAX_VERTICES)]
included = [False for _ in range(MAX_VERTICES)]
# Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm
def approx_vertex_cover(vertices, edges):
    edges_remaining = [row[:] for row in graph]
    while edges > 0:
        for i in range(vertices):
            for j in range(vertices):
                if edges_remaining[i][j]:
                    u = i
                    v = j
                    break
        included[u] = included[v] = True
        for i in range(vertices):
            edges_remaining[u][i] = edges_remaining[i][u] = False
            edges_remaining[v][i] = edges_remaining[i][v] = False
        edges -= 1
if __name__ == "__main__":
    vertices = 8
    edges = 10
    edges_data = [(1, 6), (1, 2), (1, 4), (2, 3), (2, 4),
                  (6, 7), (4, 7), (7, 8), (3, 5), (8, 5)]
    for u, v in edges_data:
        graph[u][v] = graph[v][u] = 1
    approx_vertex_cover(vertices, edges)
    print("Vertex Cover:", end=" ")
    for i in range(1, vertices + 1):
        if included[i]:
            print(i, end=" ")
    print()

输出

Vertex Cover: 1 3 4 5 6 7
打印页面
上一个
下一个
广告