Overview

도로 교통을 예시로 생각해보자. 고속도로에서는 많은 자동차가 이동할 수 있는 반면, 골목길에서는 비교적 적은 수의 자동차가 이동할 수 있다. 이를 떠올리면 Network Flow를 이해하기 편할 것이다.

Network Flow

Network Flow(네트워크 플로우)는 한 vertex에서 다른 vertex까지 흐를 수 있는 데이터의 최대 크기가 어느 정도인지 확인하는 알고리즘이다.

• 예제 (더 좋은 예시가 있으면 좋겠는데.. 중간고사 문제에서 가져올까?)

용어 정의

• Capacity(용량): 각 edge에서 흐를 수 있는 flow의 최대 ; $c(e)≥0$
• Flow(유량): 각 edge에서 현재 흐르고 있는 데이터의 양 ; $0 ≤ f(e) ≤ c(e)$
• Source: Flow가 시작하는 vertex. source에서 나가는 flow는 되도록 크게 내보낸다.
• Sink: Flow가 도착하는 vertex

Flow graph

Flow graph(플로우 그래프) $G$는 정점 $s$(source)와 $t$(sink)가 있는 directed graph이다.

$f(u,v)$와 $c(u,v)$를 $u$에서 $v$로 가는 edge의 유량과 용량이라고 하자. 다음 세 가지 속성을 만족한다.

• 용량 제한 속성: $f(u,v) ≤ c(u,v)$
• 유량 대칭성: $f(u,v) = -f(v,u)$
• 유량 보존
  • Flow conservation(유량 보존)은 각 vertex에 들어오는 flow와 나가는 flow가 같아야 한다는 원리이다.
  • $s$와 $t$를 제외한 다른 vertex는 flow가 보존된다.

Residual Graph

Residual Graph(잔여 그래프) $G_R$은 남은 capacity를 보여주는 flow graph이다.

• Flow graph $G$: 간선 $e$는 capacity $c$와 flow $f$를 가진다.
• Residual Graph $G_R$: 정방향 간선 $e'$는 capacity $c-f$를 가진다.