최대 흐름 최소 컷 정리

컴퓨터 과학 및 최적화 이론에서, max-flow min-cut 정리는 흐름 네트워크에서 소스에서 싱크대로 통과하는 최대 흐름의 양은 최소 컷에 있는 에지의 총 무게, 즉 제거될 경우 싱크대에서 선원을 분리할 수 있는 에지의 최소 총 무게와 동일하다고 기술한다.

이것은 선형 프로그램에 대한 이원성 정리의 특별한 경우이며 멩거 정리와 쾨니그-에거바리 ^[1]정리를 도출하는 데 사용될 수 있다.

정의 및 스테이트먼트

이 정리는 네트워크를 통과하는 최대 흐름과 네트워크 컷의 최소 용량이라는 두 가지 양에 해당합니다.정리를 서술하기 위해서는 먼저 각각의 개념을 정의해야 한다.

네트워크

네트워크는 다음과 같이 구성됩니다.

유한 방향 $그래프$ N = ( $V,$ $E)$ 여기서 V는 정점의 유한 집합을 $나타내고$ E $µ$ V $\times V$ 는 방향 모서리의 집합이다.
$선원$ s $µV$ 및 $싱크$ t $µV$ ;
capacity 함수, 즉 매핑 $c:E\to \mathbb {R} ^{+}$ E $c:E\to \mathbb {R} ^{+}$ + {\ $displaystyle$ c $:$ $E$ ( $u, v) e$ E에 대해 c $또는$ c $(u, v)$ 로 $나타냅니다 uv$ .이것은 에지를 통과할 수 있는 최대 흐름량을 나타냅니다.

플로우

네트워크를 통과하는 흐름은 $f:E\to \mathbb {R} ^{+}$ $f:E\to \mathbb {R} ^{+}$ $f:E\to \mathbb {R} ^{+}$ $f:E\to \mathbb {R} ^{+}$ + {\ $displaystyle$ f $:$ $f_{uv}$ $\to \mathbb {R}^{+}:$ $f_{uv}$ v $f_{uv}$ {\ $displaystyle$ $f_{$ uv $f_{uv}$ $f(u,v)$ $f(u,v)$ f $u$ , $v )$ 로 표시되며 다음 두 가지 제약사항이 적용됩니다.

용량 제약:모든 $(u,v)\in E$ 엣지( $(u,v)\in E$ , $(u,v)\in E$ ) $(u,v)\in E$ E {\ $displaystyle (u, v)\in$ E $(u,v)\in E$ $f_{uv}\leq c_{uv}.$ v $f_{uv}\leq c_{uv}.$ $f_{uv}\leq c_{uv}.$ . $f_{uv}\leq c_{uv}.$ \ $displaystyle f_{uv}\leq c_{$ }에 대해 $}$
흐름 보존: $s$ $\displaystyle$ s와 $s$ t $\displaystyle$ t $($ 각각 소스 및 싱크)를 제외한 각 $정점$ v $\displaystyle$ v에 $v$ 대해 다음과 같은 동등성이 유지된다.
$(\displaystyle \sum \sum \sum \sum \sumimits _{uv}=\sum \sum \sum \sum \simits _{w:(v,w)\}f_{vw}).}$

흐름은 각 가장자리의 방향에 따라 네트워크를 통과하는 유체의 물리적 흐름으로 시각화할 수 있습니다.다음으로 용량 제약조건은 단위시간당 각 에지를 통과하는 볼륨이 에지의 최대 용량보다 작거나 같다고 하며 보존 제약조건은 소스 및 싱크 정점을 제외하고 각 정점으로 유입되는 양이 각 정점에서 유출되는 양과 동일하다고 합니다.

흐름의 값은 다음과 같이 정의됩니다.

f =\sum \sum \sum \sumimits _{v:(s,v)\in E\}f_{vt} f_{sum \sum \simits _{v}

$s$ 의 s $\displaystyle$ s는 $s$ 소스이고 $\displaystyle$ t는 $t$ 네트워크의 싱크입니다.유체 유추에서, 이것은 소스의 네트워크에 유입되는 유체의 양을 나타냅니다.흐름의 보존 공리를 위해 이는 싱크에서 네트워크를 나가는 흐름의 양과 동일합니다.

최대 흐름 문제는 특정 네트워크에서 가장 큰 흐름을 요구합니다.

최대 흐름 문제f $displaystyle$ f $|f|$ 를 최대화합니다.즉 $,$ s{ $displaystyle$ s $}$ 에서 $s$ t ${displaystyle$ t $t$ 으)로 가능한 한 많은 플로우를 라우팅합니다.

절단

max-flow min-cut 정리의 나머지 절반은 네트워크의 다른 측면, 즉 컷의 수집을 참조합니다.s-t $절단$ C = ( $S,$ $T)$ 는 s $s$ S $및$ t $t$ T가 $되도록$ $V$ 의 분할이다.즉, s-t 컷은 네트워크의 정점을 2개의 부분으로 분할하는 것으로, 한쪽 부분에는 소스가, 다른 한쪽에는 싱크가 있습니다. $컷$ C의 컷 $X_{C}$ X $(\$ X_ ${C})$ 는 $X_{C}$ 컷의 소스 부분과 싱크 부분을 연결하는 가장자리 세트입니다.

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

따라서 C의 $컷$ 세트 내의 모든 에지가 제거되면 소스로부터 싱크까지의 결과 그래프에 경로가 없기 때문에 양의 흐름은 가능하지 않습니다.

s-t 절단 용량은 절단 세트에 있는 가장자리 용량의 합이다.

c(S,T)=\sum \sum X_{C}}c_{uv}=\sum \sum \sum \simits_{ij}d_{ij}

$d_{ij}=1$ 서 d $d_{ij}=1$ $d_{ij}=1$ $=$ 1 ({ $displaystyle$ $d_$ {ij $}=1$ ) ( $i$ $j\in T$ $j\in T$ { $displaystyle$ i $\in$ S $i\in S$ } 및 $i\in S$ $0$ j $j\in T$ T { $displaystyle$ j $\$ $in$ T $j\in T$ }, $0$ { displaystyle 0 ）。

그래프에는 일반적으로 많은 절단 부분이 있지만 가중치가 작은 절단 부분을 찾기가 더 어렵습니다.

최소 s-t 절단 문제.c

(S,

T)

를

최소화

한다. 즉, s-t 절단 용량이 최소가 되도록

S

와 T를

결정

한다.

주정리

상기 상황에서는 네트워크를 통과하는 흐름의 값이 s-t컷 용량 이하임을 증명할 수 있으며, 또한 최대값을 가진 흐름과 최소용량을 가진 컷이 존재함을 증명할 수 있습니다.주요 정리는 최대 흐름 값과 네트워크의 최소 컷 용량을 연결합니다.

최대 흐름 최소 컷 정리.s-t 흐름의 최대값은 모든 s-t 컷의 최소 용량과 동일합니다.

예

네트워크의 최대 흐름.각 에지는 f/c로 라벨이 지정되며, 여기서 f는 에지 위의 흐름이고 c는 에지의 용량입니다.흐름 값은 5 입니다.용량이 5인 몇 가지 최소 s-t 컷이 있습니다. 하나는 S={s,p} 및 T={o,q,r,t}입니다.

오른쪽 그림은 네트워크 내의 흐름을 나타내고 있습니다.각 화살표의 숫자 주석은 f/c 형식으로 화살표의 흐름(f)과 용량(c)을 나타냅니다.소스에서 나오는 흐름은 총 5개(2+3=5)이며, 싱크(2+3=5)로 들어가는 흐름도 마찬가지로 흐름의 값이 5임을 나타냅니다.

값이 5인 s-t 컷은 S={s,p} 및 T={o,q,r,t}에 의해 주어진다.이 절단부를 가로지르는 가장자리 용량은 3과 2로, 절단 용량은 3+2=5입니다.(O에서 p까지의 화살표는 T에서S를 가리키기 때문에 고려되지 않습니다).

흐름의 값은 컷의 용량과 같으며, 흐름은 최대 흐름이고 컷은 최소 컷임을 나타냅니다.

S와 T를 연결하는 2개의 화살표 각각을 통과하는 흐름은 최대 용량입니다.이것은 항상 마찬가지입니다.최소한의 컷은 시스템의 '병목'을 나타냅니다.

선형 프로그램 공식화

max-flow 문제와 min-cut 문제는 2개의 primal-dual 선형 프로그램으로 ^[2]공식화할 수 있습니다.

	최대 흐름(프라이머리)	최소 컷(듀얼)
변수	$f_{uv}$ $\displaystyle \forall (u,v)\in E}$ [변수/에지]	$d_{uv}$ $\displaystyle \forall (u,v)\in E}$ [변수/에지] $z_{v}$ $\displaystyle \forall v\in V\setminus \{s,t\}$ [단말기 노드별 변수]
객관적으로	최대화 $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ v $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ : $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ ( $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ , $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ v ) $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ f s $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ \ $\sum \nolimits _{v:(s,v)\in E}f_{sv}$ _ { $v$ : ( $s$ , $v$ ) \ $in$ E $}f$ _ { $sv$ } [소스로부터의 최대 총 흐름]	$\sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}$ minimize ( $\sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}$ , $\sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}$ v ) $\sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}$ $\sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}$ c v $\sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}$ $\sum \nolimits _{(u,v)\in E}c_{uv}d_{uv}$ \ $displaystyle \sum$ \ $nolimits$ _ { ( $u$ , $v$ ) \ $in$ E } $c$ _ { $uv$ } $d$ _ { $uv$ } [컷된 모서리 총 용량 최소]
제약	의 영향을 받는. ${signed}f_{uv}&\leq c_{uv}&\forall(u,v)\sum_{uv}-\sum_{w}f_{vw}&=0&v\in V\setminus\{s,t\}\endaligned$ [에지당 구속조건 및 비터미널 노드당 구속조건]	의 영향을 받는. $\displaystyle { begin { aligned }d_{u}-z_{v}&\geq 0&\forall (u,v)\in E,u\neq s,v\neq t\d_{v}+z_{v}&\geq 1&\forall (s,v)\neq 0&\in.$ [에지당 구속력]
부호 제약	$(\displaystyle\begin{aligned}f_{uv}&\geq 0&\forall(u,v)\in E\\end{aligned})$	$\displaystyle \begin{aligned}d_{uv}&\geq 0&\forall (u,v)&\in \mathbb {R}&\in V\setminus \{s,t\}\end{aligned}}$

