Algorithm: Network Flow

#개요

          > Network Flow란 노드들과 그들 사이의 에지로 이루어진 흐름을 나타내는 개념

          > 노드들이 출발지와 목적지로 구성되며, 에지들은 용량(capacity)를 가진다

          > 목표: 출발지에서 목적지로 가는 흐름의 양을 최대화/최소화 하는것

 

          > Flow Network란?

                    >> 네트워크 플로우 문제를 모델링하기위한 그래프이다.

                    >> 각 에지에 허용가능한 최대 흐름이 지정되어 있다

                    >> 시작점과 목적지가 지정되어 있어야 한다

                    >> 출발지에서 목적지로 흐르는 실제 흐름량이 나와있다

 

#입력

          > 가중그래프 

          > 에지의 가중치: c(e)

          > 시작점 s: 들어오는 에지 x

          > 도착점 t: 나가는 에지 x

 

#Flow 란?

          > 그래프 G,s,t 가 주어졌을 때, flow f는 각 에지 e에 정수값 f(e)를 다음 조건에 맞추어 할당하는 문제

                    >> 모든 에지 e에 대해 0<= f(e) <= c(e)

                    >> flow f의 값 |f|는 s 에서 나가는 flow 의 총량

                    >> 즉 한 노드에 들어오는 값이 한 노드에서 나가는 양보다 크면 안된다.

          > Maximum Flow: 최대 값을 가지는 flow

 

#Cut 이란?

          > 주어진 노드 V를 두 집합 Vs 와 Vt로 분할

                    >> s는 Vs에, t는 Vt에 들어있다

                    >> Cut X에 대해 f(X)는 X를 지나가는 flow 의 값 총량

                    >> Cut X에 대해 c(X)는 Vs에서 X를 지나 Vt로 가는 에지의 총량

                    >> Cut X 가 주어지면 s에서 t로 가는 flow 의 값은 c(X) 보다 클 수 없다

                              >>> 그렇다면 maximum flow 는 c(X)의 최소값과 같다.

 

#Ford-Fulkerson 알고리즘

          > s 에서 t로 가는 경로를 찾는다(BFS)

                    >> 이때 경로에 포함되는 에지 e는 c(e)>0 이어야 한다. 

          > 위에서 구한 경로를 p 라고 할때, p에 속하는 각 에지 e 마다 c(e)의 최소값을 구해 m 이라 하자

          > p의 각 에지 e 마다 c(e) -= m 으로 갱신

                    >> 이때 e = (u,v)일때, e' = (v,u)에 대해 c(e') = c(e') + m 이다

          > 더이상 할 수 없을떄 까지 반복

 

#Example

다음과 같은 그래프가 있다 가정

 

경로를 BFS로 탐색후 각 경로마다 최소 에지 값을 구해 경로의 모든 에지에 더해준다

          > S - A - D - T 의 경로의 경우 A - D 가 최소 에지 값(8)을 갖는다. 즉

                    >> S - A = 8/10

                    >> A - D = 8/8

                    >> D - T = 8/10

          > S - C - D - T 의 경우 위에서 구한 D - T 경로의 에지가 8 이고 최대 용량은 10 이기에 이 경로에서 최소 에지는 2.

                    >> S - C = 2/10

                    >> C - D = 2/9

                    >> D - T = 10/10

          > S - C - D - A - B - T의 경로를 보면 D - A 는 역방향이다.

                    >> 역방향의 경우 최소값(4)을 더하는 것이 아닌 빼주면 된다. 즉 경로의 값은 다음과 같다

                    >> S - C = 6/10

                    >> C - D = 6/9

                    >> D - A = 4/8 (이전에 A-D = 8 이었다)

                    >> A - B = 4/4

                    >> B - T = 4/10

          > S - A - D - B - T 최소값(2)

                    >> S - A = 10/10

                    >> A - D = 6/8

                    >> D - B = 2/6

                    >> B - T = 6/10

          >S - C - D - B - T 최소값 (3)

                    >> S - C = 9/10

                    >> C - D = 9/9

                    >> D - B = 5/6

                    >> B - T = 9/10

          

 

#Dinitz 알고리즘

          > BFS를 이용해 s 에서 t로 가는 가장 짧은 길이의 모든 경로를 찾는다.

                    >> 이때, 경로에 포함되는 에지 e는 c(e)>0 이어야 한다. 

          > 위에서 찾은 각 경로 p 마다, p에 속하는 각 에지 e 마다, c(e)의 최소값을 구해 이를 m 이라 하자

          > p 의 각 에지 e 마다 c(e) -= m으로 갱신, e = (u,v) 일때 e' = (v,u) 이면, c(e') = c(e') + m