티스토리 뷰
네트워크 유량(Network Flow)은 네트워크 플로우라고도 불리며 이를 설명하기 전,
유량 그래프(Flow Graph)에 대해서 먼저 알아봅시다.
유량 그래프란 각 간선에 용량이라는 추가 속성이 존재하는 방향 그래프로
각 간선은 유량을 흘려보낼 수 있는 파이프 역할을 합니다.
이 그래프에서는 소스(Source)와 싱크(sink)가 존재하며
소스는 유량이 시작되는 정점, 싱크는 유량이 도착하는 정점을 뜻합니다.
유량 그래프에서는 아래와 같은 3가지의 속성을 만족합니다.
1. 용량 제한 속성 : 각 간선의 유량은 해당 간선의 용량을 초과할 수 없다.
2. 유량의 대칭성 : u에서 에서 v로 유량이 들어올 경우 v입장에서는 u로 음수의 유량을 보내는 것과 같다.
3. 유량의 보존 : 소스와 싱크를 제외하고 각 정점에 들어오는 유량과 나가는 유량의 양은 같다.
이러한 유량 그래프에서 소스와 싱크 사이에 흐를 수 있는 최대 유량을 구하는 문제를 네트워크 유량 문제라고 말합니다.
이 문제를 풀기 위하여 네트워크 유량의 기본 알고리즘인 포드-풀커슨(ford-Fulkerson) 알고리즘을 사용합니다.
(추후 더 빠른 디닉 알고리즘에 관하여 설명합니다.)
동작원리는 아래와 같습니다.
1. 소스에서 싱크로 가는 경로 중 c(u, v) - f(u, v) > 0인 증가 경로를 아무거나 찾는다.
2. 찾은 증가 경로 상에서 c(u, v) - f(u, v) 값이 최소인 값을 찾는다.
3. 찾은 증가 경로 상의 모든 간선에 그 만큼의 유량을 추가한다.
4. 더 이상 증가 경로가 없을 때까지 반복한다.
이 때 증가 경로를 BFS로 탐색하여 포드-풀커슨 알고리즘의 단점을 없애면
시간복잡도는 정점 개수가 V 간선 개수가 E이며 문제의 답이 f일 때 min(O(Ef), O(VE^2))입니다.
유량 그래프의 정의는 방향 그래프이지만 양쪽 용량을 같은 값으로 초기화 해주면 방향이 없는 그래프에서도 가능하며
정점을 한 번만 거쳐서 싱크에 도달하고 싶은 경우 정점을 2개의 정점으로 나눈 뒤
사이에 있는 간선의 용량을 1로 하여 유량을 흐르게 할 수 있습니다.
이렇듯 여러 응용이 존재하며 네트워크 유량 문제인 지 숨기는 경우가 많아
다양한 유형의 문제와 유량 그래프를 그리는 연습이 필요합니다.
기본 문제
