네트워크 유량(Network Flow)

1. 개념

그래프의 간선에 거리, 시간이나 가중치, 즉 cost 대신에 용량(capacity)이라는 개념이 추가된다.

이제 두 정점 u, v를 잇는 간선 (u, v)가 있을  때, 정점 u에서 v 방향으로 간선의 용량 이하만큼의 유량(flow)을 흘려보낼 수 있다.

또한, 그래프에 서로 다른 두 정점인 소스(source), 싱크(sink) 정점이 정해지고 소스 정점에서 유량을 발생시켜서 간선들을

통해 싱크 정점에 도달시키는 것이 목표이다. 유량을 발생시킬 수 있는 것은 소스 정점 뿐이고, 그 외의 정점들은 자신이 받은 유량만큼만

다시 흘려보낼 수가 있다.

2. 특징

- 각 간선에 흐르는 유량은 그 간선의 용량을 넘어서는 안 된다.

- 소스와 싱크를 제외한 정점에서는 들어오는 유량 총합과 나가는 유량 총합이 같아야한다.

- 간선(u,v) 방향으로 유량이 흐르고 있다면, 역방향으로는 음의 유량이 그만큼 흐르고 있는 것으로 취급한다.

3. 구현

[1] 포드 풀커슨 알고리즘(Ford-Fulkerson algorithm)

1) S에서 T로 가는 증가 경로(augmenting path)를 아무거나 하나 찾는다. 이때, 증가 경로는 단순 경로이고 경로상의 모든 간선에

   아직 여유 용량(residual)이 남아 있다. 즉, c(u, v) - f(u, v) > 0

2) 증가 경로 중 차단 간선(blocking edge)을 찾는다. 이 간선은 경로상에서 c(u, v) - f(u, v) 값이 최소인 간선이다.

    많아봐야 이만큼만 유량을 더 보낼 수 있을 것이다. 이 값을 F라 하자.

3) 경로상의 모든 간선에 F만큼의 유량을 추가한다. 즉, S에서 T로 이 경로를 따라서 F만큼의 유량을 새로 흘려보낸 것이다.

    경로상의 모든 간선에 대해 f(u, v) += F. 그런데 이 성질을 만족시키기 위해 f(v, u) -= F 또한 행해야 한다.

    역방향으로 상응하는 음의 유량을 흘려주는 것.

이 과정들을 더 이상 증가 경로가 없을 때까지 반복한다. 증가 경로를 찾고, 찾은 경로에 대해 가능한 많은 유량을 흘려보내는 것의 반복이다.

출처 : 네이버 '라이'님 블로그