최대 유량 최소 컷 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의 및 설명
3. 주요 정리
4. 선형 계획법 공식화
- 4.1. 최대 유량 (주문제)
- 4.2. 최소 컷 (쌍대)
5. 증명
6. 응용
7. 역사
참조

1. 개요

최대 유량 최소 컷 정리는 네트워크에서 흐를 수 있는 최대 유량과 네트워크 컷의 최소 용량이 같다는 것을 나타내는 정리이다. 이 정리는 네트워크를 유향 그래프로 표현하고, 소스와 싱크를 설정하여 유량과 컷의 개념을 정의한다. 유량은 각 간선을 통과하는 유체의 양을 나타내며, 용량 제약과 흐름 보존의 두 가지 조건을 만족해야 한다. 컷은 네트워크의 정점을 두 개의 집합으로 나누는 것이며, 컷의 용량은 S에서 T로 향하는 간선들의 용량 합으로 정의된다. 최대 유량 최소 컷 정리는 포드-풀커슨 알고리즘을 통해 증명되며, 최대 유량 문제와 최소 컷 문제를 선형 계획법으로 공식화하여 해결할 수 있다. 이 정리는 체더바움의 최대 유량 정리, 일반화된 최대 유량 최소 컷 정리, 멩거의 정리 등 다양한 응용 분야에서 활용되며, 프로젝트 선택 문제 및 이미지 분할 문제와 같은 실생활 문제 해결에도 기여한다. 이 정리는 1956년 포드와 풀커슨에 의해 증명되었으며, 최대 유량 문제를 해결하는 데 중요한 역할을 한다.

더 읽어볼만한 페이지

그래프 이론 정리 - 램지의 정리
램지의 정리는 주어진 조건을 만족하는 램지 수가 존재한다는 정리로, 그래프 이론으로 해석되며, 특정 크기의 동색 클릭이 존재함을 보장하고, 램지 이론의 시초로 여겨진다.
그래프 이론 정리 - 4색 정리
4색 정리는 평면을 나눈 영역을 인접한 영역과 다른 색으로 칠할 때 필요한 최소 색의 수가 4개라는 정리로, 그래프 이론을 통해 추상화되어 평면 그래프의 4-채색 가능성을 나타내며, 컴퓨터를 이용한 증명과 그에 대한 논란, 그리고 재증명이 이루어졌다.
조합 최적화 - A* 알고리즘
A* 알고리즘은 가중치 그래프에서 시작 노드부터 목표 노드까지 최소 비용 경로를 찾는 정보 탐색 알고리즘으로, 경로 비용과 목표까지 추정 비용의 합을 최소화하여 경로를 탐색하며 내비게이션, 게임 AI 등에 활용된다.
조합 최적화 - 정수 계획법
정수 계획법은 선형 계획법의 한 분야로, 해가 정수 값을 가져야 하는 제약 조건이 추가된 최적화 문제이며, 다양한 분야에 응용되고 정확한 알고리즘 또는 휴리스틱 방법을 통해 해결할 수 있다.

최대 유량 최소 컷 정리

2. 정의 및 설명

최대 유량 최소 컷 정리는 네트워크를 통과하는 최대 유량과 네트워크 컷의 최소 용량이 같다는 것을 보여주는 정리이다.

두 단자 플로우 네트워크 $\boldsymbol{\Nu} = (G(V, E), c, s, t)$ 를 가정한다. 이는 유한 방향성 그래프 $G(V, E)$ 의 각 에지(변) $(u, v)$ 에 음이 아닌 실수인 '''용량''' $c(u, v)$ 가 할당되어 있으며, 시작 노드('''입구''') $s$ 와 끝 노드('''출구''') $t$ 가 지정된 네트워크를 의미한다.

플로우 $f$ 의 '''유량''' $|f|$ 는, 입구 $s$ 에서 빠져나가는 플로우의 합으로 정의된다.

: $|f| = \sum_{v \in N^-(s)} f(s, v)$ ^[1]

