Vertex Cover, Independent Set

Vertex Cover : 그래프 G=(V,E)의 정점 집합 중 어떤 부분집합 C를 택하였을 때에, 그래프 상에 존재하는 모든 간선이 C에 속하는 정점과 인접하다면 C를 G의 Vertex Cover라고 한다. 이 때 가능한 C 중 최소 크기의 C를 Minimum Vertex Cover(최소 정점 덮개)라고 한다.

Independent Set : 그래프 G=(V,E)의 정점 집합 중 어떤 부분집합 I를 택하였을 때에, I의 모든 원소가 서로 인접하지 않다면(두 정점을 연결하는 간선이 존재하지 않는다면) 해당 집합 I를 Independent Set이라고 한다. 이 때 가능한 I 중 최대 크기의 I를 Maximum Independent Set(최대 안정 집합)이라고 부른다.

이와 연관하여 알아두면 좋은 사실들을 정리해보면

1. |V| = |Minimum Vertex Cover| + |Maximum Independent Set|

2. 이분 그래프에서는 Minimum Vertex Cover와 Maximum Independent Set을 다항 시간 내에 구할 수 있다. 쾨닉의 정리(Kőnig's Theorem)에 의해 최대 매칭의 크기와 최소 정점 덮개의 크기가 같다.
최소 정점 덮개를 구성하는 정점은 최대 유량이 모두 계산된 유량 네트워크 상에서
- S : Source쪽에 모두 연결된 정점 집합
- T : Sink쪽에 모두 연결된 정점 집합
- L : Source에서 출발하여 residual(이 양수인 간선만을 타고 방문한 정점 집합
- R : Sink에서 출발하여 residual이 양수인 간선만을 타고 방문한 정점 집합
위의 정의를 따르면 (S∩R)∪(T∩L)이다.