설명
네트워크 유량, 혹은 유량 네트워크(Network Flow, Flow Network)는 각각의 간선에 용량(Capacity)을 가지는 유향 그래프로, 구체적으로는 다음과 같이 정의된다.
- 유량 네트워크(Flow Network) 는 유향 그래프 에서, 각각의 간선 에 용량 가 정의되어, 다음과 같은 성질을 만족한다.
1) 각각의 간선 에 흐를 수 있는 유량은 해당 간선에 정의된 유량 를 넘어갈 수 없다.
2) 유량의 시작점(Source)과 끝점(Sink)을 제외한 모든 노드에서는, 들어온 유량과 나가는 유량이 같아야 된다. (= 오로지 시작점에서만 유량이 뿜어져 나오고, 끝점에서만 유량을 빨아들인다.)
3) 만약 간선 에 만큼의 유량이 흐르고 있다면, 역간선 방향으로 만큼의 유량이 흐르고 있다고 취급한다. 이는 추후 유량 네트워크와 관련된 다양한 문제들을 풀 때 도움이 된다.
위 정의대로, 유량 네트워크를 도식화하면 다음과 같다.
여기서 각 간선에 붙어있는 숫자는 그 간선에 최대로 흐를 수 있는 유량을 나타낸다.
컴퓨터 공학과 이산수학에서의 그래프가 현실 세계에서의 다양한 문제들을 도식화시킬 수 있는 것처럼, 유량 네트워크도 수많은 현실 문제들을 추상화시킬 수 있다. 예를 들어, 각각의 간선 용량을 최대 수용 가능한 교통량이라고 치면 유량 네트워크는 교통망이라고 할 수 있고, 간선 용량을 최대 전송 가능한 데이터량이라고 치면 유량 네트워크는 말 그대로 네트워크망 그 자체라고 할 수 있다.
이와 같이 유량 네트워크는 다양한 방식으로 응용될 수 있는데, 여기서 몇 가지를 먼저 소개해보도록 한다.
최대 유량 알고리즘
위에서 정의한 유량 네트워크에 대해, 각 간선의 용량을 초과하지 않는 선에서 특정 시작 정점에서 끝 정점까지 최대한의 유량을 흘려보내는 최대 유량(Maximal Flow)을 생각할 수 있다. 이 최대 유량을 효율적으로 구하는 알고리즘은 컴퓨터 과학에서 상당히 오랜 기간동안 연구되어 왔는데, 그 간략한 역사는 다음과 같다.
비교적 최근인 2012년까지 개선된 알고리즘이 나온 것을 알 수 있다. 이 중에 유명한 알고리즘 일부를 추후 다룰 것이다.
이분 매칭
그래프 이론에서, 그래프의 매칭(Matching)은 서로 공통된 정점을 가지지 않는 간선들의 집합이다. 이 때, 이분 그래프에서 이러한 매칭을 찾는 문제를 이분 매칭(Bipartite Matching)이라고 하는데, 이분 매칭 문제를 푸는 데 유량 네트워크를 응용할 수 있다.
참고문헌
