====== 최소 컷 (Minimum Cut) ====== * 이제 막 작성 시작한 단계 * https://koosaga.com/192 * undirected 그래프에서 정의되는 것이다. 가중치 없는 그래프, 가중치 있는 그래프 모두 계산 가능 * s-t min cut은 Max flow min cut 정리를 이용해서 플로우로 풀 수 있다 * 글로벌 min cut은 * s-t min cut을 모든 s,t에 대해서 돌리기 : O(V^2)번의 플로우 연산 * Gomory-Hu Tree : O(V)번의 플로우 연산 * [[wp>Karger's Algorithm]] : 랜더마이즈드 알고리즘. unweighted 그래프에서만 가능? * [[wp>Stoer–Wagner algorithm]] : O(V^3) or O(VElogE) * https://justicehui.github.io/hard-algorithm/2019/11/28/global-min-cut/ * https://koosaga.com/192 ===== Global Minimum Cut ===== * 무향그래프에서 최소개의 엣지를 제거해서 그래프를 둘로 나누는 방법을 찾는 문제. weighted 버전은 제거해야 하는 엣지의 가중치의 총합을 최소화하는 문제가 된다. * 크게 세가지 접근 방법이 있다 ([[https://koosaga.com/255]] 참고) * s-t min cut을 모든 s,t에 대해 찾기: * s-t min cut은 max flow를 찾는것과 같은 문제이다. HLPP를 쓴다면 O(V^2*sqrt(E)) 가 걸린다 * 이것을 모든 s,t에 대해 찾아야 한다. 진짜로 그냥 돌리면 O(V^2)번 돌려야 하지만, Gomory-Hu 알고리즘을 쓰면 O(V)번만 돌려도 가능하다. * Gomory-Hu와 HLPP를 같이 써도 O(V^3*sqrt(E)).. 느리다 * Edge contraction 접근 * Karger's algorithm * [[wp>Karger's algorithm]], [[https://koosaga.com/71]] * 이하의 특성으로, Stoer-Wagner Algorithm 에 비해 장점이 없는것 같다. 그래서 굳이 몰라도 될거 같다 * 제약 있음: Unweighted graph에서만 사용 가능하다 * Randomized 알고리즘 -> 오답 확률 있음 * 속도 느림 * 구현 난이도 별차이 없음 * 기본적으로 Randomized 알고리즘이다. 한번 돌리는데에 O(ElogV)인데, 한번 돌려서 정답을 찾을 확률은 매우 낮다. 1/C(V,2) 의 확률. * 그래서 엄청 많이 돌려야 정답을 기대할수 있다. O(V^2logV)번 돌리면 오답률이 1/V 이하로 낮아진다. * O(ElogV)알고리즘을 O(V^2logV)번 돌리려면 O(V^2*E*logV)가 걸린다. Karger–Stein algorithm 은 이것을 발전시켜서 O(V^2*log^3(V))로 속도를 향상시켰다. 하지만 그래도 O(V^3)인 Stoer-Wagner Algorithm에 비해 큰 메리트가 없다. * **Stoger-Wagner 알고리즘** * [[wp>Stoer–Wagner algorithm]], [[https://justicehui.github.io/hard-algorithm/2019/11/28/global-min-cut/]], [[https://koosaga.com/192]] * 간단한 아이디어로 O(V^3) 또는 O(VElogV) 에 글로벌 민컷을 deterministic 하게 찾는다 * 이것을 사용하자 * Tree packing 접근 * [[https://koosaga.com/255]] * Edge-disjoint spanning tree 들에서 컷을 찾아내는 방식인데.. 이론적으로는 이쪽이 가장 빠르다고 한다. PS에서 쓸일은 아직 없어보인다. * State-of-art는 deterministic 알고리즘의 경우, unweighted graph에서는 O(E*log^2(V)*loglog^2(V)), weighted graph에서는 O(VE) 에 동작한다고 한다 ==== Stoger-Wagner 알고리즘 ==== * mincut phase에서 s-t mincut을 찾고, 얻은 s,t를 contraction 하는 작업을 O(V)번 반복한다 * 이렇게 찾아진 mincut 값들중 최소값이 global mincut의 capacity이다 * mincut phase는 프림 알고리즘과 비슷한 방식이라서, O(V^2) 또는 힙을 써서 O(ElogV)에 구현 가능. 그래서 총 시간복잡도는 O(V^3) 또는 O(VElogV)가 된다. * 보통 프림이나 다익스트라는 sparse 한 그래프를 대상으로 돌리는 경우가 많아서, 힙을 쓰는 O(ElogV) 구현이 일반적이다. 하지만 글로벌 민컷 관련해서 백준에 있는 문제들은 대부분 E=O(V^2)인 dense graph이다. 그래서 백준에서 문제를 풀기에는 힙을 안쓰는 구현이 더 유용하다 * mincut에 해당하는 엣지를 찾는 방법 * 보통 mincut의 capacity를 구하는 방법만 설명되어있고, mincut에 해당하는 엣지를 찾는 방법은 안 나와있는 경우도 많아서 찾는데 고생했다. * i번째의 mincut phase에서 구해진 s-t mincut의 용량이 값이 최소용량이었다고 하자. 이때의 t노드와 여태까지 (i-1번째 phase까지) t노드와 컨트랙션 되었던 노드들이 하나의 파티션을 이룬다. 당연히 이 노드들을 제외한 노드들이 다른 파티션을 이룬다. 이제 모든 엣지들 중에서 서로 다른 파티션의 노드들을 연결하는 엣지들만 찾으면 mincut의 엣지들이 된다. * 실제 구현은 i-1번째 phase까지 컨트랙션되는 노드 쌍들을 엣지로 이어서 그래프를 만든 다음에 i번째 phase에서 찾은 t노드와 연결된 노드들을 모두 하나의 파티션으로 두면 된다. 그래프탐색을 해도 되고 Disjoint set을 이용해도 된다. === 구현 및 관련문제 === * s-t민컷 문제와 마찬가지로, 구하는 값은 여러가지가 될수 있다 * 민컷의 캐퍼시티, 민컷에 포함하는 엣지들, 민컷으로 나뉘어진 두 노드 그룹 * 그래서 함수 하나로 만들기 보다는 그냥 클래스로 만들었다. * 캐퍼시티만 구할때는, 그냥 contraction 한 노드쌍들을 리스트에 저장만 해둔다. partition이나 edge들을 구해야 할때는 저장해둔 contraction 히스토리를 Disjoint set으로 재구성해서 partition을 만든다. * O(n^3) 알고리즘이다 보니, 구현 디테일에 따라서 속도 차이가 좀 나는 편이다. 현재 백준에 스토어-바그너 태그로 들어있는 문제는 모두 4개인데, 이것들을 모두 풀기 위해서는 구현을 좀 신경써야 한다.. * [[ps:problems:boj:13367]]: T<20, V<500, E