구사과

(Lecture note is essentially an English version of this post. Slides are used for presentation.) 원 논문 (arxiv) 그래프의 최소 컷 (Minimum cut) 은 그래프를 연결되지 않게 하기 위해서 지워야 하는 간선 가중치의 최소 합이다. 가중치가 없는 경우에, 최소 컷은 그래프의 connectivity 를 정의하는 수량이 된다. 고로 최소 컷은 그래프가 주어졌을 때 계산하고 싶은 가장 기초적인 수량에 해당되며, 응용 예시 또한 무수히 많다. 그래프의 최소 컷을 계산하는 방법은 크게 3가지가 있다. 아래에 해당 방법의 발견 시간 순으로 나열한다. (아래 요약은 이 논문에서 따왔다.) Min-cut Max-flow 접근. Gl..

계산 이론은 전산학의 근간을 이루며, 컴퓨터를 사용하는 모든 학문의 수학적 분석에 있어서 중요한 역할을 한다. 계산 이론 분야의 $P = NP$ 난제는 컴퓨터 과학의 거의 모든 분야를 관통하는 중요한 문제이고. $P = NP$ 난제의 여러 중요한 실용적 의미와 그 악명높음은 이미 대중적으로도 잘 알려져 있다. 계산 이론의 내용은 전산학의 어떠한 부분을 다루더라도 만나게 되는 경우가 많지만, 대부분의 내용은 튜링 머신과 같은 복잡한 개념을 바탕으로 정의된다. 이러한 특징 때문에, 계산 이론의 많은 내용은 잘 알려져 있으면서도 제대로 알고 있는 사람은 그렇게 많지 않은 경우가 많다. NP 시간 복잡도가 Non-Polynomial의 줄임말이라는 유명한 오해가 대표적인 사례이다. 튜링 머신과 같은 개념은 매우 ..

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