max-flow LP는 간단합니다.듀얼 LP는 듀얼 선형 프로그램에서 기술된 알고리즘을 사용하여 얻어집니다. 듀얼의 변수와 부호 제약은 프라이멀의 제약에 대응하고 듀얼의 제약은 프라이멀의 변수와 부호 제약에 대응합니다.결과 LP에는 설명이 필요합니다.Min-cut LP의 변수 해석은 다음과 같습니다.

d_{uv}=cases}1,&{\text{if}}}u\in S{\text{및}}v\in T{\text{\text}}}\0,&{\text{cases}}}}}\in T{\text{\cases}}

\displaystyle z_{v}=sys{case}1,\text{if}}v\in S\0,\text{othery}}\end{case}}

최소화 목표는 절단에 포함된 모든 모서리의 용량을 합산합니다.

이러한 제약은 변수가 실제로 법적 ^[3]삭감을 나타내는 것을 보증합니다.

$d_{uv}-z_{u}+z_{v}\geq 0$ $d_{uv}-z_{u}+z_{v}\geq 0$ $d_{uv}\geq z_{u}-z_{v}$ v $d_{uv}-z_{u}+z_{v}\geq 0$ - $d_{uv}-z_{u}+z_{v}\geq 0$ + $d_{uv}-z_{u}+z_{v}\geq 0$ $d_{uv}-z_{u}+z_{v}\geq 0$ 0 { $d_{uv}\geq z_{u}-z_{v}$ d $_$ { $d_{uv}-z_{u}+z_{v}\geq 0$ $d_{uv}\geq z_{u}-z_{v}$ } - $z$ $d_{uv}\geq z_{u}-z_{v}$ { $v$ $d_{uv}\geq z_{u}-z_{v}$ + z _ { $v$ $d_{uv}\geq z_{u}-z_{v}$ \ $geq$ 0 （ $displaystyle d$ { $uv}$ \ geq $z$ _ { $u$ - z _ { $v}$ ）는 비 터미널 노드 u에 대해 다음과 같이 보증합니다. $eq$ 1 $d_{uv}\geq 1$ ） $d_{uv}\geq 1$ 。
$d_{sv}+z_{v}\geq 1$ s $d_{sv}+z_{v}\geq 1$ + $d_{sv}+z_{v}\geq 1$ v $d_{sv}+z_{v}\geq 1$ $d_{sv}+z_{v}\geq 1$ { $displaystyle$ d $_$ { $sv$ } + $z$ $d_{sv}\geq 1-z_{v}$ { $v$ $d_{sv}\geq 1-z_{v}$ \ $geq$ 1 $（$ $displaystyle d$ { $sv$ }\ $geq 1-z$ _ { $v$ }}) 제약조건에 따라 v가 T에 있는 경우 엣지(s, v)가 (s, v)에 의해 컷 S에 카운트됩니다.
제약 $d_{ut}-z_{u}\geq 0$ $d_{ut}-z_{u}\geq 0$ $d_{ut}-z_{u}\geq 0$ t $d_{ut}-z_{u}\geq 0$ - $d_{ut}-z_{u}\geq 0$ u $d_{ut}-z_{u}\geq 0$ 0 { { $displaystyle$ d $_$ { $ut$ } - $z$ _ { $u}$ \ $geq$ 0 $d_{ut}-z_{u}\geq 0$ } $d_{ut}-z_{u}\geq 0$ ( $d_{ut}\geq z_{u}$ $d_{ut}\geq z_{u}$ $d_{ut}\geq z_{u}$ $d_{ut}\geq z_{u}$ u ${$ $displaystyle d_{ut}$ \ $geq z_{u$ )는 u가 S에 있는 경우 엣지(u, t)가 (정의에 의해)에 카운트됨을 보증합니다.

이것은 최소화의 문제이기 때문에 에지가 컷에 없는 것을 보증할 필요는 없습니다.컷에 있어야 할 각 에지가 목표 함수에 합산되어 있는 것만 보증하면 됩니다.

max-flow min-cut 정리에서의 등식은 선형 프로그래밍의 강력한 이중성 정리로부터 따르며, 선형 프로그래밍에서는 원시 프로그램이 최적 솔루션 x*를 가지면, 이중 프로그램 또한 최적 솔루션 y*를 가지며, 두 솔루션에 의해 형성된 최적 값이 동일하다는 것을 나타냅니다.

어플

세더바움의 최대 유량 정리

최대 흐름 문제는 비선형 저항 ^[4]소자로 구성된 네트워크를 통해 전류를 최대화하는 것으로 공식화할 수 있습니다.이 공식에서 $입력전압 in$ V가 $δ$ 에 가까워질 때 전기네트워크 입력단자 사이의 $전류 in$ I의 한계는 최소 중량 컷 $세트$ 의 무게와 동일합니다.

\displaystyle \lim _{\text{in}}\to \infty }(I_{in})=\min _{X_{C}\sum _{(u,v)\in X_{C}c_{uv}\sum

일반화 최대 흐름 최소 컷 정리

에지 용량 외에 각 정점에 용량이 있다고 간주합니다. 즉, $c:V\to \mathbb {R} ^{+}$ c : $c:V\to \mathbb {R} ^{+}$ $c:V\to \mathbb {R} ^{+}$ + {\ $display style$ c $:$ $흐름$ f가 c $(v)$ 로 $표시$ 되는 V $\to \mathbb {R}$ ^{+}은 $c:V\to \mathbb {R} ^{+}$ 용량 제약 및 흐름 보존뿐만 아니라 정점 용량 제약도 충족해야 합니다.

\displaystyle \forall v\in V\s,t\:\qquad \sum \nolimits _{\in V\mid (u,v)\}f_{uv}\leq c(v)입니다.}

즉, 정점을 통과하는 흐름의 양은 정점의 용량을 초과할 수 없습니다.s에서 t까지의 경로에 대해 경로에 절단의 멤버가 포함되도록 s-t 절단을 정점과 모서리 집합으로 정의합니다.이 경우 절단 용량은 절단된 각 모서리와 정점의 용량을 합한 것입니다.

이 새로운 정의에서 일반화 max-flow min-cut 정리는 s-t 흐름의 최대값이 새로운 의미에서 s-t 컷의 최소 용량과 동일함을 나타낸다.

멩거의 정리

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

Menger's 정리는 무방향 그래프의 에지-분리 s-t 경로의 최대 수가 s-t 컷 세트의 최소 에지 수와 동일하다는 것을 나타냅니다.

프로젝트 선택 문제

최적의 솔루션을 사용한 프로젝트 선택 문제의 네트워크 공식화

프로젝트 선택 문제에는 n개의 $프로젝트$ 와 m개의 기계가 $있습니다$ .각 $프로젝트 i$ p는 $수익$ r $(p i)$ 을 산출하고 각 $머신 j$ q는 $구입비용$ c $(q j)$ 를 들 수 있다.각 프로젝트에는 다수의 머신이 필요하며 각 머신은 여러 프로젝트에서 공유할 수 있습니다.문제는 수익 극대화를 위해 어떤 프로젝트와 기계를 각각 선택하고 구입해야 하는지를 결정하는 것입니다.

P가 선택되지 않은 프로젝트 $세트$ 이고 Q가 구입한 기계 세트라고 $가정$ 하면 다음과 같이 문제를 공식화할 수 있습니다.

\displaystyle \max\{g\}=\sum _{i}r(p_{i}),\sum _{p_{i}\in P}r(p_i}),\sum _{q_{j}c(q_{j})}

첫 번째 항은 $P$ 와 Q의 $선택$ 에 의존하지 않기 때문에, 이 최대화 문제는 대신 최소화 문제로 공식화할 수 있습니다. 즉, 다음과 같습니다.

\displaystyle \min\{g'\}=\sum _{i}\in P}r(p_{i})+\sum _{q_{j}\in Q}c(q_{j}).}

위의 최소화 문제는 $capacity$ r $(p i)$ 의 프로젝트에 소스가 접속되고 $capacity$ c $(q j)$ 의 머신에 의해 sink가 접속되는 네트워크를 구축함으로써 최소 컷 문제로 공식화할 수 있습니다. $프로젝트 i$ p가 $머신 j$ q를 필요로 하는 경우에는 무한 용량의 에지 $(p i j,$ q)를 추가한다.s-t 컷 세트는 프로젝트와 기계를 각각 $P$ 와 Q로 $나타냅니다$ .max-flow min-cut 정리에 의해 최대 흐름 문제로서 해결할 수 있다.

오른쪽 그림은 다음 프로젝트 선택 문제의 네트워크 공식입니다.

	$프로젝트$ r $(p i)$	$머신$ c $(q j)$
1	100	200	프로젝트 1에는 머신1과 머신2가 필요합니다.
2	200	100	프로젝트 2에는 머신 2가 필요합니다.
3	150	50	프로젝트 3에는 머신 3이 필요합니다.

s-t 삭감의 최소 용량은 250이고 각 프로젝트의 수익 합계는 450입니다. 따라서 $프로젝트 2$ $p$ 와₃ p를 선택하면 최대 이익 g는 450 - 250 = 200입니다.

여기서의 아이디어는 각 프로젝트의 수익을 기계의 '파이프'를 통해 '흐름'하는 것입니다.기계에서 파이프를 채울 수 없는 경우 기계의 수익률은 비용보다 낮아지고, 최소 컷 알고리즘은 기계의 비용 에지 대신 프로젝트의 수익 에지를 줄이는 것이 더 저렴하다는 것을 알게 됩니다.

이미지 분할 문제

각 검은 노드는 픽셀을 나타냅니다.

영상 분할 문제에는 n개의 픽셀이 $있습니다$ .각 $화소$ i에는 $전경값 i$ f 또는 $배경값 i$ b를 할당할 수 있다. $픽셀$ i, $j$ 가 인접해 있고 할당이 다른 경우 $p$ 의_ij 패널티가 발생합니다.문제는 픽셀 값에서 패널티를 뺀 합계가 최대가 되도록 픽셀을 포그라운드 또는 백그라운드에 할당하는 것입니다.

P를 전경에 할당된 픽셀 집합으로 $하고$ Q를 배경에 할당된 포인트 집합으로 $하면$ 다음과 같이 문제를 공식화할 수 있습니다.

\displaystyle \max\{g\}=\sum _{i\in P}f_{i}+\sum _{i\in Q}b_{i}-\sum _{i\in P,j\lor j\in Q}p_{ij}.}

이 최대화 문제는 대신 최소화 문제로 공식화할 수 있습니다. 즉, 다음과 같습니다.

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

상기 최소화 문제는 소스(주황색 노드)가 $용량 i$ f의 모든 픽셀에 접속되고 싱크(보라색 노드)가 $용량 i$ b의 모든 픽셀에 접속되는 네트워크를 구축함으로써 최소 컷 문제로 공식화할 수 있다.인접한 2개의 화소 사이에 $p용량$ 의_ij 2개의 엣지( $i, j$ , i)와 ( $j, i$ )를 추가한다.그런 다음 s-t 컷 세트는 전면에 할당된 픽셀( $P$ )과 배경에 할당된 픽셀(Q)을 나타냅니다.

역사

1962년 ^[5]포드와 풀커슨에 의해 다음과 같은 정리가 발견되었다.

「아크의 용량 제한이 있는 네트워크상에서, 1 포인트로부터 다른 포인트로의 최대 안정 상태 플로우를 결정하는 것은, 1955년 봄에 T.E.에 의해서 작성자에게 제시되었습니다.General F. S. Ross (Ret)와 함께, 철도 교통 흐름의 단순화된 모델을 공식화했고, 이 모델에 의해 제안된 중앙 문제로서 특정 문제를 지적하였습니다.그 후 얼마 지나지 않아 우리가 최대 흐름 최소 컷 정리라고 부르는 정리 5.1이 추측되고 ^[6]확립되었다.그 후 많은 증거가 나타났다.^[7]^[8]^[9]

증명

$G$ = ( $V,$ $E)$ 를 네트워크(방향 그래프)로 $하고$ , $s$ 와 t를 각각 $G$ 의 소스 및 싱크라고 한다.

Ford-Fulkerson 알고리즘에 의해 G에 $대해$ 계산된 $흐름$ f를 고려합니다.(Ford-Fulkerson 알고리즘에 의한 최종 흐름 할당 후) G에 $대해$ 얻은 잔차 그래프 $(G f)$ 에서 다음과 같이 정점의 2개의 서브셋을 정의한다.

$A$ : $G$ 의_f s에서 $도달$ 가능한 정점 집합
$A c$ : 나머지 정점 집합. $V - A$

Claim. $value(f$ ) = $c (A,$ $A c)$ 이며, 여기서 s-t 절단 용량은 다음과 같이 정의된다.

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

(

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

,

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

)

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

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

( （

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

, v

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

）

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

s

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

×

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

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

u

v \

display c

( S , T ) = \ sum \

simits

_ { (

u

, v ) \

in S

\

times

T }

c

_ {

uv

} 。

이제 정점 $A$ 의 서브셋에 $value(f)=f_{out}(A)-f_{in}(A)$ v $value(f)=f_{out}(A)-f_{in}(A)$ $value(f)=f_{out}(A)-f_{in}(A)$ e ( $value(f)=f_{out}(A)-f_{in}(A)$ ) $value(f)=f_{out}(A)-f_{in}(A)$ $value(f)=f_{out}(A)-f_{in}(A)$ $value(f)=f_{out}(A)-f_{in}(A)$ t ( $value(f)=f_{out}(A)-f_{in}(A)$ ) - $value(f)=f_{out}(A)-f_{in}(A)$ ( $value(f)=f_{out}(A)-f_{in}(A)$ ) { $displaystyle$ value ( f ) = $f$ _ { $out$ } ( $A$ ) - $f$ _ { $in$ } ( $A$ ) 。따라서 값 $(f)$ = $c (A,$ $A c)$ 의 $경우$ 다음이 필요합니다.

절단부에서 나오는 모든 가장자리가 완전히 포화 상태여야 합니다.
컷으로 들어오는 모든 가장자리의 유량이 0이어야 합니다.

위의 주장을 증명하기 위해 우리는 두 가지 경우를 고려합니다.

$G$ 에는 발신 에지 $(x,y),x\in A,y\in A^{c}$ ), $(x,y),x\in A,y\in A^{c}$ A $(x,y),x\in A,y\in A^{c}$ y $(x,y),x\in A,y\in A^{c}$ A, y $(x,y),x\in A,y\in A^{c}$ A c $(x,y),x\in A,y\in A^{c}$ c c c c { $display style (x,y),x\in$ A $,y\in$ A $^{c}$ 가 $(x,y),x\in A,y\in A^{c}$ 존재합니다.즉, f $(x, y)$ < $c xy$ 는, 패스 S 에 $x f$ 에서 y 로의 전방 에지가 존재하는 것을 의미합니다.따라서 모든 발신 에지 $(x,$ $y)$ 가 완전히 포화됩니다.

$G$ 에는 착신 $(y,x),x\in A,y\in A^{c}$ x $(y,x),x\in A,y\in A^{c}$ $(y,x),x\in A,y\in A^{c}$ $,$ $(y,x),x\in A,y\in A^{c}$ A $,$ y, $A, y, in$ A^{ $c})$ 가 $(y,x),x\in A,y\in A^{c}$ 존재합니다.이러한 에지는, 제로 이외의 플로우( $즉,$ f( $y, x)>$ 0)를 반송합니다.따라서 G에는 $x에서y$ 로의_f $후방$ 엣지가 존재하는 것을 의미합니다.따라서 모든 착신 에지 $(y,$ $x)$ 에는 0 플로우가 필요합니다.

위의 두 문장은 위에서 설명한 방법으로 얻을 수 있는 컷 용량이 네트워크에서 얻을 수 있는 흐름과 동일함을 증명합니다.또, Ford-Fulkerson 알고리즘에 의해서 플로우가 취득되었기 때문에, 네트워크의 최대 플로우이기도 합니다.

또한 네트워크 내의 흐름은 항상 네트워크 내의 가능한 모든 컷 용량보다 작거나 같기 때문에 위의 컷은 max-flow를 얻는 min-cut이기도 합니다.

이 증명의 결과로 그래프 절단 내의 가장자리 세트를 통과하는 최대 흐름은 이전의 모든 절단된 부분의 최소 용량과 동일합니다.

「」를 참조해 주세요.

레퍼런스

^ Dantzig, G.B.; Fulkerson, D.R. (9 September 1964). "On the max-flow min-cut theorem of networks" (PDF). RAND Corporation: 13. Archived from the original (PDF) on 5 May 2018.
^ Trevisan, Luca. "Lecture 15 from CS261: Optimization" (PDF).
^ Keller, Orgad. "LP min-cut max-flow presentation".
^ Cederbaum, I. (August 1962). "On the optimal operation of communication nets". Journal of the Franklin Institute. 274: 130–141.
^ L. R. Ford Jr. & D. R. Fulkerson (1962) 네트워크 흐름, 1페이지, Princeton University Press MR01500
^ L. R. 포드 주니어와 D.R. Fulkerson(1956) "네트워크를 통한 최대 흐름", 캐나다 수학저널 8: 399-404
^ P. Elias, A.Feinstein, 및 C. E. Shannon(1956) "네트워크를 통과하는 최대 흐름에 대한 메모", IRE.정보이론 거래, 2(4): 117~119
^ 조지 단치히와 D.R. Fulkerson(1956) "네트워크의 최대 흐름 MinCut 정리에 대하여", 선형 부등식, 앤.수학. 연구 38번, 프린스턴, 뉴저지
^ L. R. Ford & D. Fulkerson(1957) "최대 네트워크 흐름과 히치콕 문제에 대한 응용을 찾는 단순한 알고리즘", 캐나다 수학 저널 9: 210–18

Eugene Lawler (2001). "4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem". Combinatorial Optimization: Networks and Matroids. Dover. pp. 117–120. ISBN 0-486-41453-1.
Christos H. Papadimitriou, Kenneth Steiglitz (1998). "6.1 The Max-Flow, Min-Cut Theorem". Combinatorial Optimization: Algorithms and Complexity. Dover. pp. 120–128. ISBN 0-486-40258-4.
Vijay V. Vazirani (2004). "12. Introduction to LP-Duality". Approximation Algorithms. Springer. pp. 93–100. ISBN 3-540-65367-8.

[1] Dantzig, G.B.; Fulkerson, D.R. (9 September 1964). "On the max-flow min-cut theorem of networks" (PDF). RAND Corporation: 13. Archived from the original (PDF) on 5 May 2018.

[2] Trevisan, Luca. "Lecture 15 from CS261: Optimization" (PDF).

[3] Keller, Orgad. "LP min-cut max-flow presentation".

[4] Cederbaum, I. (August 1962). "On the optimal operation of communication nets". Journal of the Franklin Institute. 274: 130–141.

[5] L. R. Ford Jr. & D. R. Fulkerson (1962) 네트워크 흐름, 1페이지, Princeton University Press MR01500

[6] L. R. 포드 주니어와 D.R. Fulkerson(1956) "네트워크를 통한 최대 흐름", 캐나다 수학저널 8: 399-404

[7] P. Elias, A.Feinstein, 및 C. E. Shannon(1956) "네트워크를 통과하는 최대 흐름에 대한 메모", IRE.정보이론 거래, 2(4): 117~119

[8] 조지 단치히와 D.R. Fulkerson(1956) "네트워크의 최대 흐름 MinCut 정리에 대하여", 선형 부등식, 앤.수학. 연구 38번, 프린스턴, 뉴저지

[9] L. R. Ford & D. Fulkerson(1957) "최대 네트워크 흐름과 히치콕 문제에 대한 응용을 찾는 단순한 알고리즘", 캐나다 수학 저널 9: 210–18

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search

최대 흐름 최소 컷 정리

네임스페이스

더

목차

정의 및 스테이트먼트

네트워크

플로우

절단

주정리

예

선형 프로그램 공식화