Vertex Cover 알고리즘 설명, 구현 (c언어)

정점 커버(Vertex Cover) 문제란?

 

그래프가 주어지면 그래프의 간선의 양 끝 정점 중 적어도 하나의 정점을 포함하는 정점들의 집합들 중에서 최소 크기의 집합을 찾는 문제이다.

 

조금 더 쉽게 설명하면 그래프가 주어졌을때 가장 많은 edge와 연결된 vertex를 선택하게 된다. 그리고 선택한 vertex는 기록하고, 그 정점과 연결된 모든 간선을 지워나가면서 모든 그래프의 정점과 간선이 사라지도록 동작한다. 그리고 그때 선택된 정점의 개수는 최소가 되어야 한다.

 

예를 들어서 설명하면

그래프 G

위와 같은 그래프가 주어졌을 때 이 그래프의 정점을 커버하는 집합은 {1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1} 이 존재한다.

 

여기서 {2}, {3} 은 그래프 G의 모든 정점을 커버할 수 없다.

 

그리고 이 정점을 커버하는 집합들 중  {1}은 최소 크기의 집합이고, 그래프의 모든 정점과 연결되므로 정점커버 문제의 답이 된다. (위의 그래프에서 1을 선택하면 1과 연결된 간선들이 모든 정점과 연결된다 -> 커버되었다)

 

정점 커버 문제에서는 위와 같이 정점을 선택하여 그래프를 커버하는 방법이 있고 간선을 선택하여 그래프의 정점을 커버하는 방법이 있다.

 

간선을 선택하여 정점을 커버하는 방법은 그래프의 간선을 선택하면 간선의 양쪽 끝 정점들이 가장 많은 간선들과 연결된 간선을 선택하여 그래프 내의 모든 정점을 커버하는 커버 방법이다.

 

위의 사진과 같이 동작하게 된다.

 

그리고 이 글에서는 간선을 선택하여 정점을 커버하는 동작 구현해본다.

 

먼저 자연어로 알고리즘의 구현 방법에 대해서 설명한다.

 

     1. 가장 많은 간선을 가진 정점 찾는다.

     2. 그 정점과 연결된 정점 중 가장 많은 간선을 가진 정점을 찾는다.

     3. 정점 사이의 간선에 커버되는 값들을 갱신 : except_vertex()

     4. 위 과정을 그래프가 모두 커버됐는지 확인하며 반복 : isComplete()

 

여기서 사용할 그래프는 다음과 같다.

구현 코드에서 사용한 그래프

vertex cover algorithm - c language

#include <stdio.h> #include <stdlib.h> #define SIZE 8 // 그래프 초기화 int mat[SIZE][SIZE] = {      {0, 1, 0, 1, 1, 1, 1, 1},     {1, 0, 0, 0, 1, 0, 0, 0},     {0, 0, 0, 0, 1, 1, 0, 0},     {1, 0, 0, 0, 1, 1, 0, 0},     {1, 1, 1, 1, 0, 1, 1, 0},     {1, 0, 1, 1, 1, 0, 1, 1},     {1, 0, 0, 0, 1, 1, 0, 0},     {1, 0, 0, 0, 0, 1, 0, 0}}; // 주어진 간선과 연결된 정점의 간선들에 대한 값 초기화 하는 함수 void except_vertex(int a, int b){     for (int i = 0; i < SIZE; i++) mat[i][a] = mat[a][i] = mat[i][b] = mat[b][i] = 0; } // 모든 정점이 커버됐는지 확인하는 함수 int isComplete() {     for (int i = 0; i < SIZE; i++) {         for (int j = 0; j < SIZE; j++) if (mat[i][j] == 1) { return 0; }     }     return 1; } // vertex cover 함수 void vertex_cover() {     int first, second, max, count; // 1-2 선분     printf("선택된 간선:");     // 1. 가장 많은 간선을 가진 정점 찾는다.     // 2. 그 정점과 연결된 정점 중 가장 많은 간선을 가진 정점을 찾는다.     // 3. 정점 사이의 간선에 커버되는 값들을 갱신 : except_vertex()     // 4. 위 과정을 그래프가 모두 커버됐는지 확인하며 반복 : isComplete()     while (!isComplete()) { // 4.         first = second = max = 0;         // 1.         for (int i = 0; i < SIZE; i++) {             count = 0;             for (int j = 0; j < SIZE; j++)                 if (mat[i][j] == 1) count++;             if (count > max) {                 first = i;                 max = count;             }         }         // 2.         max = 0;         for (int i = 0; i < SIZE; i++) {             if (mat[i][first] != 1) continue;             count = 0;             for (int j = 0; j < SIZE; j++)                 if (mat[i][j] == 1) count++;             if (count > max) {                 second = i;                 max = count;             }         }         printf(" %d-%d",first+1,second+1); // 선택된 간선 출력         // 3.         except_vertex(first, second);     }     printf("\n"); } int main() {     vertex_cover(); // 1-2 간선을 시작 간선으로 선택     return 0; }

위의 코드를 동작시킨 결과

결과

인접 행렬 방식을 사용하여 구현