Network Flow

Network Flow

물이 사작점에서 끝점으로 흐를 때, 최대 얼마나 많은 물이 흐를 수 있는지 구하는 경우에 사용
물 대신 데이터, 물건 등으로 바꾸어 나오는 문제도 있음

왼쪽 그래프에서 S가 시작점이며 T가 끝점
엣지에서의 숫자는 용량 제한(capacity)를 의미한다. S에서 A로 갈 때는 최대 3의 물이 흐를 수 있고, F에서 T로는 최대 4의 물이 흐를 수 있다.

오른쪽의 그래프는 실제로 물이 흐르고 있는 그림이다. '/' 앞의 숫자가 실제로 흐르는 물의 양을 의미한다.
1/3은 3의 용량 제한 중에 1만큼 물이 흐르고 있다는 뜻이고, 그냥 3은 0/3을 의미한다.

네트워크 플로우가 성립하기 위해서는 3가지 조건을 만족해야만 하는데,
* c(u,v) : capacity의 약자, u에서 v로 가는 간선의 용량
  f(u,v) : flow의 약자, u에서 v로 흐르는 실제 유량

1) 용량 제한 속성 f(u,v) <= c(u,v)
두 간선에서 흐르는 유량은 용량을 넘을 수 없다

2) 유량의 대칭성 f(u,v) = -f(v,u)
u->v로 5가 흐른다면 반대로 v->u로 -5가 흐르는 것과 같다

3) 유량 보존의 법칙
S와 T를 제외하고 각 정점에서 들어오는 유량과 나오는 유량은 일치해야한다

Solution

포드 풀커슨의 알고리즘을 사용하여 해결한다.
1) dfs를 통해 증가경로를 찾고, 찾은 만큼 유량을 흘러보낸다
2) 더 이상 증가경로를 찾을 수 없을 때까지 1번을 반복

좌 : 기본 그래프      우 : 잔여 네트워크

왼쪽 그림이 처음 상태이다. 오른쪽 그림은 왼쪽 그림의 잔여 네트워크이다.
s에서 w로 가는 아크가 1/3이었다. 그렇다면 오른쪽에서는 기존에 흐르던 1을 반대방향으로 바꾸고, 빈공간인 (3-1)2를 원래 방향으로 보낸다. w에서 x로 흐르던 2를 반대방향으로 바꾸고, 빈 공간인 0을 없으므로 생략한다.
또 x에서 t로 흐르는 2/3은, 2는 반대방향으로 바꾸고, 빈 공간인 1을 원래 방향으로 보내준다.

잔여 네트워크에서 s에서 t로 가는 선이 생기는데, 이 경로를 통해서 1만큼 더 보내줄 수 있다는 것을 의미한다.

위 그래프에서 1만큼 늘려주면 아래 그림처럼 된다.

이제 다시 잔여 네트워크를 구하면 오른쪽 그림인 Gf처럼 되는데, 더는 s에서 t로 가는 경로를 찾을 수 없기에 흐름을 늘려줄 곳이 없음을 확인할 수 있다.

따라서 최대 유량은 x->t의 3과 z->t의 1을 합친 4이다.  

Code

(추가해라 꼭 추가해라ㅜㅜㅜㅠ미루지마라ㅜㅜㅠ)

 

Reference

1] https://www.zerocho.com/category/Algorithm/post/5893405b588acb00186d39e0
2] https://m.blog.naver.com/PostView.nhn?blogId=jh20s&logNo=221298145631&proxyReferer=https%3A%2F%2Fwww.google.com%2F