네트워크 $\boldsymbol{\Nu}$ 의 '''컷''' $(S, T)$ 는, 노드(정점) 집합 $V$ 를 두 개의 집합 $S$ 와 $T$ 로 분할하고, $S$ 에는 $s$ 가 포함되고, $T$ 에는 $t$ 가 포함되도록 하는 것을 말한다.^[1] $s$ 와 $t$ 외에는 어느 쪽 집합에 속할 수 있으므로, 가능한 컷의 종류는 $2^$

2. 1. 네트워크

유한 방향성 그래프 ''N'' = (''V'', ''E''). 여기서 ''V''는 정점의 유한 집합이고, ''E'' ⊆ ''V''×''V''는 방향성 간선(에지)의 집합이다.
'''소스'''(source) ''s'' ∈ ''V'' 및 '''싱크'''(sink) ''t'' ∈ ''V''.
'''용량'''(capacity) 함수 c_uv 또는 ''c''(''u'', ''v'')는 $c:E\to\R^+$ ( (''u'',''v'') ∈ ''E''에 대해)로 표현되는 매핑이다. 용량 함수는 간선을 통과하는 유량의 최대값을 의미한다.

2. 2. 유량

'''유량'''(Flow)은 각 간선에 흐르는 유체의 양을 나타내는 함수 f:E→R⁺^영어로, 다음 두 가지 제약 조건을 만족해야 한다.

# '''용량 제약''': 모든 간선

(u, v) \in E

에 대해,

f_{uv} \le c_{uv}.

(즉, 각 간선을 흐르는 유량은 그 간선의 용량을 초과할 수 없다.)

# '''흐름 보존''': 소스

s

와 싱크

t

를 제외한 각 정점

v

에 대해,

\sum\nolimits_{\{ u : (u,v)\in E\}} f_{uv} = \sum\nolimits_{\{w : (v,w)\in E\}} f_{vw}.

(즉, 각 정점에 들어오는 유량과 나가는 유량은 같아야 한다.)

이러한 흐름은 각 간선의 방향을 따라 네트워크를 통과하는 유체의 물리적 흐름으로 시각화할 수 있다.

흐름의 '''값'''은 소스에서 싱크로 흐르는 총 유량을 의미하며, 다음과 같이 정의된다.

:

|f| = \sum\nolimits_{\{v : (s,v)\in E\}} f_{sv}=\sum\nolimits_{\{v : (v,t)\in E\}} f_{vt},

여기서

s

는 네트워크의 소스이고

t

는 싱크이다.

최대 유량 문제는 주어진 네트워크에서 가능한 최대 유량 값을 찾는 문제이다.

2. 3. 컷

최대 유량 최소 컷 정리에서 '''s-t 컷'''(s-t cut)은 네트워크의 정점 집합 를 두 개의 집합 와 로 분할하는 것으로, 이고 를 만족해야 한다. 즉, s-t 컷은 네트워크의 정점을 '''소스'''(source) ''s''를 포함하는 집합 ''S''와 '''싱크'''(sink) ''t''를 포함하는 집합 ''T'', 두 집합으로 분할하는 것이다.

'''컷 집합'''(Cut-set)

X_C

는 소스 집합 ''S''와 싱크 집합 ''T''를 연결하는 간선의 집합이다.

:

X_C := \{ (u, v) \in E \ : \ u \in S, v \in T \} = (S\times T) \cap E.

s-t 컷 ''C''의 '''용량'''은

X_C

에 속하는 모든 간선의 용량의 합이다.

일반적으로 그래프에는 많은 컷이 있지만, 가중치가 작은 컷은 찾기가 더 어려운 경우가 많다.

'''최소 s-t 컷 문제'''(Minimum s-t cut problem)는 주어진 네트워크에서 용량이 최소인 s-t 컷, 즉 를 최소화하는 및 를 찾는 문제이다.

왼쪽부터: 1. 주어진 네트워크. 각 에지의 용량은 모두 동일하다고 가정한다. 2. 하나의 플로우. 3. 2의 잔여 네트워크와, 그 증가 경로. 4. 최대 플로우의 잔여 네트워크. ''s''에서 도달 가능한 녹색 원형 노드의 집합을 S, 불가능한 파란색 사각형 노드의 집합을 T라고 하면, (S, T)가 최소 컷이 된다.

