[1. 개요]
그래프에서 간선에는 가중치라는 개념이 있다.
여기서 가중치 대신 용량이라는 개념을 적용하여, 일종의 파이프라고 모델링을 하고
이 간선을 통해 물을 흘려보낸다고 하자.
출발지에서 목적지까지 물을 흘려보낸다고 했을 때, 이 간선에 흐르는 양을 유량이라고 부를 수 있다.
이렇게, 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 흐름 혹은 유량을 보낼 수 있는지
계산하는 문제를 네트워크 용량 문제라고 한다.
[2. 유량 네트워크]
각 간선에 용량(Capacity) 라는 추가 속성이 존재하는 방향 그래프를 말한다.
이 간선을 통해 유량을 흘려 보낼 수 있다
정점 u 에서 정점 v 로 가는 간선에 대해서 아래와 같이 표기하도록 한다.
- 용량: c(u, v), capacity
- 유량: f(u, v), flow
이 때, 네트워크의 유량은 항상 다음 세가지 속성을 만족한다.
- 용량 제한 속성
# 자명한 속성, f <= c 를 항상 만족해야 한다. - 유량의 대칭성
# f(u, v) = -f(v, u)
# u -> v 로 유량을 보내는 것은 v -> u 로 음수 유량을 보내는 것과 같다. - 유량의 보존
# 정점에 들어오는 유량과 나가는 유량의 양은 정확히 같다.
# 모두 더하면 0 이다.
# 유량의 대칭성으로 인해, 들어오는 유량은 음수 유량으로 표현 할 수 있다.
유량 네트워크에는 유량의 보존 속성이 성립하지 않는 특별한 두 정점이 있다.
- Source (소스) => 유량이 시작되는 정점
- Sink (싱크) => 유량이 도착하는 정점
다른 모든 정점에서 유량의 보존 속성이 성립해야 하므로,
소스에서 나온 모든 유량을 결국 싱크로 들어가게 된다.
소스와 싱크 사이에 흐를 수 있는 최대 유량을 계산 하는 문제가 네트워크 유량 문제이다.
[3. 포드-풀커슨 알고리즘]
네트워크 유량 문제를 해결하는 가장 기초적인 방법으로, 몇 가지 개념을 먼저 정리하면,
- 유량을 보내는 경로를 증가경로 라고 부른다.
- 간선의 용량과 현재 이 간선에 흐르고 있는 유량의 차이를 잔여 용량 이라 한다.
# r(u, v) = c(u, v) - f(u, v) - 증가 경로를 통해 보낼 수 있는 유량의 최대량은 포함된 간선의 잔여 용량 중 가장 작은 값으로 결정된다.
# 대역폭 같은 개념이다.
포드-풀커슨 알고리즘은 증가 경로가 존재하지 않을 때 까지 증가 경로를 찾고,
보낼 수 있는 최대 유량을 해당 경로를 따라 보내는 작업을 반복한다.
시간 복잡도
최대 유량이 f 이고, Edge 개수가 |E| 일 때,
min(O(|E|f), O(|V||E|2) 이다.
- bfs 를 이용하는 경우, bfs 의 시간복잡도 O(|V| + |E|) =>
=> 그래프를 인접 행렬로 구현하면...
[4. 최소 컷 최대 유량 정리]
포드-풀커슨 알고리즘의 정당성을 증명 할 때 필요한 개념이다.
컷 (Cut) 이라는 개념은 아래와 같다.
유량 네트워크에서 컷이란,
소스와 싱크가 각각 다른 집합에 속하도록
그래프의 정점들을 두개의 집합으로 나눈 것이다.
- 소스가 집합 S 에 속하고, 싱크가 집합 T 에 속하도록 정점들을 두 집합으로 나누었을 때,
- S -> T 로 가는 간선들의 용량들의 합 => "컷 S,T 의 용량"
- S -> T 로 실제로 보내는 총 유량 => "컷 S,T 의 유량"
# T 에서 S 로 흘러오는 유량은 음수로 취해서 더해야 한다.
# 유량의 대칭성을 이용한다.
한편, 유량 네트워크에서 모든 컷의 유량과 용량에는 다음 두 속성이 항상 성립한다.
- 컷의 유량은 소스에서 싱크로 가는 총 유량과 같다.
# 유량의 일부가 S 와 T 를 여러 번 오가는 경우에도, 유량의 대칭성 때문에
# 컷의 유량에는 한 번만 포함된다. - 컷의 유량은 용량과 같거나 더 작다.
즉, 모든 컷 (그래프에서 발생 할 수 있는 두 정점 집합 S 와 T) 의 유량은 같고,
어떤 컷에서라도 용량은 유량 이상의 값이 된다.
여기서, 용량이 가장 작은 컷을 찾아내는 것이 최소 컷 문제이다.
- 컷의 용량을 최소로 만들도록 해야 한다.
이 최소 컷을 통해 포드-풀커슨 알고리즘의 정당성을 증명 할 수 있다.
- 용량과 유량이 같은 컷 S`, T` 이 존재한다고 가정한다.
- S`, T` 보다 용량이 작은 컷이 존재한다면 => 유량이 용량보다 크므로 모순
# 최초 가정에서 용량과 유량이 같다고 하였다.
# 유량은 바뀌지 않았는데, 용량이 작아졌으므로, 유량이 용량보다 더 커졌다. - S`, T` 보다 많은 유량을 보내는 방법이 있다면 => 유량이 용량보다 크므로 모순
# 이번에는 용량은 그대로 인데, 유량이 커졌다. - ======
- 최소 용량 최대 유량 정리는 (용량은 최소이면서, 유량은 최대가 되도록 하려면)
# 증가 경로가 존재하지 않는 유량 네트워크에서 용량과 유량이 같은 컷을 찾아내면 된다.
# 소스에서 잔여 용량이 있는 간선을 통해 갈 수 있는 정점들의 집합 S 와
# 그럴 수 없는 정점들의 집합 T 로
# 그래프의 속한 정점을 두 집합으로 나누는 것이다.
# 여기서 소스는 항상 S 에 속하고, 싱크는 항상 T 에 속한다.
# 그리고, S 에 속한 정점에서 T 에 속한 정점으로 가는 모든 간선의 잔여 용량은 0 이다.
# 잔여 용량이 있다면, 이 정점 또한 S 에 속해야 하기 때문이다.
# 즉, 모든 간선에 대해 용량과 유량이 같게 된다. => (용량은 최소, 유량은 최대)
# 또한 증가 경로 역시 존재하지 않는다. - 위에서 포드-풀커슨 알고리즘은 증가경로가 존재하지 않을 때 종료하므로,
- 위 정리를 통해 정당성을 증명 할 수 있다.
[5. 구현 - 인접행렬]
