zasxer   4달 전

minimum vertex cover 문제 격자판을 풀고 있는데, 헝가리안 알고리즘을 써서 정점을 커버하기 위한 최소 간선을 찾아내는 것은 알겠는데, 최소 정점 커버를 구하는 것을 모르겠네요. 최소 정점 커버를 구하는 방법이 있나요? 해설을 보니 헝가리안 알고리즘을 활용하여 bfs로 간단하게 구현 가능하다는데, 제가 찾아본 풀이 외 다른 풀이로는 최대독립집합으로 사용하라고 하기도 합니다. 어떻게 풀어야 할까요? 헝가리안 알고리즘을 활용하여 bfs로 풀라고 하시면 bfs를 정확하게 어떤 식으로 코드를 작성해야 할까요?

appa   3달 전

해당 문제는 이분 그래프로 모델링 가능하며 그래프의 왼쪽 부분을 S, 오른쪽 부분을 T라고 하겠습니다.

소스 정점(시작점)에서 residual(capacity - flow)이 양수인 방향으로 방문 가능한 모든 정점 집합을 R이라고 하겠습니다.

R과 S의 교집합을 집합 A라고 하겠습니다.

R의 여집합과 T의 교집합을 집합 B라고 하겠습니다.

집합 A와 집합 B의 원소들이 결국 이분 그래프의 cut이 되며, 그 원소의 개수가 최대유량과 같고 쾨닉의 정리에 의해 minimum vertex cover가 됩니다.

해당 문제에서는 R + C = K인 해를 출력하라고 했기 때문에,

|A|+|B| < K인 경우 S의 원소 중 집합 A에 포함되지 않은 원소들 중 K - |A| - |B|개를 A에 강제로 넣어주시면 됩니다.

만약 |A|+|B| > K이면 min cut의 크기가 K보다 크기 때문에 해당 모델링된 그래프에서는 만족하는 해를 찾을 수 없게 되구요.

appa   3달 전

헝가리안 메소드는 1:1 가중치 매칭에서 최소 가중치의 합을 찾는 알고리즘인데, 이는 maximum flow 알고리즘과는 다른 개념이며,

저는 선택된 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 가장 큰 숫자의 최솟값에 대해 이분탐색하면서 그래프를 remodeling하여 정한 답에 대해 최대유량알고리즘으로 가능한 지를 확인하는 풀이를 말씀드렸습니다.

zasxer   3달 전

답변 감사합니다.

궁금한 점이 하나 있는데 혹시 이분 그래프에서 가중치가 1이라면 헝가리안 메소드의 답과 maximum flow의 답이 같나요?

appa   3달 전

네, 그런데 소 잡는 칼로 닭 잡는 격이라 비추천합니다.

zasxer   3달 전

가중치가 1일때만 가능한 거죠???

appa   3달 전

아마도 저 문제에 적용시키기 위해서는 R+C=K인 조건 때문에 가중치가 1이어야하지않을까요.

원래 헝가리안 메소드 자체는 양의 가중치이면 항상 사용가능합니다.

zasxer   3달 전

감사합니다!

zasxer   2달 전

appa님 단절점을 양방향 그래프가 아닌 단방향 그래프에서도 찾는 방법이 있나요?

댓글을 작성하려면 로그인해야 합니다.