최소 버텍스 커버(Minimum Vertex Cover)

---

목록

1. 최소 버텍스 커버(Minimum Vertex Cover)란?

2. König's Theorem

3. 최소 버텍스 커버 문제임을 알아채는 방법

---

1. 최소 버텍스 커버(Minimum Vertex Cover)란?

일단 버텍스 커버(Vertex Cover)의 의미를 먼저 보자.

버텍스 커버(Vertex Cover) :: 정점 집합 S가 있을 때, 모든 간선은 양 끝점 중 하나가 S에 포함되어야 한다.

여기서 버텍스 커버는 무엇을 의미할까?

위의 그림은 버텍스 커버의 정의에 맞으므로 버텍스 커버는 A, C, D, E, F, G가 된다.

위의 그림은 버텍스 커버일까?

이 그림은 A-G, G-F를 이어주는 버텍스가 없으므로 버텍스 커버에 해당하지 않는다.

이제 최소 버텍스 커버의 의미를 알아보자.

최소 버텍스 커버(Minimum Vertex Cover) :: 정점 집합 S가 있을 때, 모든 간선은 양 끝점 중 적어도 하나가 S에 포함 되어야 한다.

버텍스 커버의 의미와 최소 버텍스 커버의 의미는 '적어도'라는 말이 있냐 없냐 차이이다.

그렇다면 위의 그래프에서 최소 버텍스 커버는 무엇일까?

위의 그림이 보고있는 그래프에서의 최소 버텍스 커버가 될 것이다.

2. König's Theorem

Wiki :: https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)

한국어 :: http://koosaga.myungwoo.kr/entry/%EC%9C%A0%EB%9F%89-%EA%B4%80%EB%A0%A8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC

쾨닉의 정리에 의하면 최소 버텍스 커버 문제라면 이분 그래프로 해결 할 수 있다는 것이다.

즉, 이분 그래프에서 최대 매칭은 최소 버텍스 커버와 같다는 의미이다.

이 블로그에서는 쾨닉의 정리에 대해 깊게 들어가지 않고, 결론적인 내용으로 바로 접근해 본다.

이 정리를 설명하기 위해 [1867번] 돌멩이 제거 :: http://www.crocus.co.kr/749 문제를 보자.

돌멩이 문제도, 최소 버텍스 커버임을 알 수 있는 내용이 하나의 행 혹은 열을 선택하여 그 방향으로 쭉 밀면되기에

하나의 정점을 선택하여 그래프에서 모든 간선이 적어도 하나의 정점과 연결되게 하면 된다는 것이다.

위 그림의 오른쪽 행렬 그림을 보면 명확하다.

하나의 정점 (1행 정점)을 선택하면 1열, 3열로 가는 간선이 연결되고, 

(2행 정점)을 선택하면 2행, 3행으로 가는 간선이 연결되므로 이분 그래프의 모든 간선과 연결된다는 것이다.

3. 최소 버텍스 커버 문제임을 알아채는 방법

1. 이분 그래프 문제인지 확인해본다.

2. 그래프로 만약 형성된다면 그 그래프에 존재하는 모든 간선이 이용되는지 확인한다.

3. 그 모든 간선이 정점에 적어도 하나가 연결되야 하는지 확인해본다.(정의를 잘 생각하고 이용하면 좋다.)

최소 버텍스 커버 문제 :: http://www.crocus.co.kr/search/%EC%B5%9C%EC%86%8C%20%EB%B2%84%ED%85%8D%EC%8A%A4%20%EC%BB%A4%EB%B2%84