3. 주요 정리

'''최대 유량 최소 컷 정리'''는 s와 t를 잇는 흐름의 최대값은 s-t 컷에 대한 최소 용량과 같다는 정리이다.

'''N'''의 최대 유량은 '''N'''의 유량 중 유량이 최대인 것을 말하며, 최소 컷은 '''N'''의 컷 중 용량이 최소인 것을 말한다. 이때, 최대 유량과 최소 컷에 대해 다음이 성립한다.

: $|f_{\mathrm{max}}| = c((S, T)_{\mathrm{min}})$

네트워크를 통과하는 모든 흐름의 값은 모든 ''s-t'' 컷의 용량보다 작거나 같고, 더 나아가 최대값을 갖는 흐름과 최소 용량을 갖는 ''s-t'' 컷이 존재한다는 것을 증명할 수 있다.

4. 선형 계획법 공식화

최대 유량 최소 컷 문제는 쌍대 관계를 가지는 선형 계획법으로 나타낼 수 있다.^[2]

	최대 유량 (주문제)	최소 컷 (쌍대)
변수	$f_{uv}$ $\forall (u,v)\in E$ (각 방향으로 하나의 변수, 간선당 두 개의 변수)	$d_{uv}$ $\forall (u,v)\in E$ (간선당 하나의 변수)
목적 함수	최대화 $\sum\nolimits_{v: (s,v)\in E} f_{sv}$ (소스에서 총 유량 최대)	최소화 $\sum\nolimits_{(u,v) \in E } c_{uv}d_{uv}$ (컷에 있는 간선의 총 용량 최소)
제약 조건	다음 조건을 만족해야 함:	다음 조건을 만족해야 함:
부호 제약 조건	$\begin{align}$	$\begin{align}$

최소 컷 선형 계획법에서 변수

d_{uv}

는 ''u''가 소스 ''S'' 집합에 속하고 ''v''가 싱크 ''T'' 집합에 속하면(즉, 간선 ''uv''가 컷에 있으면) 1이고, 그렇지 않으면 0이다.

z_{v}

는 ''v''가 ''S''에 속하면 1이고, 그렇지 않으면 0이다.^[3]

최소화 목적 함수는 컷에 포함된 모든 간선의 용량을 더하며, 제약 조건은 변수가 실제로 유효한 컷을 나타내도록 한다.^[3]

최대 유량 문제와 최소 컷 문제의 최적값이 같다는 최대 유량 최소 컷 정리의 등식은 선형 계획법의 강한 쌍대성 정리에서 유도된다. 즉, 주문형 프로그램에 최적 해가 있으면, 쌍대 프로그램에도 최적 해가 있으며, 두 해에 의해 형성된 최적 값이 같다는 것이다.

4. 1. 최대 유량 (주문제)

최대 유량 문제에서 각 간선 $(u, v)$에 대한 유량 $f_{uv}$를 변수로 사용한다.^[2]

목적 함수는 $\sum\nolimits_{v: (s,v)\in E} f_{sv}$ (소스에서 나가는 총 유량)를 최대화하는 것이다.^[2]

제약 조건은 다음과 같다:^[2]

$f_{uv} \leq c_{uv}$ (각 간선의 유량은 용량을 초과할 수 없음)
$\sum_{u} f_{uv} - \sum_{w} f_{vw} = 0$ (소스와 싱크를 제외한 각 노드에서 들어오는 유량과 나가는 유량은 같아야 함)
$f_{uv} \geq 0$ (유량은 음수가 아니어야 함)

4. 2. 최소 컷 (쌍대)

선형 계획법의 강한 쌍대성 정리에 따르면, 최대 유량 문제의 최적 해가 존재하면 쌍대 문제인 최소 컷 문제에도 최적 해가 존재하며, 두 해의 최적값은 같다.^[2]

최소 컷 선형 계획법에서 변수의 의미는 다음과 같다.

$d_{uv} = \begin{cases} 1, & \text{if }u \in S \text{ and } v \in T \text{ (간선 } uv \text{가 컷에 있음) }$

\\ 0, & \text{그렇지 않음} \end{cases}

