Flows in Networks

• digraph $G = (V,E)$, source and sink $s, t \in V$
• capacities $c_e >0$
• Flow: variable $f_e$ per edge
  • $0 ≤ f_e ≤ c_e$
  • conservation: $\Sigma {(w,u)\in E} f{wu}$ = $\Sigma {(u,z)\in E} f{uz}$ 즉 한 노드에 들어오고 나오는 flow의 합은 같아야 함!!
• Maximize:
  • size(f) = $\Sigma_ {(w,u)\in E} f_{wu}$

Solve with simplex method

1. Start with Zero flow
2. choose appropriate path from s to t increase flow along the edges in the path, as much as possible

• 잘 보면 방향만 바꾸면 성립하는 path들이 있다 (빨간색)

• 이런 path를 고려하자! residual Graph $G^f = (V, E^f)$

  

Example

edge마다의 capacity가 주어져 있다.

유효한 아무 path나 골라서 추가한다. residual graph에서 정방향의 c를 감소, 역방향의 c를 증가시킨다.

더이상의 s→t path가 존재하지 않는다. 알고리즘 종료 (Ford-Fulkerson alg.)