그래프 (8) - 최대 유량(최대 유량 최소 컷 정리)

플로우

그래프에서 파생된 개념인 네트워크 유량(Network Flow)에 대해 알아보자. 그래프의 각 간선에는 유량이 흐를 수 있는 값의 제한인 용량(capacity)이 있고, 유량을 발생시키는 정점인 S(source)와 유량이 최종적으로 도착하는 T(sink)가 있을 때, S에서 T까지 이동하는 경로에서 간선의 용량을 넘지 않도록 유량을 적절히 흘려보내는 것이 network flow의 개념이다. 도로의 폭에 따라 출발점에서 도착점까지 화물을 적절히 배송해야 하는 상황이나, 대역폭에 따라 데이터를 나누어 전송하는 상황 등 말 그대로 네트워크에서의 흐름을 계산해야 할 때 이용하는 개념이라고 보면 된다.

 

출처: 위키백과. 일반적으로 현재 유량과 용량을 f/c 형식으로 표현한다.

 

유량에는 다음과 같은 성질이 있다.

• $f(u,v)\leq c(u,v)$
• S, T를 제외한 정점에서 $\sum_{n} f(n,u) = \sum_m f(u,m)$
• $f(u,v) = -f(v,u)$

마지막 성질은 직관적으로 와닿지는 않는데, 최대 유량을 구하는 알고리즘에 필요한 가정이 된다.

 

 

최대 유량 (Ford-Fulkerson, Edmonds-Karp)

최대 유량을 구하는 기본적인 두 가지 알고리즘에 대해 알아보자. 첫 번째는 포드-풀커슨(Ford-Fulkerson) 알고리즘으로, 다음과 같은 원리로 동작한다.

 

1. 유량이 더 흐를 수 있는 간선(즉, $c(u,v)-f(u,v)>0$)들을 대상으로, DFS하여 경로를 찾는다.

2. 찾은 경로로 흘릴 수 있는 유량의 최댓값(한계 유량이라고 부르자)을 찾는다. 이때 한계 유량은 찾은 경로에서 $c(u,v)-f(u,v)$의 최솟값이 된다.

3. 해당 경로로 한계 유량 $f_{max}$을 흘려 주고($f(u,v):= f(u,v)+f_{max}$), 유량의 성질에 따라 반대 방향으로 음의 한계 유량을 흘려 준다($f(v,u):=f(v,u)-f_{max}$). 1으로 돌아가 경로를 더 이상 찾을 수 없을 때까지 반복한다.

 

음의 유량을 흘려 준다는 것이 어떤 의미인지 생각해 보자. 단방향 그래프라면 $c(v,u)=0$이므로 v에서 u로 갈 수 있는 $f_{max}$만큼의 유량 용량을 확보하게 된다. 이는 최대 유량의 해를 찾기 위해, 이전에 찾은 경로에서 흘린 유량을 취소할 수 있게 해주는 역할을 한다. 원래 u->v로 유량 3을 흘렸다가, $f(v,u)=-3$이므로 기존에는 불가능했던 v->u->k 경로로 유량 2를 흘리게 된다면, 두 경로가 (u, v)를 기준으로 swap되면서 총 유량 5를 흘릴 수 있게 된다. u를 기준으로 생각하면 v로 가던 유량 3 중 2를 취소하고 대신 k로 흘려주어, u->v로 흐르는 유량 값은 1이 된다.

 

포드-풀커슨 알고리즘은 한번 DFS할 때마다 유량을 적어도 1만큼 갱신하므로, 최대 유량이 f라 한다면 시간복잡도는 $O((V+E)f) \sim O(Ef)$가 된다. 시간복잡도에서 확인할 수 있듯이 그래프가 크지 않아도 f가 크다면 문제가 생길 수 있다. 이 경우 DFS 대신 BFS를 이용해 정점을 최소로 방문하는 경로를 찾으면 $O(VE^2)$만에 문제를 해결할 수 있다. 이를 에드몬드-카프(Edmonds-Karp) 알고리즘이라 한다.

 

아래는 에드몬드-카프 알고리즘으로 최대 유량을 찾는 코드이다.

def edmonds_karp():
    res = 0

    while 1:
        parents = [-1]*N
        q = deque([S])
        while q and parents[T] == -1:
            u = q.pop()
            for v in adj[u]:
                if capacity[u][v] - flow[u][v] > 0 and parents[v] == -1:
                    q.appendleft(v)
                    parents[v] = u
                    if v == T: break
        if parents[T] == -1: break
        
        f = float('inf')
        v = T
        while v != S:
            u = parents[v]
            f = min(f, capacity[u][v] - flow[u][v])
            v = u
        
        v = T
        while v != S:
            u = parents[v]
            flow[u][v] += f
            flow[v][u] -= f
            v = u

        res += f

    return res

 

 

최대 유량 최소 컷 정리

플로우는 생각보다 정말 다양한 문제에서 활용되는데, 대표적인 사례로 최대 유량 최소 컷 정리(Max-Flow Min-Cut, MFMC)가 있다. 내용은 간단한데, 그래프를 나누기 위해 잘라야 하는 간선의 가중치를 최소로 만드는 문제인 최소 컷(minimum cut)은 최대 유량 과 동일하다는 정리이다.

 

$$ \textrm{flow} \leq \textrm{Max-flow} = \textrm{Min-cut} \leq \textrm{cut} $$

 

병목(bottleneck)으로 그 원리를 직관적으로 이해해 볼 수 있다. 최대 유량의 상황에서 병목인 간선(들)이 존재하기 때문에, 그 간선을 잘라 버리는 것만으로 S에서 T로 유량이 흐를 수 없게 되어 최소 컷의 상황과 동일해진다. 최소 컷으로 나뉜 정점 그룹이나 최소 컷에 해당하는 간선을 구하기 위해서는, 최대 유량의 상황에서 한번 더 탐색하면서 넘어갈 수 없는 정점(간선)을 찾으면 된다.