그래프 관련

그래프 에서

매칭 = 변집합 로, 상호 끝점을 공유하지 않는다.

변 덮개 = 변집합 로, 의 어떤 정점도 적어도 1개의 에 포함된 변에 접속 하고 있다.

안정집합 = 점집합 로, 의 어떤 두점도 에 대해 인접하고 있지 않다.

점 덮개 = 점집합 로, 의 어떤 변도 적어도 1개의 에 포함된 정점에 접속하고 있다.

일때 몇가지 법칙이 성립한다.

1. 고립점이 없는 그래프에서 대해서, |최대매칭| + |최소 변 덮개| = |V|

2. |최대 안정 집합| + |최소 점 덮개| = |V|

특히 이분그래프에서는

|최대 매칭| = |최소 변 덮개| 가 된다.

http://prague.algospot.com/judge/problem/read/TRAPCARD

위 문제가 위의 성질을 이용하여 풀수있는 대표적인 문제이다

이문제는 갯수만 출력하는것이 아니라 그 구체적인 예시까지 출력해야되는 문제인데.

이분그래프에서 minimum vertex cover를 찾는 방법은 다음과 같다.

이분그래프 에서 최소 점덮개(minimum vertex cover)를 라고 하자

이분매칭을 돌리고 나온 그래프에서 residual edge를 따라 갈수있는 정점을 라고 하면

가 된다.