26. Maximum Flow

최대 유량 문제에서는 간선의 유량 제한을 넘지 않고 소스에서 싱크로 얼마만큼의 유량을 보낼 수 있는지를 계산한다.

26.1. Flow networks

유량 망의 그래프 이론적 정의를 알아보자.

Flow networks and flows

유량 망 G = (V, E)는 각 간선이 용량 c(u, v) \geq 0을 갖고 있는 방향그래프로, 각 간선에 대해 반대 방향 간선이 존재하지 않는다. 간선이 없다면 c(u, v) = 0이라 하고, 자가 루프는 허용하지 않는다. 또한 특별한 두 정점인 소스 s와 싱크 t가 존재하여 각 정점 v에 대해 경로 s \to v \to t가 존재한다. 따라서 그래프는 연결그래프이며 소스를 제외한 모든 정점에는 그 정점으로 들어가는 간선이 존재한다. 이 때 유량은 다음 조건을 만족한다.

0 \leq f(u, v) \leq c(u, v)

모든 u \in V - \{s, t\}에 대해 \sum_{v \in V} f(v, u) = \sum_{v in V} f(u, v).

이 때 유량의 \lvert f \rvert = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s)로 정의한다. 최대 유량 문제에서는 소스와 싱크가 주어졌을 때 최대 유량을 찾는 것이다.

An example of flow

유량 망으로 모델링할 수 있는 상황은 여러 가지가 있다.

Modeling problems with antiparallel edges

유량 망은 역평행 간선을 허용하지 않으므로, 역평행 간선이 존재한다면 중간 정점을 하나 추가해 역평행 간선이 없는 유량 망으로 바꾼다.

Networks with multiple sources and sinks

소스와 싱크가 여러 개일 경우 수퍼소스 s와 수퍼싱크 t를 추가해 c(s, s_{i}) = c(t_{i}, t) = \infty가 되도록 한다.

26.2. The Ford-Fulkerson method

최대 유량 문제를 푸는 데는 포드-풀커슨 방법이 유용하다. 이는 다음과 같다.

FORD-FULKERSON-METHOD(G, s, t)
initialize flow f to 0
while there exists an augmenting path p in the residual network G_f
    augment flow f along p
return f

이를 구현하기 위해서는 몇 가지 개념들을 추가로 설명해야 한다.

Residual networks

유량 f에 대한 잔여 용량을 다음과 같이 정의한다.

c_{f}(u, v) = c(u, v) - f(u, v) if (u, v) \in E, f(v, u) if (v, u) \in E, 0 otherwise.

이 때 잔여 용량이 양수인 잔여 간선으로 만든 망을 잔여 망이라 한다. 이 때 \lvert E_{f} \rvert \leq 2 \lvert E \rvert이 성립한다. 잔여 망 내의 유량 f^{\prime}이 존재할 때 f에 대한 f^{\prime}증강f \uparrow f^{\prime}(u, v) = f(u, v) + f^{\prime}(u, v) - f^{\prime}(v, u) if (u, v) \in E, 0 otherwise로 정의한다. 이 때 간선에 역방향 유량을 잔여 망에 추가하는 것을 간선에 대한 취소라 한다.

Lemma. f \uparrow f^{\prime}은 G 내의 유량으로 \lvert f \uparrow f^{\prime} \rvert = \lvert f \rvert + \lvert f^{\prime} \rvert이다.

Augmenting paths

유량 f에 대한 증강 경로는 잔여 망 내 소스에서 싱크로의 단순 경로이다. 이를 이용해 기존 유량을 증강시킬 수 있다. 이를 통해 증강시킬 수 있는 최대 유량을 잔여 용량 c_{f}(p) = \min \{c_{f}(u, v) : (u, v) is on p\}이라 한다.

Lemma. G_{f}의 증강 경로 p에 대해 f_{p}(u, v) = c_{f}(p) if (u, v) \in p, 0 otherwise로 놓으면 f_{p}는 양의 값을 가진 G_{f} 위의 유량이다.

Corollary. G_{f}의 증강 경로 p에 대해 f를 f_{p}로 증강시킬 수 있다. 이 때의 증강된 유량은 기존 유량보다 크다.

