138. Network Flow

네트워크 플로우(Network Flow)는 그래프 상의 두 정점 사이에 데이터를 얼마나 많이 흘려보낼 수 있는지를 구하는 분야이다. 일반적으로 네트워크를 생략하고 그냥 플로우라고 부르는 경우가 많다. 이제부터 앞에서 간단하게 소개하고 넘어갔던 간선의 용량이 중요하게 다뤄진다. 플로우에서 나오는 용어들의 정의와 특징은 다음과 같다.

• 정점 $u$에서 정점 $v$로 가는 방향 간선이 존재하고 이 간선의 용량이 $w$일 때, 최대 $w$만큼의 데이터가 이 간선을 따라 정점 $u$에서 정점 $v$로 이동할 수 있다.
• 정점 $u$에서 정점 $v$로 가는 간선을 통해 이동하는 데이터의 양이 $k$일 때, $k$를 이 간선의 유량(Flow)이라고 한다. 간선의 유량은 간선의 용량을 넘을 수 없다.
• 데이터를 처음으로 흘려보내는 정점을 소스(Source), 데이터가 최종적으로 도달하는 정점을 싱크(Sink)라고 한다.
• 용량이 존재하는 간선들과 소스, 싱크 및 정점들로 구성된 그래프를 유량 그래프(Flow Network)라고 한다.
• 정점 $u$에서 정점 $v$로 가는 방향 간선의 용량이 $w$일 때, 정점 $v$에서 정점 $u$로 가는 용량 $0$의 간선이 존재한다고 가정할 수 있다. 이런 간선들의 유량은 음수가 될 수 있다.
• 정점 $u$에서 정점 $v$로 $k$만큼의 데이터를 흘려보냈을 경우 정점 $v$에서 정점 $u$로는 $-k$만큼의 데이터를 흘려보낸 것으로 간주한다.
• 소스를 제외한 모든 정점은 다른 정점이 자신에게 흘려보낸 양 이하의 데이터를 다른 정점으로 흘려보낼 수 있다.
• 소스와 싱크를 제외한 각 정점에서는 들어오는 데이터의 총합과 나가는 데이터의 총합은 같아야 한다.

플로우에서 해결해야 하는 문제는 소스에서 싱크로 얼마나 많은 데이터를 흘려보낼 수 있는지이며, 이 문제를 해결하기 위해 다양한 알고리즘이 개발되었고 특수한 형태의 그래프에서 작동하는 변형된 버전도 많이 존재한다. 이것들을 하나씩 살펴보기로 한다.

 

→ solved.ac tag: flow