티스토리 뷰

https://en.wikipedia.org/wiki/Karger's_algorithm


그래프에서의 Minimum Cut은 그래프의 컴포넌트를 2개로 쪼개는 데 삭제해야 하는 간선의 개수를 뜻한다. (가중치를 붙여서 일반화한 경우도 있다. 지금 소개하는 알고리즘은 그 경우는 해결하지 못하는 걸로 알고 있음)

이 중 정점 S와 T의 Minimum Cut을 구하는 것은 (즉, S와 T를 서로 다른 컴포넌트로 쪼개는 데 필요한 간선수) 알고리즘이 알려져 있다. (http://amugelab.tistory.com/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) Minimum Cut의 상한이 O(N) 이므로, O(N^3M)에 문제를 해결할 수 있으며, 사실 O(NM^2) 까지의 상한을 보장할 수 있다. (이 증명은 생략) 작동하는 가장 빠른 알고리즘은 O(NM + N^2lgN)에 동작한다.


Karger's Algorithm은 기본적으로 Contraction Algorithm이라는 알고리즘을 여러번 수행함으로써 Minimum Cut을 높은 확률로 구해내는 알고리즘이다. David Karger가 학부생 시절에 만들었다고 한다 (굇수 ㄷㄷ)

Contraction Algorithm에 대해서 설명하자면

 * 1. 아무 에지나 고른다

 * 2. 해당 에지가 잇는 두 정점을 합친다 (다시 말해서 정점 s, t를 정점 (st)로 합치고, s와 t를 잇는 간선을 삭제)

 * 3. 남은 정점의 개수가 2개 초과면 반복한다.

 * 4. 남은 정점의 개수가 2개면, 두 정점을 잇는 간선의 수가 답이다.


정점을 합치는 과정은, 에지 집합을 random shuffle한 후, union-find 자료 구조를 사용하면 O(M) 시간에 가능하다. 이 알고리즘이 답을 맞출 확률은 (1 / nC2)로 상당히 나쁘다. 때문에 Karger's Algorithm에서는 이 알고리즘을 O(N^2lgN)번 실행시킨다. (1 - 1/N^2) ^ (N^2lgN) <= 1 / N 이므로 답을 못 맞출 확률이 1 / N 정도밖에 안되기 때문이다.

고로 이 알고리즘은 1 / N 정도의 확률로 틀리고, O(N^2MlgM)에 동작한다. 하지만 조금의 변형을 가해서 이 상한을 O(N^2lg^3N) 까지 끌어올릴 수 있다고 한다.

신고
댓글
  • 프로필사진 plzrun "정점을 합치는 과정은, 에지 집합을 random shuffle한 후, union-find 자료 구조를 사용하면 O(M) 시간에 가능하다. 이 알고리즘이 답을 맞출 확률은 (1 / nC2)로 상당히 나쁘다. 때문에 Karger's Algorithm에서는 이 알고리즘을 O(N^2lgN)번 실행시킨다. (1 - 1/N^2) ^ (N^2lgN) <= 1 / N 이므로 답을 못 맞출 확률이 1 / N 정도밖에 안되기 때문이다."

    이 부분에서 답을 못 맞출 확률이 1/N^2 보다 작은거지 않나요?
    2016.06.08 11:26 신고
  • 프로필사진 구사과 (1 - 1/x) ^ x <= 1/e (x >= 1, http://www.wolframalpha.com/input/?i=%281-1%2Fx%29^x 급수 참고하세요)
    (1 - 1/x) ^ (x lg x) <= e ^ (-lgx) = 1 / x
    (1 - 1/x) ^ (x lg x) <= 1 / x

    제가 의도한 바는 이것입니다.
    다만 iteration 횟수를 조금 바꾸면 1/n^2의 확률을 만들 수는 있겠네요.
    2016.06.08 19:43 신고
  • 프로필사진 plzrun 아~ 그렇군요! ㅎ
    학교에서 배운건 1/n^2이라 알려줘서 그것만 기억하고 댓글을 남겼던 거였어요.
    아무튼 min-cut이 뭐하는 알고리즘인지 잘 이해가 안되는 부분이 있었는데 정말 도움이 많이 됐습니다ㅎㅎ 감사합니다~!
    2016.06.09 01:50 신고
댓글쓰기 폼
공지사항
Total
79,027
Today
102
Yesterday
209