최소 절단 알고리즘을 알기 위해서는 절단이라고 불리는 개념을 생각해야 한다.
절단(cut)란 네트워크를 정확히 두래로 쪼개는 것을 의미한다.
문제의 입력으로 시작점 s와 종점 t 가 들어 오기 때문에 우리는 둘로 쪼개는 여러 방법 중에 한쪽에는 s에 속하고 다른쪽엔느 t에 속하도록 하는 절단만을 고려한다.
이것을 s-t절단 이라고 부르는데 이 글에서는 다른 절단에 대해서는 고려하지 않기 때문에 절단이란 s-t 절단을 가르킨다고 생각한다.
그래프 절단이란 어떤 정점 집합 S ⊆ V 에 대해서 s ∈ S 이고 t ∈ V\S 일 때 (S,V\S) 처럼 나타내며 S로부터 나가는 변의 집합을 말한다.
또한 그 용량의 합을 절단의 용량이라고 말하며 절단에 포함된 변을 모두 제거하면 s에서 t까지의 경로가 존재하지 않는다.
따라서 다음과 같은 문제를 생각할 수 있다.
네트워크에 대해서 s에서 t로의 경로가 존재하지 않게 하기 위해 제거해야 하는 변의 용량의 합의 최소 값은 무엇인가?
이 문제는 최소 절단 문제라고 하는데 최대흐름 문제와 상당히 관계가 깊다.
https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Max-flow min-cut theorem - Wikipedia
From Wikipedia, the free encyclopedia Concept in optimization theory In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the tot
en.wikipedia.org
위의 링크에서 최대 흐름과 최소 컷에 대한 정리를 살펴 볼 수 있다.
위의 그림을 최대 흐름으로 표현을 해 보면 다음과 같다.
f/c 형식의 각 화살표
여기서 f/c 라는 라벨이 붙어 있고 f는 모서리 위의 흐름이고 c는 모서리 용량이다.
여기서 유량값은 11이다. 따라서 용량 11의 위치를 잘라주면 잘라 주면 최소 컷이 된다.
따라서 흐름의 값은 컷의 용량과 동일하며 이는 흐름의 최대 흐름이고 이 컷이 최소 컷임을 나타낸다.
최소절단 문제임을 알아내는 방법 : s에서 t로 가는 것을 막으려고 하는 경우 최소절단 문제로 생각할 수 있다.
'강의자료 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 모스알고리즘(Mo's algorithm) (21) | 2023.12.15 |
|---|---|
| [알고리즘] 제곱근 분할법(Sqrt Decomposition) (23) | 2023.12.05 |
| inchworm 알고리즘 (29) | 2023.11.13 |
| 기하알고리즘] 회전하는 캘리퍼스 (28) | 2023.11.01 |
| [알고리즘]다익스트라(Dijkstra) 알고리즘 (9) | 2023.03.16 |