네트워크 흐름

그래프 이론에서 네트워크 흐름(Network flow)이란 각각의 변(edge)에 정해진 용량(capacity)보다 작은 흐름(flow)이 주어진 방향 그래프를 말한다. 네트워크 흐름에서 각 꼭짓점(node)은 날꼭짓점 (source node), 들꼭짓점(sink node)과 이 둘을 제외한 나머지 꼭짓점으로 구분될 수 있다. 날꼭짓점과 들꼭짓점을 제외한 모든 꼭짓점에서는 해당 꼭짓점에 들어오는 흐름의 총합과 나가는 흐름의 총합이 같아야한다는 성질이 있다. 이러한 네트워크 흐름은 도로망의 교통 흐름을 분석하거나 전자 회로의 전류, 파이프를 흐르는 유체등 네트워크를 통해 묘사될 수 있는 다양한 대상들의 특성을 연구하는데 사용된다.