서론

네트워크 플로우(Network Flow) 알고리즘은 네트워크 내에서 한 지점에서 다른 지점으로 가능한 최대의 ‘유량(flow)’을 찾는 문제를 해결하기 위해 사용됩니다. 여기서 말하는 ‘네트워크’는 간선(edge)들이 정점(vertex)들을 연결하는 그래프로, 각 간선에는 그 간선을 통해 흘러갈 수 있는 최대 흐름의 양(capacity)이 할당되어 있습니다. 네트워크 플로우 문제는 다양한 형태로 나타날 수 있으나, 가장 기본적인 형태는 소스(source)에서 싱크(sink)로의 최대 유량을 찾는 문제입니다.

정의

유량 네트워크(flow network)란 각 간선에 용량(capacity)이라는 속성이 존재한는 방향 그래프.

정점 u에서 v로 가는 간선의 용량을 c(u,v), 실제 흐르는 유량을 f(u,v)라고 할 때 네트워크 유량은 항상 다음 세 가지 속성을 만족해야 한다.

  • 용량 제한 속성 f(u, v) <= c(u,v) : 각 간선의 유량은 해당 간선의 용량을 초과할 수 없다.
  • 유량의 대칭성 f(u, v) = -f(u, v): u 에서 v로 유량이 흘러올 경우, v의 입장에서는 u로 음수의 유량을 보내는 것과 같다.
  • 유량의 보존 : 각 정점에 들어오는 유량과 나가는 유량의 양은 정확히 같아야 한다. (source,sink 제외)

유량 네트워크 에서는 특수한 두 정점 소스(source)와 싱크(sink)가 존재한다. 소스는 유량이 시작되는 정점이고, 싱크는 유량이 도착하는 정점이다. 따라서 이 두 정점에 대해서 유량의 보존 속성은 성립하지 않는다.

포드-풀커슨 알고리즘(Ford-Fulkerson algorithm)

포드-풀커슨 알고리즘은 유량 네트워크의 모든 간선의 유량을 0으로 두고 시작해서, source에서 sink로 유량을 더 보낼 수 있는 경로를 찾아 유량을 보내기를 반복한다.

그림으로 보자.
image

최대 유량을 나타내는 flow 변수를 0으로 하고 잔여그래프 G 을 G로 초기화 한다. while 잔여그래프 G에서 s-t 패스 P가 존재한다면 P에 포함된 변의 용량 중 최솟값인 f를 흘려보낸다 flow+=f 패스 P 위에 f를 흐르게함 잔여그래프 G` 갱신

참고자료

알고리즘 문제 해결 전략(구종만)
문제 해결력을 높이는 알고리즘과 자료 구조(오츠키 켄스케)