$z_{v} = \begin{cases} 1, & \text{if } v \in S \\ 0, & \text{그렇지 않음} \end{cases}$

최소화 목적 함수는 컷에 포함된 모든 간선의 용량을 더한다.^[3]

제약 조건은 변수가 실제로 유효한 컷을 나타내도록 보장한다.^[3]

비단말 노드 ''u'', ''v''에 대해, $d_{uv} - z_u + z_v \geq 0$ ( $d_{uv} \geq z_u - z_v$ 와 동일) 제약 조건은 ''u''가 ''S''에 있고 ''v''가 ''T''에 있다면, 간선 (''u'', ''v'')가 컷에 포함됨을 보장한다 ( $d_{uv} \geq 1$ ).
$d_{sv} + z_v \geq 1$ ( $d_{sv} \geq 1 - z_v$ 와 동일) 제약 조건은 ''v''가 ''T''에 있다면, 간선 ''(s,v)''가 컷에 포함됨을 보장한다 (''s''는 정의상 ''S''에 있기 때문이다).
$d_{ut} - z_u \geq 0$ ( $d_{ut} \geq z_u$ 와 동일) 제약 조건은 ''u''가 ''S''에 있다면, 간선 ''(u,t)''가 컷에 포함됨을 보장한다 (''t''는 정의상 ''T''에 있기 때문이다).

최소화 문제이므로, 컷에 간선이 없다는 것을 보장할 필요는 없으며, 컷에 있어야 하는 각 간선이 목적 함수에 합산되도록 보장하기만 하면 된다.

변수	$d_{uv}$ (u, v) ∈ E (간선당 하나의 변수)
목적 함수	$\sum\nolimits_{(u,v) \in E } c_{uv}d_{uv}$ 최소화 (컷에 있는 간선의 총 용량 최소)
제약 조건	다음 조건을 만족해야 함:
부호 제약 조건	$\begin{align}$

5. 증명

포드-풀커슨 알고리즘을 사용하여 최대 유량을 계산하고, 잔여 네트워크를 통해 최소 컷을 구함으로써 최대 유량 최소 컷 정리를 증명할 수 있다.^[10]^[11]

G = (V, E)

를 소스

s

와 싱크

t

를 각각 갖는 네트워크(방향 그래프)라고 하자.

포드-풀커슨 알고리즘에 의해

G

에 대해 계산된 흐름

f

를 고려한다.

G

에 대해 얻어진 잔여 그래프

G_f

에서, 다음과 같이 정점의 두 하위 집합을 정의한다.

#

A

:

G_f

에서

s

로부터 도달 가능한 정점 집합

#

A^c

: 나머지 정점 집합, 즉

V - A

A^c

는

A

에 속하지 않는 나머지 정점들의 집합이다.

'''주장.'''

value(f) = c(A, A^c)

여기서 ''s-t 컷''의 '''용량'''은 다음과 같이 정의된다.

:

c(S,T) = \sum\nolimits_{(u,v) \in S \times T} c_{uv}

.

모든 정점의 하위 집합

A

에 대해

value(f) = f_{out}(A) - f_{in}(A)

임을 안다. 따라서,

value(f) = c(A, A^c)

가 되려면 다음 조건이 필요하다.

컷에서 모든 ''출발 엣지''는 '''완전히 포화'''되어야 한다.
컷으로의 모든 ''도착 엣지''는 '''영 흐름'''을 가져야 한다.

위 주장을 증명하기 위해 두 가지 경우를 고려한다.

$G$ 에서, $(x,y), x \in A, y \in A^c$ 와 같은 ''출발 엣지''가 존재하고, 이 엣지가 포화되지 않았다는 의미는 $f(x, y) < c_{xy}$ 가 성립한다는 것이다. 이는 $G_f$ 에서 $x$ 에서 $y$ 로 가는 '''정방향 엣지'''가 존재함을 의미하므로, $G_f$ 에서 $s$ 에서 $y$ 로 가는 경로가 존재하며, 이는 모순이다. 따라서, 모든 출발 엣지 $(x, y)$ 는 완전히 포화된다.

