구사과

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의..