Cuts of flow networks

유량 망의 절단은 정점들을 (S, T = V – S)로 분할해 한 쪽에 소스, 한 쪽에 싱크가 속하도록 하는 것이다. 이 때 유량 f에 대해 절단 (S, T)에 대한 알짜 유량f(S, T) = \sum_{u \in S} \sum_{v \in T} f( u, v) - \sum_{u \in S} \sum_{v \in T} f( v, u)으로 정의된다. 이 절단의 용량c(S, T) = \sum_{u \in S} \sum_{v \in T} c(u, v)이다. 최소 절단은 용량이 최소인 절단이다.

Lemma. G에서 유량 f와 절단 (S, T)이 있을 때 (S, T)에 대한 알짜 유량은 f(S, T) = \lvert f \rvert이다.

Corollary. 유량 망 G에서 임의의 유량은 G 내의 모든 절단에 대해 그 절단의 용량보다 작다.

Theorem. (Max-flow min-cut theorem) f가 유량일 때 다음 세 조건은 동치이다.

  1. f가 최대 유량이다.
  2. 잔여 망 G_{f}에 증강 경로가 없다.
  3. 어떤 절단 c에 대해 \lvert f \rvert = c(S, T)이다.

The basic Ford-Fulkerson algorithm

이를 통해서 포드-풀커슨을 구현하면 다음과 같다.

FORD-FULKERSON(G, s, t)
for each edge (u, v) ∈ G.E
    (u, v).f = 0
while there exists a path p from s to t in the residual network G_f
    c_f(p) = min {c_f(u, v) : (u, v) is in p}
    for each edge (u, v) in p
        if (u, v) ∈ E
            (u, v).f = (u, v).f + c_f(p)
        else
            (v, u).f = (v, u).f - c_f(p)

Analysis of Ford-Fulkerson

유량이 가질 수 있는 값이 정수일 때 최대 유량의 값을 \lvert f^{\ast} \rvert이라 하면 포드-풀커슨의 동작 시간 상한은 O(E \lvert f^{\ast} \rvert)이다.

The Edmonds-Karp algorithm

에드몬즈-카프 알고리즘은 포드-풀커슨 내의 증강 경로를 넓이 우선 탐색으로 찾는다. 즉, 증강 경로를 s에서 t로의 경로 중 최단 경로로 찾는다. (여기서는 경로의 가중치를 전부 1로 가정한다.) O(VE^{2}) 시간에 동작한다.

Lemma. 에드몬즈-카프 알고리즘은 잔여 망 내에서 소스에서 싱크로의 최단 경로 길이를 각 유량 증강에 대해 단조증가시킨다.

Theorem. 에드몬즈-카프 알고리즘을 썼을 때 수행되는 유량 증강의 횟수는 O(VE)이다.

26.3. Maximum bipartite matching

어떤 조합론적 문제들은 최대 유량 문제로 바꿔서 풀 수 있다.

The maximum-bipartite-matching problem

비방향그래프에 대해, 매칭 M은 모든 정점 v에 대해 M과 v가 최대 1회만 인접하는 간선의 집합이다. 인접했을 경우 매칭되었다고, 아니면 언매칭되었다고 한다. 최대 매칭은 크기가 최대인 매칭이다. 이분 그래프에서 최대 이분 매칭은 어떻게 찾아야 할까?

Finding a maximum bipartite matching

이분 그래프에 대해서 대응 유량망을 구성해 정수값을 가진 유량에 대한 최대 유량 문제로 바꿔 풀 수 있다.

Lemma. 이분 그래프에 대한 대응 유량망에 대해, 그래프의 매칭은 대응 유량망 내의 유량에 대응한다.

Theorem. 유량이 정수 값만 가진다면, 포드-풀커슨에 의해 생성되는 최대 유량은 정수값을 가진다. 또한, 각 간선에 대해 f(u, v)도 정수이다.

Corollary. 이분 그래프의 최대 매칭의 크기는 대응 유량망의 최대 유량의 크기와 같다.

26.4. Push-relabel algorithms

