플로우 알고리즘
이전까지 다룬 그래프 알고리즘에서는 간선에 거리, 가중치 등을 나타내는 cost라는 값이 있었습니다. 네트워크 플로우에는 capacity라는 개념이 추가됩니다.
네트워크 플로우는 네트워크 유량이라고 부르기도 합니다. 핵심이 되는 아이디어는 (u, v)를 연결하는 간선이 있을 때, u에서 v로 용량 이하의 유량을 보낼 수 있다는 것입니다.
네트워크 플로우 관련 알고리즘은 위에서 말한 핵심 아이디어를 기반으로 해서, 시작점(source)에서 도착점(sink)까지 시작점에서 유량을 흘려보내 도착점까지 보내는 것이 목표입니다. 최대한 많이 흘려보내 Max-Flow, 최소한의 비용을 들여서 최대한 많이 흘려보내는 Min-Cost Max-Flow 등 여러 알고리즘이 있고, 몇 개의 글을 통해 하나씩 소개하려고 합니다.
용어/개념 정의
이 글에서는 앞으로 사용할 용어와 개념을 명확하게 정의하겠습니다.
유량 네트워크(flow network)는 간선에 capacity라는 속성이 존재하는 방향 그래프입니다.
u에서 v로 가는 간선 (u, v)의 용량을 c[u][v], 실제로 흐르고 있는 유량을 f[u][v]라고 할 때, 항상 아래 3가지 성질을 만족해야 합니다.
- 용량 제한 속성(f[u][v] <= c[u][v]) : 각 간선의 유량은 용량을 초과할 수 없습니다.
- 유량의 대칭성(f[u][v] = -f[u][v]) : u에서 v로 유량을 x만큼 흘리는 것을 반대로 생각해보면 v에서 u로 -x만큼 유량을 흘리는 것이라 할 수 있습니다.
- 유량의 보존 : source와 sink를 제외한 모든 정점은 각각 들어오는 유량과 나가는 유량은 같아야 합니다.
다음 글에서는 Max-Flow알고리즘에 대해 소개하도록 하겠습니다.