제 4회 (3주차) 모각코 결과
4회차 (3주차) - 그리디 문제 풀어보기 (수정) 최소 버택스 커버에 대해 공부, 응용 문제 풀기
최소 버택스 커버...?
최소 버택스 커버란 그래프와 간선이 있을 때, 간선의 양쪽 노드 중 한개는 적어도 S집합에 있어야 할 때, S집합에 포함 해야 하는 노드를 최소한으로 정하는 것이다.
이 최소 버택스 커버를 찾기 위해서는 최대유량으로 접근하여야 한다. 해당 내용은 쾨닉의 정리에 해당하는데, 아직 이해하지 못했다.
그래프에서 최소 버택스 커버를 찾을려면 일반적인 그래프에서는 다항 시간내에 문제를 해결 할 수 없다. 하지만 이분그래프의 경우라면, 최대 유량 알고리즘을 이용하여, 다항 시간내에 문제를 해결 할 수 있다.
최소 버택스의 개수는 최대 매칭의 개수랑 동일 하다. 이것 또한 쾨닉의 정리의 일부이다.
최소 버택스를 역추적 하여 발견하기 위해서는 증명을 이해해야 하는데, 아직 이해하지 못했다.
위 백준 문제는 단순히 매칭의 개수를 세어보면 되는 간단한 문제였다.
최소 버텍스 커버를 구한다... 내가 이해한 최소 버텍스 커버를 구하는 방법이다.
주어진 그래프에서 임의로 최대 매칭을 시키면 오른쪽 그림과 같이 된다.
여기서 최소 벌텍스를 구하는 방법이 여러가지 경우가 있지만, 나는 내가 이해하여 푼 방법을 순서대로 나열하려 한다.
이해를 명확하게 한 게 아니라서 정확한 증명은 아니다.
우선 매칭 된 빨간색 선분에 해당하는 왼쪽 노드나 오른쪽 노드에서 최소 벌텍스가 될 수 있는 노드가 존재하고, 존재해야만 한다.
또한, 매칭 된 모든 왼쪽 노드는 최소 벌텍스가 될 수 있다고 가정하고 시작한다.
1. 왼쪽 노드에서 매칭 되지 않은 임의의 노드에 대해서 그 노드가 가르키는 점은 매칭이 되어야 하는 점이다.
왜냐하면 매칭 되지 않았다는 것은, 그 오른쪽 노드를 가르키는 임의의 노드가 왼쪽에서 이미 존재한다는 뜻이다. 그럼 그 왼쪽 노드를 최소 벌텍스로 고르는 것보다는 오른쪽 노드를 최소 벌텍스로 골라야 임의의 매칭되지 않은 왼쪽 노드에 대해, 오른쪽 노드가 간선을 포함하고 있다고 보장 할 수 있다.
2. 오른쪽 노드랑 매칭 되고 있던 왼쪽 노드에 대해, 1번을 다시 실행한다.
그에 해당하는 왼쪽 노드는 이미 오른쪽 노드가 최소 벌텍스로 선택됨에 따라, 왼쪽노드는 최소 벌텍스가 될 수 없게 되었다. 그럼 최소 벌텍스가 아닌 왼쪽 노드에 대해 왼쪽 노드가 가르키는 모든 오른쪽 노드 중 이미 짝지어진 오른쪽 노드는 최소 벌텍스가 되어야 한다.
정확한 증명은 최소 컷의 개념으로 해야하는데, 이해하지 못했다.
이 방법이 왜 맞는지도 잘 모른다.
이해가 너무 어려워, 일단 이렇게 풀었다. 쾨닉의 정리를 계속 읽고 정확한 수학적 이해를 해 볼 예정이다.
댓글
댓글 쓰기