$G$ 에서, $(y,x), x \in A, y \in A^c$ 와 같은 ''도착 엣지''가 존재하고, 이 엣지가 0이 아닌 흐름을 전달한다는 의미는 $f(y, x) > 0$ 이 성립한다는 것이다. 이는 $G_f$ 에서 $x$ 에서 $y$ 로 가는 '''역방향 엣지'''가 존재함을 의미하므로, $G_f$ 에서 $s$ 에서 $y$ 로 가는 경로가 존재하며, 이는 다시 모순이다. 따라서, 모든 도착 엣지 $(y, x)$ 는 영 흐름을 가져야 한다.

위의 두 진술은 위에서 설명된 방식으로 얻어진 컷의 용량이 네트워크에서 얻어진 흐름과 같다는 것을 증명한다. 또한, 흐름은 포드-풀커슨 알고리즘에 의해 얻어졌으므로, 이는 네트워크의 최대 흐름이기도 하다.

또한, 네트워크의 모든 흐름은 네트워크에서 가능한 모든 컷의 용량보다 항상 작거나 같으므로, 위에서 설명된 컷은 또한 최대 흐름을 얻는 최소 컷이다.

최대 흐름은 포드-풀커슨 알고리즘에 의해 다음과 같이 찾을 수 있다.^[11]

# 두 단자 흐름 네트워크

Ν(G(V, E), c, s, t)

가 주어졌다고 가정한다.

# 최대 유량을 찾기 위해,

s

에서

t

로 가는 경로를 찾는다. 이 경로를 구성하는 모든 엣지의 용량의 최소값을 엣지의 유량으로 할당하면, 이것이 이 네트워크의 흐름이 된다.

# 유량의 여유를 용량으로 하는 순방향 엣지와, 현재 유량을 용량으로 하는 역방향 엣지로 이루어진 네트워크에서, 용량이 0이 되는 엣지를 제거한 것을 '''잔여 네트워크''' (residual network) 또는 보조 네트워크라고 부른다. 이 잔여 네트워크 안에서, 똑같이 경로를 찾는다. 경로의 구성 요소 중, 순방향 엣지에서는 유량을 증가시키고, 역방향 엣지에서는 유량을 감소시킴으로써, 더 유량이 큰 새로운 흐름을 얻을 수 있다. (이러한, 흐름

f

의 잔여 네트워크에서

s

에서

t

로 가는 경로를,

f

의 '''증가 경로'''라고 부른다.)

# 증가 경로가 없어지면, 이 흐름이

Ν

의 최대 흐름이다.

최대 흐름의 잔여 네트워크는,

s

에서 도달 가능한 노드군

S

와 도달 불가능한 노드군

T

로 나눌 수 있다. 증가 경로가 없으므로,

t

는

T

에 포함된다. 정의에 의해, 잔여 네트워크 상에서는

S

에서

T

로 가는 엣지는 존재하지 않는다. 원래 네트워크로 돌아가서 생각하면,

S

에서 나오는 엣지

(u, v)

는 모두, 잔여 네트워크에 존재하지 않으므로, 유량의 여유가 없다, 즉

f(u, v) = c(u, v)

가 된다는 것을 알 수 있다. 또한,

S

에 들어가는 엣지는 역방향 엣지가 잔여 네트워크에 없으므로, 유량이 0이라는 것을 알 수 있다. 이러한 점들로부터,

c(S, T) = |f_{\mathrm{max}}|

가 된다.

따라서,

|f_{\mathrm{max}}| = c(S, T) \geq c((S, T)_{\mathrm{min}})

이다.

다음으로

c((S, T)_{\mathrm{min}}) \geq |f_{\mathrm{max}}|

도 성립한다는 것을 본다. 임의의 흐름

f

에 대해,

T

로 흘러 들어오는 엣지

(u, v)

의 유량은 최대

c(u, v)

이며, 이것의 합은

(S, T)

의 컷의 용량의 정의 그 자체이다. 한편,

T

에서

S

로 역류하는 엣지의 유량은, 당연하게도 최소값은 0 이상이다. 흐름의 유량은 유량 보존에 의해,

T

로 유입되는 유량에서 역류하는 유량을 뺀 것임을 확인했지만, 이 점으로부터