이 장에서는 O(V^{2}E) 시간에 최대 유량 문제를 푸는 법을 소개한다. 이는 밀기-재표기 알고리즘으로써, 전체 유량망을 탐색하지 않고 한 정점씩 인접한 정점들만 탐색한다. 포드-풀커슨처럼 유량 보존 법칙을 지키는 대신, 전유량 \sum_{v \in V} f(v,u) - \sum_{v \in V} f(u, v) \geq 0 을 유지한다. e(u) = \sum_{v \in V} f(v, u) - \sum_{v \in V} f(u, v)을 정점 u에 대한 잉여 유량이라 하고, 잉여 유량이 0보다 클 경우 과류라 한다.

Intuition

밀기-재표기 알고리즘이 기반한 직관은 다음과 같다. 각 정점은 액체를 누적할 수 있는 저장고와 연결되어 있다. 각 정점, 저장고 및 그에 연결된 모든 파이프는 알고리즘이 진행됨에 따라 높이가 증가하는 플랫폼 위에 서 있다. 정점 높이는 유량이 어떻게 푸시되는지를 결정한다. 푸시는 더 높은 정점에서 더 낮은 정점으로만 가능하다. 알고리즘 도중 과류된 정점이 있을 경우 이를 재표기해 높이를 높인다. 이를 통해 전유량을 최대 유량으로 점진적으로 바꾼다.

The basic operations

전유량 f에 대해 높이 함수 h를 h(s) = \lvert V \rvert, h(t) = 0, 잔여 망 내 모든 간선 (u, v)에 대해 h(u) \leq h(v) + 1 을 정의한다. 이 때 다음을 얻는다.

Lemma. 전유량 f에 대해 높이 함수 h가 있을 때 h(u) > h(v) + 1이면 (u, v)는 잔여망 내 간선이 아니다.

The push operation

푸시 연산은 다음과 같다.

PUSH(u, v)
// Applies when: u is overflowing, c_f(u, v) > 0, and u.h = v.h + 1
// Action: Push Δ_f(u, v) = min(u.e, c_f(u, v)) units of flow from u to v.
Δ_f(u, v) = min(u.e, c_f(u, v))
if (u, v) ∈ E
    (u, v).f += Δ_f(u, v)
else
    (v, u).f -= Δ_f(u, v)
u.e -= Δ_f(u, v)
v.e += Δ_f(u, v)

이를 u에서 v로의 푸시라고 정의한다. 푸시 후에 잔여 망이 포화되면 포화 푸시, 아니면 비포화 푸시라고 한다.

Lemma. u에서 v로의 비포화 푸시 이후에는 u는 더 이상 과류되지 않는다.

The relabel operation

리라벨 연산은 다음과 같다.

RELABEL(u)
// Applies when: u is overflowing and for all v ∈ V such that (u, v) ∈ E_f, we have u.h ≤ v.h
// Action: Increase the height of u.
u.h = 1 + min{v.h : (u, v) ∈ E_f}

이 연산에 대해 정점 u가 리라벨되었다고 한다.

The generic algorithm

이를 이용한 푸시-리라벨 알고리즘은 다음과 같이 구성된다.

INITIALIZE-PREFLOW(G, s)
for each vertex v ∈ G.V
    v.h = 0
    v.e = 0
for each edge (u, v) ∈ G.E
    (u, v).f = 0
s.h = |G.V|
for each vertex v ∈ s.Adj
    (s, v).f = c(s, v)
    v.e = c(s, v)
    s.e -= c(s, v)
GENERIC-PUSH-RELABEL(G)
INITIALIZE-PREFLOW(G, s)
while there exists an applicable push or relabel operation
    select an applicable push or relabel operation and perform it

이 때 다음이 성립한다.

Lemma. (An overflowing vertex can be either pushed or relabeled) 과류된 정점 u가 있다면 푸시나 리라벨 연산 중 하나가 가능하다.

Correctness of the push-relabel method

Lemma. (Vertex heights never decrease) GENERIC-PUSH-RELABEL 중 u.h는 절대 감소하지 않으며, 리라벨되면 최소 높이가 1 증가한다.

