flows (1) 썸네일형 리스트형 138. Network Flow 네트워크 플로우(Network Flow)는 그래프 상의 두 정점 사이에 데이터를 얼마나 많이 흘려보낼 수 있는지를 구하는 분야이다. 일반적으로 네트워크를 생략하고 그냥 플로우라고 부르는 경우가 많다. 이제부터 앞에서 간단하게 소개하고 넘어갔던 간선의 용량이 중요하게 다뤄진다. 플로우에서 나오는 용어들의 정의와 특징은 다음과 같다. 정점 $u$에서 정점 $v$로 가는 방향 간선이 존재하고 이 간선의 용량이 $w$일 때, 최대 $w$만큼의 데이터가 이 간선을 따라 정점 $u$에서 정점 $v$로 이동할 수 있다. 정점 $u$에서 정점 $v$로 가는 간선을 통해 이동하는 데이터의 양이 $k$일 때, $k$를 이 간선의 유량(Flow)이라고 한다. 간선의 유량은 간선의 용량을 넘을 수 없다. 데이터를 처음으로 흘.. 이전 1 다음