f

의 유량은 최대 컷

(S, T)

의 용량이 된다. 이 점으로부터,

c(S, T) \geq |f|

, 특히

c((S, T)_{\mathrm{min}}) \geq |f_{\mathrm{max}}|

이다.

6. 응용

최대 유량 최소 컷 정리는 다양한 분야에 응용될 수 있다.

체더바움의 최대 유량 정리 (Cederbaum's maximum flow theorem)

최대 유량 문제는 비선형 저항 소자로 구성된 네트워크에서 흐르는 전류를 최대화하는 문제로 나타낼 수 있다.^[4] 입력 전압이 무한대로 갈 때, 전기 네트워크 입력 단자 사이의 전류 극한은 최소 가중치 컷 집합의 가중치와 같다.

:

\lim_{V_{\text{in}} \to \infty} (I_{in})= \min_{X_C}\sum_{(u,v) \in X_C}c_{uv}

일반화된 최대 유량 최소 컷 정리 (Generalized max-flow min-cut theorem)

각 정점에 용량이 있다고 가정하고, 유량

f

는 용량 제약, 유량 보존뿐만 아니라 정점 용량 제약도 만족해야 한다.

:

\forall v \in V \setminus \{s,t\} : \qquad \sum\nolimits_{\{u\in V\mid (u,v)\in E\}} f_{uv} \le c(v).

즉, 정점을 통과하는 유량의 양은 해당 정점의 용량을 초과할 수 없다. ''s-t 컷''은 ''s''에서 ''t''로 가는 모든 경로에 대해 해당 경로가 컷의 구성원을 포함하는 정점과 엣지의 집합으로 정의한다. 이 경우, ''컷의 용량''은 컷 내 각 엣지와 정점의 용량 합이다.

일반화된 최대 유량 최소 컷 정리는 s-t 유량의 최댓값이 이 새로운 의미에서 s-t 컷의 최소 용량과 같다고 말한다.

멩거의 정리 (Menger's theorem)

멩거의 정리는 무방향 그래프에서 엣지 분리(edge-disjoint) s-t 경로의 최대 개수가 s-t 컷-셋의 최소 엣지 개수와 같다고 명시한다.

프로젝트 선택 문제 (Project selection problem)

프로젝트 선택 문제는 자원 할당 및 최적화 문제에 적용될 수 있다. 여러 프로젝트와 기계가 있을 때, 각 프로젝트는 수익을 발생시키고 각 기계는 구매 비용이 발생한다. 목표는 총 이익(선택된 프로젝트의 수익 - 구매된 기계의 비용)을 최대화하는 것이다.

이 문제는 소스가 용량으로 프로젝트에 연결되고 싱크가 용량으로 기계에 연결되는 네트워크를 구성하여 최소 컷 문제로 공식화할 수 있다. 최대 유량 최소 컷 정리에 의해 이 문제는 최대 유량 문제로 해결할 수 있다.

이미지 분할 문제 (Image segmentation problem)

컴퓨터 비전 분야에서 이미지 분할 문제는 각 픽셀에 전경(Foreground) 또는 배경(Background) 값을 할당하고, 인접 픽셀 간의 차이에 따른 벌점을 최소화하는 문제로 볼 수 있다.

이 문제는 소스(주황색 노드)가 용량 f|f_i^영어로 모든 픽셀에 연결되고, 싱크(보라색 노드)가 용량 b|b_i^영어로 모든 픽셀에 연결되는 네트워크를 구성하여 최소 컷 문제로 만들 수 있다.

6. 1. 체더바움의 최대 유량 정리 (Cederbaum's maximum flow theorem)

최대 유량 문제는 비선형 저항 소자로 구성된 네트워크를 통해 흐르는 전류의 최대화로 공식화될 수 있다.^[4] 이 공식에서, 입력 전압이

\infty

에 접근할 때 전기 네트워크의 입력 단자 간의 전류 극한은 최소 가중치 컷 집합의 가중치와 같다.

:

\lim_{V_{\text{in}} \to \infty} (I_{in})= \min_{X_C}\sum_{(u,v) \in X_C}c_{uv}

6. 2. 일반화된 최대 유량 최소 컷 정리 (Generalized max-flow min-cut theorem)

엣지 용량 외에도, 각 정점에 용량이 있다고 가정해 보자. 즉, mapping^영어

c:V\to\R^+

로 표시되는

c(v)

가 존재하여, 유량

f

는 용량 제약 및 유량 보존뿐만 아니라 정점 용량 제약도 만족해야 한다.

:

\forall v \in V \setminus \{s,t\} : \qquad \sum\nolimits_{\{u\in V\mid (u,v)\in E\}} f_{uv} \le c(v).

다시 말해, 정점을 통과하는 ''유량''의 양은 해당 정점의 용량을 초과할 수 없다. ''s-t 컷''을 ''s''에서 ''t''로 가는 모든 경로에 대해 해당 경로가 컷의 구성원을 포함하는 정점과 엣지의 집합으로 정의한다. 이 경우, ''컷의 용량''은 컷 내 각 엣지와 정점의 용량 합이다.

이 새로운 정의에서, '''일반화된 최대 유량 최소 컷 정리'''는 s-t 유량의 최댓값이 이 새로운 의미에서 s-t 컷의 최소 용량과 같다고 말한다.

6. 3. 멩거의 정리 (Menger's theorem)

무방향 엣지-분리 경로 문제에서, 무방향 그래프 G (V, E)}}와 두 개의 정점 s와 t가 주어지며, G에서 엣지-분리 s-t 경로의 최대 개수를 찾아야 한다.

'''멩거의 정리'''는 무방향 그래프에서 엣지-분리 s-t 경로의 최대 개수가 s-t 컷-셋의 최소 엣지 개수와 같다고 명시한다.

6. 4. 프로젝트 선택 문제 (Project selection problem)

프로젝트 선택 문제는 자원 할당 및 최적화 문제에 적용될 수 있다. 이 문제는 개의 프로젝트와 개의 기계가 있을 때, 각 프로젝트 는 수익 를 발생시키고 각 기계 는 구매 비용 가 발생한다. 여기서 주어진 제약 조건은 각 프로젝트는 해당 프로젝트를 선택하기 위해 필요한 기계 집합을 지정한다는 것이다. 목표는 프로젝트의 하위 집합을 선택하고 기계의 하위 집합을 구매하여 총 이익(선택된 프로젝트의 수익 - 구매된 기계의 비용)을 최대화하는 것이다.

이 문제를 해결하기 위해 를 선택하지 않은 프로젝트 집합, 를 구매한 기계 집합으로 설정하면, 문제는 다음과 같이 공식화할 수 있다.

:

\max \{g\} = \sum_{i} r(p_i) - \sum_{p_i \in P} r(p_i) - \sum_{q_j \in Q} c(q_j).

첫 번째 항은 와 의 선택에 의존하지 않으므로, 이 최대화 문제는 다음의 최소화 문제로 다시 공식화할 수 있다.

:

\min \{g'\} = \sum_{p_i \in P} r(p_i) + \sum_{q_j \in Q} c(q_j).

위의 최소화 문제는 소스가 용량 로 프로젝트에 연결되고 싱크가 용량 로 기계에 연결되는 네트워크를 구성하여 최소 컷 문제로 공식화할 수 있다. 프로젝트 가 기계 를 필요로 하는 경우 무한대 용량의 에지 가 추가된다. s-t 컷 세트는 및 에 있는 프로젝트와 기계를 각각 나타낸다. 최대 유량 최소 컷 정리에 의해 이 문제는 최대 유량 문제로 해결할 수 있다.

오른쪽 그림은 다음 프로젝트 선택 문제의 네트워크 공식을 보여준다.

width="20px" \|	프로젝트	기계
1	100USD	200USD	프로젝트 1은 기계 1과 2를 필요로 합니다.
2	200USD	100USD	프로젝트 2는 기계 2를 필요로 합니다.
3	150USD	50USD	프로젝트 3은 기계 3을 필요로 합니다.

s-t 컷의 최소 용량은 250USD이고 각 프로젝트의 수익 합계는 450USD이므로, 프로젝트 와 를 선택하여 최대 이익 ''g''는 450USD - 250USD = 200USD이다.

여기서 아이디어는 각 프로젝트의 이익을 해당 기계의 '파이프'를 통해 '흐르게'하는 것이다. 기계의 파이프를 채울 수 없는 경우, 기계의 수익이 비용보다 적고, 최소 컷 알고리즘은 기계의 비용 에지 대신 프로젝트의 이익 에지를 자르는 것이 더 저렴하다는 것을 발견할 것이다.

6. 5. 이미지 분할 문제 (Image segmentation problem)

컴퓨터 비전 분야에서 이미지 분할 문제는 각 픽셀에 전경(Foreground) 또는 배경(Background) 값을 할당하고, 인접 픽셀 간의 차이에 따른 벌점을 최소화하는 문제로 볼 수 있다.

''n''개의 픽셀이 있는 이미지 분할 문제에서 각 픽셀 ''i''는 전경 값 f|f_i^영어 또는 배경 값 b|b_i^영어를 가질 수 있다. 픽셀 ''i'', ''j''가 인접하고 서로 다른 값을 가지면 벌점 p|p_ij^영어가 부여된다. 이 문제는 픽셀에 전경 또는 배경을 할당하여 값의 합에서 벌점을 뺀 값을 최대화하는 방식으로 해결할 수 있다.

전경에 할당된 픽셀 집합을 ''P'', 배경에 할당된 픽셀 집합을 ''Q''라고 할 때, 문제는 다음과 같이 표현할 수 있다.

:

\max \{g\} = \sum_{i \in P} f_i + \sum_{i \in Q} b_i - \sum_{i \in P,j \in Q \lor j \in P,i \in Q } p_{ij}.

이 최대화 문제는 최소화 문제로 바꿔 표현할 수 있다.

:

\min \{g'\} = \sum_{i \in P,j \in Q \lor j \in P,i \in Q } p_{ij}.

위의 최소화 문제는 소스(주황색 노드)가 용량 f|f_i^영어로 모든 픽셀에 연결되고, 싱크(보라색 노드)가 용량 b|b_i^영어로 모든 픽셀에 연결되는 네트워크를 구성하여 최소 컷 문제로 만들 수 있다. 두 인접 픽셀 사이에는 p|p_ij^영어 용량의 두 간선(''i'', ''j'') 및 (''j'', ''i'')이 추가된다. 이때 s-t 컷 집합은 ''P''에서 전경에 할당된 픽셀과 ''Q''에서 배경에 할당된 픽셀을 나타낸다.

7. 역사

1955년 T. E. 해리스(T. E. Harris)가 퇴역한 F. S. 로스 장군과 함께 철도 교통 흐름의 단순화된 모델을 공식화하면서 최대 유량 문제를 제안하였다.^[5]^[6]

1956년 포드와 풀커슨이 최대 유량 최소 컷 정리를 증명하였다.^[6] 같은 해, P. 엘리아스, A. 파인스타인, 클로드 섀넌도 독립적으로 이 정리를 증명하였다.^[7]^[8]^[9] 최대 유량을 구하는 문제는 선형 계획법의 특수한 형식이며, 최대 유량 최소 컷 정리는 선형 계획법의 쌍대성 정리의 특수한 경우로 볼 수 있다.

참조

_[1] 간행물 On the max-flow min-cut theorem of networks http://www.dtic.mil/[...] 1964-09-09
_[2] 웹사이트 Lecture 15 from CS261: Optimization http://theory.stanfo[...]
_[3] 웹사이트 LP min-cut max-flow presentation http://u.cs.biu.ac.i[...]
_[4] 간행물 On the optimal operation of communication nets 1962-08
_[5] 서적 Flows in Networks "[[Princeton University Press]]" 1962
_[6] 논문 Maximal flow through a network 1956
_[7] 논문 A note on the maximum flow through a network 1956
_[8] 서적 On the Max-Flow MinCut Theorem of Networks Princeton, New Jersey 1956
_[9] 논문 A simple algorithm for finding the maximum network flows and an application to the Hitchcock problem 1957
_[10] 문서 2002
_[11] 문서
_[12] 저널 http://www.dtic.mil/[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com