[6기 강남 조유석] Network Flow - Ford-Fulkerson Algorithm

안녕하세요. 강남멤버십 23-1기 조유석입니다.

이번 포스팅에서는 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 유량을 보낼 수 있는지를 계산하는 문제인 Network Flow 를 해결하는 기초적인 알고리즘인 Ford-Fulkerson Algorithm 에 대해 알아보겠습니다.

Network Flow

Network Flow 란 각 간선에 Capacity(용량) 라는 추가 속성이 존재하는 방향 그래프를 말합니다.

정점 u에서 v로 가는 간선의 Capacity 를 c(u, v), 실제 흐르는 유량을 f(u, v) 라고 쓸 때, Network Flow 는 항상 다음 세 가지 속성을 만족해야 합니다.

1. Capacity Constraint(용량 제한 속성): 

각 간선의 유량은 해당 간선의 용량을 초과할 수 없습니다.

2. Skew Symmetry(유량의 대칭성): 

이 속성은 두 정점이 서로 상대에게 보내 주는 것은 의미가 없기 때문에 성립합니다.

① 에서 점선으로 표시된 간선으로 1만큼을 보냄으로써 ② 를 얻을 수 있습니다. 1을 주고 1을 받는 것이기 때문에 서로 상쇄해서 없애 버리면 결과적으로 ③을 얻을 수 있고, 여기에서도 Network Flow의 세 속성은 그대로 성립합니다.

3. Flow Conservation(유량의 보존): 

각 정점에 들어오는 유량과 나가는 유량은 정확히 같아야 합니다.

Ford-Fulkerson Algorithm

Network Flow 문제를 해결하는 가장 기초적인 방법으로 Ford-Fulkerson Algorithm 이 있습니다. Ford-Fulkerson Algorithm 은 최초로 고안된 Network Flow 알고리즘으로 그 개념과 구현이 비교적 간단합니다. 그 과정은 아래와 같습니다.

- Network Flow 의 모든 간선의 유량을 0으로 두고 시작합니다.

- Residual Capacity(잔여 용량) 가 남은 간선들만을 이용해 BFS를 수행해 Augmenting Path(증가 경로) 를 찾습니다.(위 과정의 굵게 표시된 간선이 BFS를 이용해 찾은 Augmenting Path 입니다.)

- Augmenting Path를 통해 흘려보낼 수 있는 유량의 최대량은, 포함된 간선의 Residual Capacity 중 최소로 결정됩니다.

- 각 간선의 유량을 갱신할 때, 유량의 대칭성을 유지하기 위해 한 방향의 유량을 늘리면 다른 방향의 유량은 줄어듭니다.(위 과정의 푸른색으로 표시된 유량을 확인하면 됩니다.)

- Ford-Fulkerson Algorithm 은 이와 같은 Augmenting Path 가 더 이상 존재 하지 않을 때 까지 반복합니다.

Network Flow 는 교통량, 석유량 등 현실 세계에서 자주 볼 수 있는 문제일 뿐만 아니라 그래프와 별 상관이 없어 보이는 다양한 최적화 문제들을 푸는데도 이용할 수 있습니다.

이상으로 Network Flow 와 Ford-Fulkerson Algorithm 에 대해 알아보았습니다.

감사합니다.

Reference

  - ‘프로그래밍 대회에서 배우는 알고리즘 문제해결 전략’ - 구종만 저