Lemma. GENERIC-PUSH-RELABEL은 높이 함수의 성질을 유지한다.

Lemma. f가 전유량일 때 잔여 망 G_{f} 내에서 소스에서 싱크로의 경로는 없다.

Theorem. (Correctness of the generic push-relabel algorithm) GENERIC-PUSH-RELABEL이 종료되면 전유량 f는 최대 유량이다.

Analysis of the push-relabel method

푸시-리라벨 법을 분석해 보자.

Lemma. f가 전유량일 때 과류된 정점 x에 대해 잔여 망 G_{f} 내에서 x에서 s로의 단순 경로가 존재한다.

Lemma. GENERIC-PUSH-RELABEL 중 모든 정점에 대해 높이는 항상 2 \lvert V \rvert - 1 이하이다.

Corollary. (Bound on relabel operations) 리라벨 연산은 정점당 최대 2 \lvert V \rvert - 1번 수행되며, 총 최대 2 \lvert V \rvert^{2}번 수행된다.

Lemma. (Bound on saturating pushes) 포화 푸시의 수는 2 \lvert V \rvert \lvert E \rvert 번보다 작다.

Lemma. (Bound on nonsaturating pushes) 비포화 푸시의 수는 4 \lvert V \rvert^{2} (\lvert V \rvert + \lvert E \rvert) 보다 작다.

Theorem. GENERIC-PUSH-RELABEL에서 기본 연산의 수는 O(V^{2} E)이다.

Corollary. 임의의 유량 망에 대해 O(V^{2} E)에 동작하는 일반적 푸시-리라벨 알고리즘 구현이 존재한다.

26.5. The relabel-to-front algorithm

전방-리라벨 알고리즘은 O(V^{3}) 시간에 최대 유량 문제를 푼다. 이는 정점의 목록을 보존한 뒤, 앞부터 과류된 정점을 찾아내 이를 방류하고, 리라벨할 때는 리스트의 맨 앞으로 보낸다.

Admissible edges and networks

c_{f}(u, v) > 0이고 h(u) = h(v) + 1이면 (u, v)허용 가능 간선이라 한다. 아니면 비허용이라 한다. 허용 망은 허용 가능한 간선으로 이루어진 망이다.

Lemma. (The admissible network is acyclic) 허용 가능 간선은 순환이 없다.

Lemma. u가 과류된 정점이고 (u, v)가 허용 가능 간선이면 PUSH(u, v)가 가능하다. 이는 새 허용 간선을 만들지 않고, (u, v)를 비허용으로 만들 수 있다.

Lemma. u가 과류된 정점이고 u를 떠나는 허용 가능 간선이 없다면 RELABEL(u, v)가 가능하다. 리라벨 이후에는 최소 1개의 u를 떠나는 허용 가능 간선이 생기며, u로 들어오는 허용 가능 간선은 없다.

Neighbor lists

전방-리라벨 알고리즘 내 간선은 이웃 리스트로 구성된다. 이는 각 정점에 대한 단일 연결 리스트들로 이루어져 있다.

Discharging an overflowing vertex

과류된 정점을 방류시키는 법은 다음과 같다.

DISCHARGE(u)
while u.e > 0
    v = u.current
    if v == NIL
        RELABEL(u)
        u.current = u.N.head
    else if c_f(u, v) > 0 and u.h == v.h + 1
        PUSH(u, v)
    else
        u.current = v.next-neighbor

Lemma. DISCHARGE가 PUSH(u, v)를 부르면 (u, v)가 푸시되고, RELABEL(u)를 부르면 u가 리라벨된다.

The relabel-to-front algorithm

이를 이용한 전방-리라벨 알고리즘은 다음과 같다.

RELABEL-TO-FRONT(G, s, t)
INITIALIZE-PREFLOW(G, s)
L = G.V - {s, t} in any order
for each vertex u ∈ G.V - {s, t}
    u.current = u.N.head
u = L.head
while u ≠ NIL
    old-height = u.h
    DISCHARGE(u)
    if u.h > old-height
        move u to the front of list L
    u = u.next

Analysis

Theorem. RELABEL-TO-FRONT의 수행 시간은 O(V^{3})이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중