알고리즘(Algorithm) - Network Flow

알고리즘(Algorithm) - Network Flow

1. Minimum Cut Problem / Maximum Flow Problem

다음과 같은 G = (V, E) 그래프가 있을 때,

c(e) : capacity of edge e.(최대로 흘릴 수 있는 물의 양)

cap(A,B) : cut(A,B)로부터 나가는 뱡향의 capacity를 모두 더한 것.

Minimum Cut Problem : capacity가 최소가 되는 s-t cut을 찾는 문제.

s-t flow, f(e) : 실제 흘린 물린 물의 양. 
                            * 0 <= f(c) <= c(e) and 나가는 방향의 모든 f(e) = 들어오는 방향의 모든 f(e)

value of a flow, v(f) : s로부터 나가는 방향의 모든 f(e)를 더한 것.

Maximum Flow Problem : value가 최대가 되는 flow를 찾는 문제.

* 임의의 cut에서 나가는 양 - 들어오는 양 = v(f)

* v(f) <= cap(A,B)

만약 v(f) = cap(A,B)이면, f는 max flow이며 (A,B)는 min cut이다.