알고리즘에서 '네트워크 플로우(Network Flow)' 문제와 '최대 유량(Max Flow)'이란?

해설

네트워크 플로우는 방향 그래프에서 각 간선에 용량(capacity)이 주어졌을 때, 소스(시작점)에서 싱크(도착점)로 보낼 수 있는 최대 유량을 구하는 문제입니다. 포드-풀커슨, 에드몬즈-카프 등의 알고리즘으로 풀며, 이분 매칭, 최소 컷 등의 문제와 연관됩니다.