무작위 Min-Cut, Karger 's 알고리즘

Question

Karger 알고리즘을 구현 중입니다. 내가 이해하는 바에 따르면, 마지막 두 노드 사이의 엣지 수가 항상 Min Cut이되는 것은 아닙니다. 내가 이해하는데 어려움을 겪고있는 것은 실제로 어떻게이 알고리즘으로부터 최소 한도를 얻는가입니다. 나는 확률에 관한 많은 것들을 계속 찾고 있지만, 모두 내게 횡설수설처럼 보입니다. ...

내가 읽은 것으로부터, 나는 Karger의 알고리즘을 그래프에 여러 번 실행해야한다고 생각합니다. 이렇게하면 분당 타격 성공 확률이 높아집니다. 제 생각에는 ... ...

누군가가 이것을 더 간단한 방법으로 설명 할 수 있습니까? 이 알고리즘을 실행할 횟수를 찾는 방법은 무엇입니까? 내가 위에서 말한 것이 맞다.

Answer 1

Karger 's 알고리즘을 실행할 때마다 (반 무작위) 커트를 줄 것입니다. 그 커트가 최소 커트 일 확률은 P = 1/(n^2/2 - n/2)입니다. 이것은 커트를 완전히 무작위로 선택하는 것보다 훨씬 낫습니다.

알고리즘을 한 번 실행하면 최소 자르기 가능성은 P이지만받을 가능성은 1 - P입니다. 알고리즘을 두 번 실행하면 min cut을 얻지 못할 확률은 (1 - P) * (1 - P)입니다. 왜냐하면 처음으로 min 커팅을 놓치고 두 번째로 빠뜨려야하기 때문입니다.

꽤 괜찮습니다. 알고리즘을 두 번 실행하면 min cut을 찾을 확률이 높아집니다.

T 번 알고리즘을 실행하면 min cut을 얻지 못할 확률은 (1 - P)^T입니다. 즉, min cut을 얻을 확률은 1 - (1 - P)^T입니다.

이 시점에서 올바른 해결 방법을 얼마나 좋게 생각하십니까? 약간의 확률 (1,000,000에서 1)을 만들어 T를 구하십시오. 알고리즘을 실행해야하는 횟수입니다.

그것은 그것이 당신에게 최소 컷에 대해 추론 할 수있는 훨씬 더 쉽게 공식은 당신이 그런 C 1에 설정 특히,이다 발견하지의 (1/n)^C 기회보다 제공하기 때문에, T = C * (n choose 2) * ln(n)을 설정하는 것이 일반적이다, 당신은 낮은이 그래프의 단일 노드를 무작위로 선택하는 것보다 잘못 잘라낼 가능성이 있습니다. 그래프가 크면 꽤 좋습니다.

요약하면 올바른 대답을 얻는 데 필요한 기준에 따라 C을 선택하십시오. 얼마나 필요한지 잘 모르는 경우 C = 1을 입력하고 알고리즘 (n choose 2) * ln(n) 번을 실행하면됩니다.

(이 수학의 대부분은 the wikipedia page에서 가져온 것입니다. 당신이 자세한 내용은 찾을 수 있습니다)