頂點覆蓋

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
列印頁面
上一個
下一個
廣告