우리가 한 점에서 다른 곳으로 가는 최단 경로를 찾기 위해 directed graph로 road map을 모델링할 수 있는 것처럼, 우리는 또한 directed graph를 "flow network"로 해석할 수 있고, material flows에 대한 질문에 답하기 위해 그것을 사용할 수 있다. material이 생산되는 한 source로부터 그것이 소비되는 sink까지 한 시스템을 거쳐서 돌아다니는 한 material을 상상해라. 그 source는 어떤 꾸준한 비율로 그 material을 생산하고, sink는 같은 비율로 그 material로 소비한다. 그 시스템에서 어떤 점에서 material의 "flow"는 직관적으로 그 material이 움직이는 비율이다. Flow networks는 많은 문제들을 모델링할 수 있다, 파이프를 통해 흘러다니는 액체, 조립 라인을 통과하는 부품들, 전자 네트워크를 통한 흐름, 커뮤니케이션 네트워크를 통한 정보들을 포함해서.
우리는 flow network에서 각 directed edge를 그 material에 대한 conduit(도관, 전선관, 전달자)로 생각할 수 있다. 각 conduit는 명시된 capacity를 갖는데, 그 material이 conduit을 통해서 흐를 수 있는 최대 비율로서 주어진다, 한 파이프당 시간당 200갤런의 액체 또는 한 와이어당 전자 기류의 20 amperes 같은 것들. 정점들은 conduit junctions(교차로, 나들목)이다. source와 sink를 제외하고, material은 그 정점들을 통해서 그것들이 모이지 않고 흘러간다. 다시 말해서, material이 한 vertex에 들어가는 비율은 그것이 그 정점을 떠나는 비율과 같아야만 한다. 우리는 이 특징을 "flow conservation"라고 부른다. 그리고 이것은 material이 electrical current일 때 Kirchhoff의 current law와 같다.
maximum-flow problem에서, 우리는 우리가 source에서 sink까지 어떠한 capacity 제약을 위반하지 않고 material을 배송할 수 있는 가장 큰 비율을 연산하기 원한다. 그것은 flow networks와 관련된 가장 간단한 문제들 중 하나이고, 이 챕터에서 보게 되듯이, 이 문제는 효율적인 알고리즘들로 해결될 수 있다. 게다가, 우리는 다른 network-flow 문제들을 해결하기 위해 maximum-flow algorithms에서 사용되는 기본적인 기법들을 적응할 수 있다.
이 챕터는 maximum-flow 문제에 대해 두 가지 일반적인 methods들을 보여준다. Section 26.1은 flow networks와 flows의 개념을 공식화하고, 공식적으로 maximum-flow problem을 정의한다. Section 26.2는 maximum flows를 찾는 Ford와 Fulkerson의 고전적인 방법을 설명한다. 이 방법의 응용인, 방향이 없는 bipartite(이분) graph에서 maximum matching을 찾는 것은 Section 26.3에서 나타난다. Section 26.4는 push-relabel method를 보여준다. 그것은 network-flow 문제들에 대해 많은 가장 빠른 알고리즘들에 대한 기저가 된다. Section 26.5는 "relabel-to-front" 알고리즘을 다루는데, O(V^3)의 시간에 작동하는 push-relabel method의 특별한 구현이다. 비록 이 알고리즘이 알려진 가장 빠른 알고리즘은 아닐지라도, 그것은 asymptotically하게 가장 빠른 알고리즘에서 사용되는 몇 가지 기법들을 보여주고, 그리고 그것은 실제로 합리적으로 효율적이다.
26.1 Flow Networks
이 섹션에서, 우리는 flow networks의 그래프 이론적인 정의를 주고, 그것들의 특징을 이야기하고, maximum-flow problem을 정확히 정의한다. 우리는 또한 몇 가지 도움이 되는 표기를 도입한다.
Flow networks and flows
flow network G = (V, E) 는 directed graph인데, 거기에서 E에 있는 각 edge (u, v)는 음이 아닌 capacity c(u, v) >= 0을 가지고 있다. 우리는 더욱이 만약 E가 한 edge(u, v)를 포함한다면, 반대 방향의 edge(v, u)가 없다는 것을 요구한다. (우리는 이 제한으로 어떻게 작업하는지를 곧 보여줄 것이다). 만약 (u, v)가 E에 없다면, 그러면 편리성을 위해, 우리는
c(u, v) = 0라고 정의하고, 우리는 self-loops를 허용하지 않는다. 우리는 flow network에서 두 가지 정점들을 구분한다: source s 와 sink t. 편리성을 위해서, 우리는 각 정점이 source에서 sink로 가는 어떤 경로에 놓여있다고 가정한다. 즉, V에 있는 각 정점 v에 대해, 그 flow network는 s -> v -> t로 가는 한 경로를 포함한다. 그 그래프는 그러므로 연결되어 있고, s를 제외한 각 정점이 적어도 한 개의 들어오는 간선을 갖기 때문에, |E| >= |V| - 1이게 된다. 그림 26.1은 flow network의 한 예시를 보여준다.
우리는 이제 flows를 좀 더 공식적으로 정의할 준비가 되었다. G = (V, E)를 capacity function c가 있는 flow network라고 하자. s가 network의 source라고 하고, t가 sink라고 하자. G에서 flow는실수 값 함수 다음의 두 가지 특성들을 만족시키는 f : V x V -> R 이다:
Capacity constraint : V에 있는 모든 u, v에 대해, 우리는 0 <= f(u, v) <= c(u,v)를 요구한다.
Flow conservation : V - {s, t}에 있는 모든 u에 대해, 우리는
(u, v)가 E에 없을 때, u에서 v로가는 어떠한 flow도 없다, 그래서 f(u, v) = 0이다.
우리는 음이 아닌 quantity f(u, v)를 정점 u에서 v로 가는 flow라고 부른다. 한 flow f의 그 value |f|는 다음으로 정의된다
즉, "source에서 나가는 total flow" - "source로 들어가는 flow" 이다. (여기에서, | | notation은 flow value를 표기하고, 절대값 또는 기수가 아니다.) 일반적으로, flow network는 source로 들어가는 어떠한 간선도 갖지 않을 것이고, 그 합 sigma_{v in V} f(v,s)에 주어진 source로 들어가는 flow는 0이 될 것이다. 그러나 우리는 그것을 포함시키는데, 왜냐하면 우리가 이 챕터에서 나중에 residual(남은, 잔여의) networks를 도입할 때, source로 들어가는 flow가 중요해질 것이다. maximum-flow problem에서, 우리는 source s와 sink t가 있는 flow network G가 주어지고, 우리는 maximum value의 한 flow를 발견하기를 원한다.
network-flow problem의 한 예제를 보기전에, 간단히 flow의 정의와 두 가지 flow 특성을 탐험해보자. 그 capacity constraint은 한 정점에서 다른 것으로 가는 flow가 음이 아니여야 하고, 주어진 capacity를 초과해서는 안된다는 것을 간단히 말한다. 그 flow-conservation 특성은 source 또는 sink를 제외한 한 정점으로 들어가는 total flow는 그 정점에서 나가는 total flow와 같아야만 한다 - 비격식적으로 "flow in equals flow out" (흘러들어 오는 것과 흘러 나가는 것은 같다)
An example of flow
힌 flow network는 그림 26.1(a)에서 보여지는 trucking 문제를 모델링할 수 있다. 그 Lucky Puck Company는 하키 퍽을 제조하는 밴쿠버에 공장 (source s)를 가지고 있고, 그것은 그것을 저장하는 Winnipeg에 창고 (sink t)를 가지고 있다. Lucky Puck은 공장에서 창고로 퍽들을 배송하기 위해 다른 회사로부터 트럭들에 있는 공간을 임대한다. 도시들 (정점들) 사이에 있는 명시된 루트들(간선들)로 트럭들이 이동하고, 제한된 capacity를 갖기 때문에, Lucky Puck은 그림 26.1(a)에서 도시들 u와 v의 각 쌍 사이에 하루에 최대 c(u,v)의 crates들을 배송할 수 있다. Lucky Puck은 이러한 루트와 capacities에 대해 어떠한 통제력이 없다, 그래서 그 회사는 그림 26.1(a)에 보여지는 flow network를 수정할 수 없다. 그들은 그들이 배송할 수 있는 하루에 최대 creates 개수 p를 결정할 필요가 있고, 그런 다음에 이 양을 생산할 필요가 있다. 왜냐하면 그들의 창고에 배송할 수 있는 좀 더 많은 지점이 없기 떄문이다. Luck Puck은 주어진 puck이 공장에서 창고로 가는데 얼마나 걸리든 걱정하지 않는다; 그들은 오직 하루 당 p개의 crates가 공장을 떠나서 창고에 하루에 p개의 crates가 도착하기만을 신경쓴다.
우리는 이 네트워크에서 한 flow를 가진 배송의 "flow"를 모델링할 수 있는데, 왜냐하면 한 도시에서 다른 곳으로 하루에 배송되는 crates의 개수가 capacity constraint에 종속되기 때문이다. 부가적으로, 그 모델은 flow conservation을 따라야 한다, 꾸준한 상태에서, puck이 중간 도시에 들어가는 비율은 그것들이 떠나는 비율과 같아야 한다. 만약 그렇지 않다면, crates는 중간 도시에 축절될 것이다.
Modeling problems with antiparallel edges
트럭 회사가 Lucky Puck에게 Edmonton에서 Calgary로 가는 트럭에 10개의 crates를 위한 공간을 임대하는 기회를 제안했다고 가정하자. 우리의 예제에 이 기회를 추가하고 그림 26.2(a)에 보이는 network를 만드는 것은 당연한 것처럼 보일 것이다. 그러나 이 네트워크는 한 가지 문제를 겪는다: 그것의 만약 E에 있는 한 간선 (v_1, v_2)가 있다면, (v_2, v_1)은 E에 없어야 한다는 우리의 원래 가정에 위반된다. 우리는 그 두 개의 간선들 (v_1, v_2)와 (v_2, v_1)을 antiparallel하다고 부른다. 따라서, 만약 우리가 antiparallel edges를 가진 flow problem을 모델링하고 싶다면, 우리는 그 네트워크를 어떠한 antiparallel edges를 포함하지 않는 동등한 것으로 변환해야만 한다. 그림 26.2(b)는 이 같은 네트워크를 보여준다. 우리는 그 두 개의 (v_1, v_2) 케이스에서 antiparallel egdes 중의 하나를 고르고, 하나의 새로운 정점 v'를 도입하고 간선 (v_1, v_2)를 (v_1, v')와 (v', v_2)의 쌍으로 바꾸어서 그것을 쪼갠다. 우리는 또한 두 개의 새로운 간선들의 capacity를 원래 edge의 capacity로 설정한다. 그 최종 network는 만약 한 edge가 네트워크에 있다면, reverse edge가 없다는 특성을 만족시킨다. Exercise 26.1-1는 너에게 최종 네트워크가 그 원래의 것과 동일한 지를 증명하라고 요청한다.
따라서, 우리는 real-world flow problem이 antiparallel edges가 있는 한 네트워크에 의해 가장 자연스럽게 모델링 되어질 지도 모른다는 것을 알게 된다. 그러나, antiparallel edges가 없도록 하는 것은 편리할 것이다. 그래서 우리는 antiparallel edges를 포함하는 한 네트워크를 antiparallel edges가 없는 동등한 것으로 변환하는 간단한 방법을 가진다.
Networks with multiple sources and sinks
한 maximum-flow problem은 각각 한 개라기 보다는 몇 개의 sources와 sinks를 가질 지도 모른다. 예를들어, Lucky Puck Company는 그림 26.3(a)에서 보여주듯이, 실제로 m개의 공장들 집합 {s_1, ... s_m}과 n개의 창고 집합 {t_1, ... t_n}을 가질지도 모른다. 운 좋게도, 이 문제는 평범한 maximum flow보다 더 어렵지 않다.
우리는 많은 sources와 많은 sinks가 있는 네트워크에서 maximum flow를 결정하는 문제를 평범한 maximum-flow 문제로 줄일 수 있다. 그림 26.3(b)는 (a)의 네트워크를 오직 한 개의 source와 한 개의 sink를 가진 평범한 flow network로 어떻게 바꾸는지를 보여준다. 우리는 각 i = 1,2,...m에 대해 supersource s를 추가하고 capacity c(s, s_i) = ∞를 가진 방향이 있는 edge (s, s_i)를 추가한다. 우리는 또한 i = 1,2,...n 한 새로운 supersink t를 만들고 capacity c(t_i, t) = ∞가 있는 방향이 있는 edge (t_i, t)를 추가한다. 직관적으로, (a)에 있는 네트워크에 있는 어떤 flow는 (b)에 있는 네트워크에 있는 한 flow와 일치한다. 역으로도 그렇다. single source s는 간단히 많은 sources s_i로부터 요구되는 만큼의 많은 flow를 제공하고, 그 single sink t는 마찬가지로 많은 sinks t_i에 대해 요구되는 만큼의 많은 flow를 소비한다. Exercise 26.1-2는 너가 공식적으로 두 문제가 같은 지를 증명하는 것을 요구한다.
26.2 The Ford-Fulkerson method
이 섹션은 maximum-flow problem을 해결하는 Ford-Fulkerson method를 보여준다. 우리는 한 "algorithm"이라기 보다는 한 "method"라고 부른다. 왜냐하면 그것이 다른 작동시간을 가진 몇 가지 구현들을 수반하기 때문이다. Ford-Fulkerson method는 그 method를 초월하고 많은 flow algorithms들과 problems와 관련된 세 개의 중요한 아이디어들에 의존한다 : residual networks, augmenting paths, and cuts. 이러한 아이디어들은 그 중요한 max-flow min-cut 정리에 필수적이다 (정리 26.6), 그리고 이것은 한 maximum flow의 값을 flow network의 cuts의 관점에서 특징화한다. 우리는 Ford-Fulkerson method의 한 특정한 구현을 보여주고 그것의 작동시간을 분석하여 이 섹션을 마무리 한다.
Ford-Fulkerson method는 반복적으로 flow의 value를 증가시킨다. 우리는 V에 있는 모든 u,v에 대해 0의 초기 flow값을 주면서 f(u, v) = 0으로 시작한다. 각 반복에서, 우리는 한 관련된 "residual network" G_f에서 한 "augmenting path"를 찾아서 G에서 flow value를 증가시킨다. 우리가 G_f에서 augmenting path의 간선들을 알기만 한다면, 우리는 쉽게 G에서 우리가 flow의 값을 올릴 수 있도록 그 flow를 바꿀 수 있는 특정한 간선들을 확인할 수 있다. Ford-Fulkerson method의 각 반복이 그 flow의 value를 증가시킬지라도, 우리는 G에서 어떤 특정한 간선에 있는 flow가 증가하거나 또는 감소하는 것을 볼 것이다; 어떤 간선에서 flow를 감소시키는 것은 source에서 sink로 가는 좀 더 많은 flow를 보내는 한 알고리즘을 가능하게 하기 위해 필수적일지도 모른다. 우리는 반복적으로 residual network가 어떠한 더이상의 augmenting paths가 없을 때 까지 그 flow를 augment(확장) 한다. 그 max-flow min-cut 정리는 종료시에 이 프로세스가 maximum flow를 만들어낸다는 것을 보여줄 것이다.
FORD-FULKERSON-METHOD(G, s, t) 1 initialize flow f to 0 2 while there exists an augmenting path p in the residual network G_f 3 augment flow f along p 4 return f
Ford-Fulkerson method를 구현하고, 분석하기 위해서, 우리는 몇 가지 부가적인 개념들을 도입할 필요가 있다.
Residual networks
직관적으로, flow network G와 flow f가 주어진다면, 그 residual network G_f는 G의 간선들에서 우리가 flow를 바꿀 수 있는 방법을 나타내는 capacities를 가진 간선들로 구성된다. flow network의 한 간선은 edge의 capacity와 동일한 부가적인 flow의 양 - 그 edge로 가는 flow를 뺀 것을 받아들인다. 만약 그 값이 양수라면, 우리는 그 간선을
의 "residual capacity"와 함께 G_f에 배치한다. G_f에 있는 G의 유일한 간선들은 좀 더 많은 flow를 받아들일 수 있는 것들이다; flow과 그것들이ㅡ capacity와 같은 그러한 간선들
(u, v)는 c_f(u, v) = 0를 갖고, 그것들은 G_f에 있지 않다.
그러나, residual network G_f는 또한 G에 있지 않는 간선들을 포함할지도 모른다. 한 알고리즘이 그 flow를 조작할 때, total flow를 증가시키려는 목적으로, 그것은 특별한 간선에서 flow를 감소시킬 필요가 있을지도 모른다. G에서 한 간선에서 양수의 flow f(u,v)의 가능한 감소를 나타내기 위해, 우리는 한 간선 (v, u)를 G_f에 residual capacity c_f(v, u) = f(u, v)로 배치한다 - 즉, (u,v)에 반대 방향의 flow를 받아들일 수 있는 간선이다. 이것은 최대 (u,v)에 있는 flow를 취소시킨다. residual network에서 이러한 reverse edges들은 한 알고리즘이 그것이 한 edge를 따라서 이미 보냈던 flow를 다시 보내도록 하게 한다. 한 간선을 따라 flow를 다시 보내는 것은 그 edge에 있는 flow를 줄이는 것과 같다. 그리고 이것은 많은 알고리즘에서 필수적인 연산이다.
좀 더 공식적으로, source s와 sink t가 있는 G = (V, E) flow network를 가지고 있다고 가정하자. f가 G에서 flow라고 하고, V에 있는 정점들의 한 쌍 u, v를 고려하자. 우리는
residual capacity c_f(u,v)를 다음으로 정의한다
(u,v) in E가 (v,u) not in E라는 가정 때문에, 방정식 (26.2)의 정확히 한 케이스가 정점들의 각 ordered pair에 적용된다.
방정식 26.2의 한 예로서, 만약 c(u,v) = 16이고 f(u,v) = 11이라면, 그러면 우리는 edge (u,v)에서 capacity constraint를 초과하기전에 f(u,v)를 c_f(u,v) = 5단위까지 증가시킬 수 있다. 우리는 또한 알고리즘이 v에서 u로가는 flow의 11단위 까지 반환하도록 하는 것을 허용한다. 그러므로, c_f(v,u) = 11이다.
flow network G= (V, E)와 flow f가 주어진다면, f에 의해 만들어지는 G의 residual network는 G_f = (V, E_f)이고, 거기에서
즉, 위에서 약속했듯이, residual network의 각 간선, 또는 residual edge는 0보다 더 큰 flow를 수용할 수 있다. 그림 26.4(a)는 그림 26.1(b)의 flow network G와 flow f를 반복하고, Figure 26.4(b)는 대응되는 residual network G_f를 보여준다. E_f에 있는 간선들은 E에 있는 간선이거나 또는 그것들의 반대이다. 따라서,
|E_f| <= 2|E| 이다.
residual network G_f가 c_f에 의해 주어지는 capacities를 가진 flow network와 유사한 것을 관찰해라. 그것이 flow network의 우리의 정의를 만족시키지 않는다. 왜냐하면 그것은 edge(u,v)와 그것의 역인 (v, u)를 둘 다 포함하기 때문이다. 이 차이를 제외하고, residual network는 flow network와 같은 특성을 갖는다, 그래서 우리는 residual network에 있는 flow를 한 flow를 정의를 만족시키지만 network G_f에서 c_f와 관련하여 정의한다.
residual network에서 한 flow는 원래 flow network에 flow를 더하는 것에 대한 road map이다. 만약 f가 G에서 한 flow이고, f'가 대응되는 residual network G_f에서 한 flow라면, 우리는 f↑f'를 f'로 flow f를 augmentation이라고 정의한다. 이것은 V X V -> R로 가는 한 함수인데 다음으로 정의된다
(26.4)
이 정의 뒤에 있는 직관은 residual network의 정의를 따른다. 우리는 (u, v)에 있는 flow를 f'(u, v)로 증가시키지만, 그것을 f'(v, u)로 감소시킨다. 왜냐하면 residual network에서 reverse edge에 있는 flow를 push하는 것은 original network에서 그 flow를 감소시키는 것을 나타내기 때문이다. residual network에 있는 reverse edge에 있는 flow를 넣는 것은 또한 cancellation으로 알려져있다. 예를들어, 만약 우리가 u에서 v로가는 hockey pucks의 5개 crates를 보내고, v에서 u로 2개의 crates를 보낸다면, 우리는 동등히 u에서 v로 3개의 crates를 보내고, v에서 u로 아무것도 못보낸다. 이 러한 유형의 Cancellation은 어떠한 maximum-flow algorithm에 중요하다.
Lemma 26.1
G = (V, E)가 source s와 sink t를 가진 flow network라고 하고, f가 G에서 한 flow라고 하자. G_f는 f에 발생하는 G의 residual network이고, f'는 G_f에 있는 한 flow이다. 그러면 방정식 26.4에 정의된 f↑f' 함수는 |f↑f'| = |f| + |f'|인 값을 가진 G에 있는 한 flow이다.
Proof 우리는 처음에 f↑f'가 E에 있는 각 edge에 대해 capacity constraint에 따르고,
V - {s,t}에서 각 정점에 대해 flow conservation을 따른다는 것을 증명한다.
capacity constraint에 대해, (u,v) in E가 있다면, c_f(v,u) = f(u,v)라는 것을 관찰해라. 그러므로, 우리는 f'(v, u) <= c_f(v,u) = f(u,v)이고, 그러므로
(f↑f')(u, v) = f(u,v) + f'(u,v) - f'(v, u) (by 방정식 26.4)
>= f(u,v) + f'(u,v) - f(u,v) (because f'(v,u) <= f(u,v))
= f'(u,v)
>= 0.
게다가,
(f↑f')(u,v)
= f(u,v) + f'(u,v) - f'(v, u) (by 방정식 26.4)
<= f(u,v) + f'(u,v) (because flows are nonnegative)
<= f(u,v) + c_f(u,v) (capacity constraint)
= f(u,v) + c(u,v) - f(u,v) (definition of c_f)
= c(u,v)
flow conservation에 대해, f와 f' 둘 다 flow conservation을 따르기 때문에, 우리는
V - {s, t}에 있는 모든 u에 대해,
Sum_{v in V}((f↑f')(u,v) = Sum_{v in V} ( f(u,v) + f'(u,v) - f'(v,u))
= Sum_{v in V} f(u,v) + Sum_{v in V} f'(u,v) - Sum_{v in V} f'(v,u)
= Sum_{v in V} f(v,u) + Sum_{v in V} f'(v,u) - Sum_{v in V} f'(u,v)
= Sum_{v in V} ( f(v,u) + f'(v,u) - f'(u,v))
= Sum_{v in V} (f↑f')(u,v)
여기에서 세 번째 라인은 flow conservation의 두 번째로부터 온다.
마침내, 우리는 f↑f'의 값을 연산한다. 우리가 G에서 (G_f에서가 아닌) antiparallel 간선들을 허용하지 않은 것을 회상해라. 그리고 V에 있는 각 정점 v에 대해, 우리는 (s,v) 또는 (v,s)의 한 간선이 있다는 것을 안다. 그러나 결코 둘다는 없다. 우리는 V_1 = {v : (s,v) in E}를 s에서 출발하는 간선들을 가진 정점들의 집합으로 정의하고, V_2 = {v : (v,s) in E}를 s로 가는 간선들을 가진 정점들을의 집합으로 정의한다. 우리는 V_1 U V_2 in V를 갖게 되고, 우리가 antiparallel edges를 허용하지 않기 때문에, V_1 ∩ V_2 = Ø이게 된다. 우리는 이제 다음을 연산한다
|f↑f'| = Sum_{v in V}((f↑f')(s,v) - Sum_{v in V}((f↑f')(v,s)
= Sum_{v in V1}((f↑f')(s,v) - Sum_{v in V2}((f↑f')(v,s) (26.5)
여기에서 두 번째 라인이 나오는데, (w,x)가 E에 있지 않다면, (f↑f')(w,x)가 0이기 때문이다. 우리는 이제 f↑f'의 정의를 방정식 (26.5)에 적용하고, 그러고나서 항들의 순서를 조정하고 그룹화 한다 다음을 얻기위해서.
방정식 26.6에서, 우리는 V에 대해 합치기 위해서 모든 네 개의 합계를 확장할 수 있다. 왜냐하면 각 부가적인 항은 0의 값을 갖기 때문이다. (Exercise 26.2-1은 너에게 이것을 공식적으로 증명하라고 요구한다.) 우리는 따라서
Augmenting paths
flow network G = (V, E)가 주어지고, flow f가 주어진다면, augmenting path p는 residual network G_f에서 s에서 t로 가는 간단한 경로이다. residual network 정의에 의해, 우리는 (u,v)와 (v,u)가 원래 flow network G에 어디에 있든지에 capacity constraint를 위반하는 것 없이, augmenting path의 간선 (u, v)에 있는 flow를 c_f(u,v)까지 증가시킬 수 있을지도 모른다.
그림 26.4(b)에서 색칠된 경로는 augmeting path이다. 그림에서 residual network G_f를 하나의 flow network로서 다루어서, 우리는 이 경로에 있는 각 간선을 통해 그 flow를 capacity constraint를 위반하지 않고 4units까지 증가시킬 수 있다. 왜냐하면 이 경로에서 가장 작은 residual capacity는 c_f(v_2, v_3) = 4이기 때문이다. 우리는 augmenting path p에서 각 간선에서 그 flow를 증가시킬 수 있는 최대 양을 p의 residual capacity라고 부른다, 그리고 다음에 의해 주어진다
c_f(p) = min{ c_f (u,v) : (u,v) is on p}.
우리가 Exercise 26.2-7에 증명을 남겨놓은, 다음의 lemma는 위의 주장을 좀 더 정확하게 만든다.
Lemma 26.2
G = (V,E)가 flow network, f가 G에서 flow, p가 G_f에서 augmenting path라고 하자. 한 함수 f_p : V X V -> R을 다음으로 정의하자
그러면, f_p는 |f_p| = c_f(p) > 0을 가진 G_f에서의 한 flow이다.
다음의 corollary는 만약 우리가 f를 f_p로 증가시킨다면, 우리가 flow 값이 maximum이 더 가까워 지는 G에서의 flow를 얻는다는 것을 보여준다. 그림 26.4(c)는 그림 26.4(a)의 flow f를 그림 26.4(b)에 있는 flow f_p로 증가시킨 결과를 보여준다. 그리고 그림 26.4(d)는 다음의 residual network를 보여준다.
Corollary 26.3
G = (V,E)가 flow network, f가 G에서 한 flow, p가 G_f에서 augmenting path라고 하자. f_p는 방정식 (26.9)에 정의되어있고, f를 f_p로 증가시킨다고 가정하자. 그러면 f↑f_p 함수는
|f↑f_p| = |f| + |f_p| > |f|인 값을 갖는 G에서의 한 flow이다.
Proof Lemma 26.1과 26.2로부터 곧바로 된다.
Cuts of flow networks
Ford-Fulkerson method는 그것이 maximum flow를 찾을 때 까지, augmeting paths를 따라서 flow를 반복적으로 증가시킨다. 어떻게 그 알고리즘이 종료될 때 우리가 실제로 maximum flow를 발견했다고 아는것인가? 우리가 곧 증명할 그 max-flow min-cut theorem은 우리에게 residual network가 어떠한 augmenting path를 포함하고 있지 않다면 한 flow가 maximum이라고 말해준다. 이 정리를 증명하기 위해서, 우리는 처음에 flow network의 cut에 대한 개념을 알아야만 한다.
flow network G = (V, E)의 cut(S,T)는 V를 S와 T = V - S로 분할하는 것인데, s in S이고 t in T가 되게한다. (이 정의는 챕터 23에서 최소 신장 트리에서 우리가 썼던 "cut"의 정의와 유사하다, 여기에서 우리가 방향이 없는 그래프가 아닌 방향이 있는 그래프를 자르고 있는 것을 제외하고, 그리고 우리는 s in S 그리고 t in T라고 주장한다.) 만약 f가 flow라면, 그러면 cut(S,T)를 가로지르는 그 net flow f(S,T)는 다음으로 정의된다
cut(S,T)의 capacity는
한 network의 minimum cut은 capacity가 그 네트워크의 모든 cuts에 대해 최소한이 되는 cut이다.
flow의 정의와 cut의 정의 사이의 비 대칭성은 의도적이고 중요하다. capacity에 대해, 우리는 S에서 T로 가는 간선들의 capacities만을 중요시하고, 반대 방향의 edges를 무시한다. flow에 대해, 우리는 S->T flow - T->S flow 를 고려한다. 이 뺄셈에 대한 이유는 이 섹션에서 나중에 명백해 질 것이다.
그림 26.5는 그림 26.1(b)의 flow network에서 cut ({s,v1,v2}, {v3, v4,t})를 보여준다. 이 cut을 가로지르는 그 net flow는
f(v_1, v_3) + f(v_2, v_4) - f(v_3, v_2) = 12 + 11 - 4 = 19
이 것의 capacity는
c(v_1, v_3) + c(v_2, v_4) = 12 + 14 = 26
다음의 lemma는 어떤 주어진 flow f에 대해, 어떤 cut을 가로지는 net flow는 같고, flow의 값 |f|와 같다는 것을 보여준다.
Lemma 26.4
f가 source s와 sink t를 가진 flow network G에 있는 flow라고 하고, (S, T)가 G의 어떤 cut이라고 하자. 그러면 (S,T)를 가로지르는 net flow f(S,T) = |f|이다.
Proof 우리는 V - {s,t}에 있는 어떤 노드 u에 대해 flow-conservation condition을 다시 쓸 수 있다
방정식 26.1로부터 |f|의 정의를 가져와서, 방정식 (26.11)의 좌변에 더하는 것은 S - {s}에 있는 모든 정점에 대해 합해진 것은 다음을 준다
우변의 합을 전개하고, 항들을 다시 묶으면
V = S U T이기이고, S ∩ T = Ø 이기 때문에, 우리는 V에 대한 각 합계를 S와 T에 대한 합계로 분리할 수 있고 다음을 얻는다..
괄호안의 두 합계는 실제로 같다, 왜냐하면 V에 있는 모든 정점 x와 v에 대해, f(x,y) 항은 각 합계에서 한 번씩 나타나기 때문이다. 그러므로 이러한 합계는 취소되고, 우리는 다음을 갖는다.
|f| = f(S, T)
Lemma 26.4에 대한 한 corollary는 한 flow의 값을 제한하기 위해 cut capacities를 어떻게 사용할 수 있는지를 보여준다.
Corollary 26.5
flow network G에 있는 어떤 flow f의 값이 G의 어떤 cut의 capacity에 의해 제한된다.
Proof (S, T)가 G의 어떤 cut이고, f가 어떤 flow라고 하자. Lemma 26.4와 그 capacity constraint에 의해
|f| = f(S, T) = c(S, T)
Corollary 26.5는 한 네트워크에서 maximum flow의 값이 그 network의 minimum cut의 capacity로 제한된다는 즉각적인 결과를 만들어낸다. 우리가 이제 명시하고 증명할, 중요한 max-flow min-cut 정리는 maximum flow의 값은 사실 minimum cut의 capacity와 동일하다고 말한다.
Theorem 26.6 (Max-flow min-cut theorem)
만약 f가 source s와 sink t가 있는 flow network G = (V,E)에서 한 flow라면, 그러면 그 다음의 조건들은 동치이다:
- f는 G에서 maximum flow이다.
- residual network G_f는 어떠한 augmenting paths를 포함하지 않는다.
- G의 어떤 cut(S,T)에 대해 |f| = c(S,T) 이다.
Proof 1 => 2: 모순을 위해서, f가 G에서 maximum flow지만, G_f는 augmenting path p를 가지고 있다고 가정하자. 그러면 Corollary 26.3에 의해, 방정식 (26.8)에 의해 주어지는 f_p로 f를 증가시켜 발견된 그 flow는 |f|보다 엄격히 더 큰 값을 가진 G에서의 한 flow이고, f가 maximum flow라는 가정과 모순된다.
2=>3 : G_f가 augmenting path가 없다고 가정하자, 즉 G_F는 s에서 t로 가는 어떠한 경로가 없다. S = {v in V : G_f에서 s에서 v로가는 경로가 존재한다} 라고 정의하자. 그리고
T = V - S 라고 하자. (S, T) partition은 한 cut이다 : 우리는 s in S를 자명하게 갖고, t not in S이다, 왜냐하면 G_f에서 s에서 t로 가는 어떠한 경로가 없기 때문이다. 이제 u in S와 v in T의 정점들의 한 쌍을 고려하자. 만약 (u,v) in E라면, 우리는 f(u,v) = c(u,v)를 가져야만한다. 그렇지 않다면 (u,v) in E_f이기 때문이다. 이것은 v를 set S에서 배치시킨다. 만약 (v,u) in E라면, 우리는 f(v,u) = 0을 가져야만한다. 왜냐하면 그렇지 않다면 c_f(u,v) = f(v,u)이 양수가 될 것이고, 우리는 (u,v) in E_f를 가질 것이기 때문이다. 물론, 만약 (u,v)와 (v,u) 둘 다 E에 없다면, 그러면 f(u,v) = f(v,u) = 0이다. 따라서, 우리는
f(S, T) = c(S,T)
Lemma 26.4에 의해, 그러므로 |f| = f(S,T) = c(S,T)
(3) => 1: Corollary 26.5에 의해, 모든 cuts (S,T)에 대해 |f| <= c(S,T). |f| = c(S,T) 조건은 따라서 f가 maximum flow라는 것을 암시한다.
The basic Ford-Fulkerson algorithm
Ford-Fulkerson method의 각 반복에서, 우리는 augmenting path p를 발견하고, flow f를 수정하기 위해 p를 사용한다. Lemma 26.2와 Corollary 26.3이 제안하듯이, 우리는 f를 f↑f_p로 대체한다. 그리고 그 값이 |f| + |f_p|인 새로운 flow를 얻는다. 그 방법의 다음의 구현은 flow network G = (V,E)에서 flow attribute (u,v).f를 업데이트하여 maximum flow를 연산한다. E에 있는 각 edge (u,v)에 대해. 만약 (u,v) not in E라면, 우리는 내적으로 (u,v).f = 0이라고 가정한다. 우리는 또한 그 flow network를 따라서 capacities c(u,v)가 주어지고, 만약 (u,v) not in E라면 c(u,v) = 0이다. 우리는 공식 (26.2)를 따라서 residual capacity c_f(u,v)를 연산한다. 코드에서 c_f(p) 표현은 path p의 residual capacity를 저장하는 임시 변수이다.
FORD-FULKERSON-METHOD(G, s, t) 1 for each edge (u,v) in G.E 2 (u,v).f = 0 3 while there exists a path p from s to t in the residual network G_f 4 c_f(p) = min{c_f(u,v) : (u,v) is in p} 5 for each edge (u,v) in p 6 if (u,v) in E 7 (u,v).f = (u,v).f + c_f(p) 8 else (v,u).f = (v.u).f - c_f(p)
Analysis of Ford-Fulkerson
FORD-FULKERSON의 작동시간은 우리가 line 3에서 augmenting path p를 어떻게 발견하는지에 달려있다. 만약 우리가 그것을 나쁘게 선택한다면, 그 알고리즘은 심지어 종료되지 않을지도 모른다: flow의 값은 연속적인 augmentations로 증가할지 모르지만, 그것은 심지어 maximum flow value로 수렴할 필요가 없다. 만약 우리가 BFS(우리가 Section 22.2에서 보았던)를 사용하여 augmenting path를 찾는다면, 그러나, 그 알고리즘은 polynomial time에 작동한다. 이 결과를 증명하기 전에, 우리는 우리가 augmenting path를 임의로 선택하고 모든 capacities가 정수인 경우에 대한 simple bound를 얻는다.
실제로, maximum-flow 문제는 종종 integral capacities와 함께 발생한다. 만약 그 capacities가 유리수라면, 우리는 그것들을 모두 정수로 만들기 위해서 적절한 scaling transformation을 적용할 수 있다. 만약 f*가 변환된 네트워크에서 maximum flow를 표기한다면, FORD-FULKERSON의 간단한 구현은 lines 3-8의 while loop를 최대 |f*| times에 실행한다. 왜냐하면 그 flow value가 적어도 각 반복에서 한 unit씩 증가하기 때문이다.
우리는 만약 우리가 flow network G = (V, E)를 올바른 자료구조로 구현하고, linear-time algorithm으로 augmenting path를 찾는다면, 그 while loop 내에서 효율적으로 작업을 수행시킬 수 있다. 우리가 directed graph G' = (V, E')에 대응되는 한 자료구조를 유지한다고 가정하자. 거기에서 E' = {(u,v) : (u,v) in E or (v,u) in E}. network G에서 간선들은 또한 G'에서 간선들이고, 그러므로 우리는 쉽게 이 자료구조에서 capacities와 flows를 유지할 수 있다. G에서 한 flow f가 주어진다면, residual network G_f의 간선들은 G'의 모든 간선들 (u,v)로 구성되는데, c_f(u,v) > 0이다. 여기에서 c_f 는 방정식 26.2를 따른다. residual network에서 한 경로를 찾는 시간은 그러므로 O(V + E') = O(E) 이다. 만약 우리가 DFS 또는 BFS를 사용한다면. while loop의 각 반복은 따라서 O(E) 시간이 걸린다. lines 1-2에서 초기화 했듯이, FORD-FULKERSON 알고리즘의 총 작동시간을 O(E|f*|)이다.
capacities가 integral하고, optimal flow value |f*|가 작을 때, Ford-Fulkerson의 알고리즘의작동시간은 좋다. 그림 26.7 (a)는 |f*|가 큰 simple flow network에서 발생할수 있는 한 예제를 보여준다. 이 네트워크에서 maximum flow는 2,000,000을 갖는다: flow의 1,000,000의 단위가 path s->u->t를 가로지르고, 또 다른 1.000,000 units이 그 경로 s->v->t를 가로지른다. 만약 그 FORD-FULKERSON에 의해 발견된 첫 번째 augmenting path가 s->u->v->t라면, 그림 26.7(a)에 보여지듯이, 그 flow는 첫 번째 반복 후에 1의 값을 갖는다. 그 결과 residual network는 그림 26.7(b)에 나타난다. 만약 그 두 번째 반복이 s->v->u->t로 가는 augmeting path를 발견한다면, 그림 26.7(b)에 나타나듯이, 그 flow는 그러고나서 2의 값을 갖는다. 그림 26.7(c)는 그 결과 residual network를 보여준다. 우리는 계속 할 수 있다, s->u->v->t의 augmeting path를선택해서, odd-numbered iterations에서, 그리고 짝수 numbered iterations에서 s->v->u->t를 해서. 우리는 총 2,000,000번의 augmentations을 수행한다. flow value를 각 1 단위씩 증가시켜서.
The Edmonds-Karp algorithm
우리는 BFS로 line 3에서 augmenting path p를 찾아서, FORD-FULKERSON의 bound를 향상시킬 수 있다. 즉, 우리는 augmenting path를 residual network에서 s에서 t로가는 최단 경로로서 선택한다. 거기에서 각 간선은 단위 거리(가중치)를 갖는다. 우리는 그래서 구현된 Ford-Fulkerson method를 Edmonds-Karp algorithm이라고 부른다. 우리는 이제 Edmonds-Karp 알고리즘이 O(VE^2) 시간에 작동한다고 증명한다.
그 분석은 residual network G_f에 있는 정점들로 가는 거리에 의존한다. 다음의 lemma는 G_f에서 u에서 v로 가는 최단 경로 거리에 대해 &_f(u,v) notation을 사용한다. 거기에서 각 간선은 단위 거리를 갖는다.
Lemma 26.7
만약 Edmonds-Karp 알고리즘이 source s와 sink t를 가진 G = (V, E)인 flow network에서 작동된다면, 그러면 모든 정점 v in V - {s, t}에 대해, residual network에서 &_f(s,v) 최단 경로 거리는 각 flow augmentation에 따라 단조 증가한다.
Proof 우리는 v in V - {s, t}의 어떤 정점에 대해, s에서 v로 가는 최단 경로 거리가 줄어드는 flow augmentation이 있다고 가정하고, 그러고나서 모순을 이끌어 낼 것이다. f가 어떤 shortest-path distance를 줄이는 첫 번째 augmentation 전의 flow라고 하고, f'가 그 이후의 flow라고 하자. v를 &_f'(s,v)의 최소인데, 그 거리가 augmentation으로 줄어든 정점이라 하자, 즉, &_f'(s,v) < &_f(s,v)라고 하기 위해서이다. p = s->u ->v를 G_f'에서 s에서 v로 가는 최단 경로라고 하자, (u,v) in E_f'이고,
&_f'(s,u) = &_f'(s, v) - 1
우리가 v를 선택한 방법 때문에, source s에서 정점 u로 가는 거리는 감소하지 않는다. 즉, &_f'(s,u) >= &_f(s, u).
우리는 (u,v) not in E_f라고 주장한다. 왜? 만약 우리가 (u,v) in E_f를 가졌다면, 그러면 우리는 또한
&_f(s,v) <= &_f(s,u) + 1 (by Lemma 24.10 , the triangle inequality
<= &_f'(s,u) + 1 (by inequality (26.13))
= &_f'(s,v) (by equation (26.12))
그리고 이것은 &_f'(s,v) < &_f(s,v)의 가정과 모순이다.
어떻게 우리는 (u,v) not in E_f and (u,v) in E_f'를 가질 수 있는가? 그 augmentation은 v에서 u로 가는 flow를증가 시켰음에 틀림없다. Edmonds-Karp 알고리즘은 항상 최단 경로를 따라서 flow를 증가시켰고, 그러므로, G_f에서s에서u로 가는 최단 경로는 그것의 마지막가선에 (v,u)를 갖는다. 그러므로
&_f(s,v) = &_f(s,u) - 1
<= &_f'(s,u) - 1 (by inequality (26.13))
= &_f'(s, v) -2 (by equation (26.12))
이것은 &_f'(s,v) < &_f(s,v)와 모순되고, 우리는 그러한 정점 v가 존재한다는 것이 옳지 않다고 결론지을 수 있다.
다음의 정리는 Edmonds-Karp algorithm의 반복의 개수의 경계를 정한다.
Theorem 26.8
만약 Edmonds-Karp 알고리즘이 source s와 sink t를 가진 flow netwrok G = (V, E)에 작동된다면, 그 알고리즘에 의해 수행되는 flow augmentations의 총 개수는 O(VE)이다.
Proof residual network G_f에 있는 (u,v) 한 간선이 만약 augmenting path p의 residual capacity가 (u,v)의 residual capcity라면, 즉, c_f(p) = c_f(u, v)라면, augmenting path p에서 그 간선이 critical하다는 것이다. 우리가 augmenting path를 따라 flow를 augment한 후에, 그 경로에 있는 어떤 critical edge는 그 residual network로 부터 사라진다. 게다가, 적어도 어떤 augmenting path에 있는 한 edge는 critical임에 틀림 없다. 우리는 그 }E|개의 간선들의 각각이 최대 |V| / 2 번 critical 해질 수 있다는 것을 보여줄 것이다.
&_f(s, v) = &_f(s, u) + 1
그 flow가 augment된다면, 그 edge(u, v)는 residual network로부터 사라진다. 그것은 u에서 v로 가는 flow가 줄어든 후에야 다른 augmenting path에서나중에 다시 나타날 수 있다. 그리고 이것은 오직 (v, u)간선이 augmenting path에 나타나야 발생한다. 만약 f'가 이 사건이 발생할 때 G에서 flow라면, 그러면 우리는
&_f'(s,u) = &_f'(s,v) + 1
Lemma 26.7에 의해 &_f(s,v) <= &_f'(s,v)이기 때문에, 우리는
&_f'(s, u) = &_f'(s, v) + 1
>= &_f(s,v) + 1
= &_f(s, u) + 2
결과적으로 (u, v)가 critical 되는 시간부터, 그것이 다음에 critical될 떄의 시간까지, source에서 u로 가는 거리는 적어도 2가 증가된다. source에서 u로 가는 거리가 초기에 적어도 0이다. s에서 u로 가는 최단 경로에서 중간 정점들은 s, u, or t를 포함할 수 없다 (augmenting path에서 (u, v)는 u != t라는 것을 암시하기 때문에). 그러므로, u가 source로부터 도달할 수 없게 될 때 까지, 그것의 거리는 최대 |V| - 2이다. 따라서, (u, v)가 critical 해진 첫 번째 시간 이후에, 그것은 (|V| - 2) / 2= |V| / 2 - 1번 더 critical 해질 수 있다. 최대 |V| / 2번에 대해. residual netowrk에서 그것들 사이에 한 간선을 가질 수 있는 정점들의 O(E) 쌍이 있기 때문에, Edmonds-Karp algorithm동안 critical edges의 총 개수는 O(VE) 이다. 각 augmenting path는 적어도 하나의 critical edge를 갖으므로 그 정리가 나온다.
우리가 BFS로 augmenting path로 찾을 때 우리는 O(E) time에서 FORD-FULKERSON의 각 반복을 구현할 수 있기 때문에, Edmonds-Karp algorithm 은 O(VE^2) 이다. 우리는 push-relabel algorithms이 훨씬 더 좋은 bounds를 만들어 낼 수 있다는 것을 볼 것이다. Section 26.4의 알고리즘은 O(V^2E)의 작동시간을 성취하는 방법을 주고, 그리고 이것은 Section 26.5의 O(V^3) 알고리즘의 토대를 형성한다.
26.3 Maximum bipartite matching
몇 가지 조합 문제들은 쉽게 maximum-flow problems으로 바뀔 수 있다. Section 26.1의 multiple-source, multiple-sink maximum-flow 문제는 우리에게 한 가지 예시를 준다. 몇 가지 다른 조합 문제들은 표면적으로 flow networks와 거의 연관성이 없는 것처럼 보이지만, 사실 maximum-flow 문제로 줄어들 수 있따. 이 섹션은 한 그러한 문제를 보여준다: 이분 그래프에서 maximum matching을 찾기. 이 문제를 해결하기 위해서, 우리는 Ford-Fulkerson method에 의해 제공되는 주요 특성을 이용할 것이다. 우리는 또한 graph G = (V, E)에 대해 O(VE) 시간에 maximum-bipartite-matching 문제를 풀기 위해 어떻게 Ford-Fulkerson method를 사용할지를 볼 것이다.
The maximum-bipartite-matching problem
방향이 없는 그래프 G = (V, E)가 주어진다면, matching은 M in E의 간선들의 부분집합인데, v in V의 모든 정점에 대해, M의 최대 한 개의 간선이 v위에 있다. 우리는 vertex v in V가 matching M과 matched 되었다고 말한다. 만약 M에있는 어떤 간선이 v 위에 있다면; 그렇지 않다면, v는 unmatched되었다. maximum matching은 maximum cardinality의 matching인데, 즉 어떤 matching M'에 대해, 우리가 |M| >= |M'|인 matching M이다. 이 섹션에서, 우리는 우리의 관심을 bipartite graphs에서 maximum matchings를 찾는 것으로 제한한다: 그 정점 집합이 V = L U R로 분할될 수 있고, L과 R이 disjoint이고, E에 있는 모든 간선들은 L과 R사이로 간다. 우리는 나아가 V에 있는 모든 정점들이 적어도 한 개의 incident edge를 가진다고 가정한다. 그림 26.8은 bipartite graph에서 matching의 개념을 보여준다.
이분 그래프에서 maximum matching을 찾는 문제는 많은 실용적인 적용을 갖는다. 예시로서, 우리는 동시에 수행되는 업무들에 관해 기계들의 한 집합 L과 task들의 한 집합 R을 매칭시키는 것을 고려할 수 있다. 우리는 E에서 (u, v) 간선의 존재를 취하는데, u in L에 있는 특별한 machine이 v in R의 특별한 task를 수행할 수 있도록 하기 위해서이다. maximum matching은 가능한한 많은 기계에 대한 작업을 제공한다.
Finding a maximum bipartite matching
우리는 |V|와 |E|에서 다항시간에 방향이 없는 bipartite graph G= (V, E)에서 maximum matching을 찾기 위해 Ford-Fulkerson method를 사용할 수 있다. 트릭은 flows matching과 일치하는 flow network를 구성하는 것이다, 그림 26.8(c)에서 보이듯이. 우리는 그 bipartite graph G에 대한 G' = (V' ,E')를 대응되는 flow network로 정의한다. 우리는 source s와 sink t를 V에 없는 새로운 정점이 되게하고, V' = V U {s, t}가 되도록 한다. 만약 G의 vertex partition이 V = L U R이라면, 그 G'의 방향이 있는 간선ㄷ르은 E의 간선들이고, L에서 R로 방향지어지는데, |V|개의 새로운 방향이 있는 간선들을 추가된다:
E' = {(s,u) : u in L} U {(u,v) : (u,v) in E} U {(v, t) : v in R}.
그 구성하는 것을 완료짓기 위해, 우리는 E'에서 각 간선에 unit capacity를 할당한다. V에 있는각 정점은 적어도 한 개의 incident edge를 갖기 때문에, |E| >= |V| / 2 이다. 따라서
|E| <= |E'| = |E| + |V| <= 3|E|이고, 그래서 |E'| = O(E)이다.
다음의 lemma는 G에서 matching이 직접적으로 G의 대응되는 flow network G'에 있는 flow와 일치하는 것을 보여준다. 우리는 flow network G = (V, E)에 있는 flow f가 f(u, v)가 모든 (u, v) in V x V에 대해 정수라면, 정수값을 갖는다고 말한다.
Lemma 26.9
G = (V, E)가 vertex partition V = L U R인 이분 그래프라고 하고, G' = (V', E')가 그것에 대응되는 flow network라고 하자. 만약 M이 G에서 matching이라면, 그러면 G'에서 |f| = |M|의 값을 갖는 정수값 flow가 있다. 역으로, 만약 f가 G'에서 정수값 flow라면, G에서 |M| = |f|인 cardinality를 가진 matching M이 있다.
Proof 우리는 처음에 G에 있는 matching M이 G'에서 정수값 flow f와 일치한다는것을 보여준다. f를 다음으로 정의하자. 만약 (u,v)가 M에 있다면, 그러면 f(s, u) = f(u, v) = f(v, t) = 1이다. 모든 다른 간선들 (u, v) in E'에 대해, 우리는 f(u, v) = 0이라고 정의한다. f가 capcity constraint와 flow conservation을 만족한다는 것을 입증한다는 것은 간단하다.
직관적으로, M에 있는 각 간선 (u,v)는 경로 s->u->v->t를 가로지르는 G'에서 한 단위의 flow와 일치한다. 게다가, M에서 간선들에 의해 만들어지는 경로들은 vertex-disjoint이다, s와 t를 제외하고. 그 cut(L U {s}, R U {t}) 를 가로지르는 net flow는 |M|과 동일하다; 따라서, Lemma 26.4에 의해, flow의 값은 |f| = |M| 이다.
그 역을 증명하기 위해, f는 G'에서 정수값 flow이고,
M = { (u, v) : u in L, v in R, and f(u, v) > 0}
이라고 하자. L에 있는 각 정점 u는 오직 한 개의 들어오는 edge를 가진다, 즉 (s, u) 그리고 그것의 capacity는 1이다. 따라서, L에 있는 각 u는 그것으로 들어오는 최대 한 단위의 flow를 갖고, 만약 한 단위 플로우가 들어온다면, flow conservation에 의해, 한 단위의 flow가 나가야 한다. 게다가, f는 정수값이기 때문에, L에 있는 각 u에 대해, 한 단위의 플로우는 최대 한 개의 간선에 들어갈 수 있고, 최대 한 개의 간선을 떠날 수 있다. 따라서, 한 단위의 플로우는 u에 들어가는데, 만약 정확히 f(u, v) = 1이 되도록 하는 R에 있는 v가 있다면이다. 그리고 L에 있는 각 정점 u를 떠나는 각 정점이 양의 flow를 가질 떄여야만 하다. symmetric argument는 R에 있는 각 정점 v에 적용된다. 그 집합 M은 그러므로 matching이다.
|M| = |f|인 것을 보기 위해서, L에 있는 모든 매칭된 정점 u에 대해, 우리는 f(s, u) = 1을 갖는다는 것을 관찰해라, 그리고 E - M에 있는 모든 간선 (u, v)에 대해, 우리는 f(u, v) = 0을 갖는다. 결과적으로 f(L U {s}, R U {t}) 이것은 cut (L U {s} , R U {t})를 가로지르는 net flow인데, |M|과 동일하다. Lemma 26.4를 적용하여, 우리는 |f| = f(L U {s}, R U {t}) = |M|을 갖는다.
Lemma 26.9을 기반으로, 우리는 이분 그래프 G에서 maximum matching은 그것의 대응되는 flow network G'에서 maximum flow와 일치한다고 결론 짓고 싶다. 그래서 우리는 그러므로 G'에서 maximum-flow algorithm을작동하여, G에서 maximum matching을 연산할 수 있다. 이 사유에서 유일한 문제는 maximum-flow algorithm이 G'에서 어떤 f(u, v)가 정수가아닌 flow를 반환할지도 모른다는 것이다. 비록 flow value |f|가 정수여야만 할지라도. 다음의 정리는 만약 우리가 Ford-Fulkerson method를 사용한다면, 이 어려움이 발생할 수 없다는 것을 보여준다.
Theorem 26.10 (Integrality Theorem)
만약 capacity function c가 오직 정수값만을 가진다면, 그러면 Ford-Fulkerson method에 의해 만들어지는 maximum flow f는 |f|가 정수라는 특징을 갖는다. 게다가, 모든 정점 u와 v에 대해, f(u, v)의 값은 정수이다.
Proof 그 증거는 반복의 개수에서 유도에 의한다. 우리는 그것을 Exercise 26.3-2로 남긴다.
우리는 Lemma 26.9에 대한 다음의 corollary를 증명할 수 있다.
Corollary 26.11
이분 그래프 G에서 maximum matching M의 cardinality는 그것의 대응되는 flow network G'에서 maximum flow f의 값과 동일하다.
Proof 우리는 Lemma 26.9로부터 명명법을사용한다. M이 G에서 maximum matching이고, G'에서 대응되는 flow가 maximum이 아니라고 가정하자. 그러면 G'에서 |f'| > |f|인 최대 유량 f'가 있다. G'에서 capacities는 정수값이기 때문에, 정리 26.10에 의해, 우리는 f'가 정수값이라고 가정할 수 있다. 따라서, f'는 |M'| = |f'| > |f| = |M|인 cardinality를 가진 G에서 M' matching은 f'돠 일치한다. 이것은 M이 maximum matching이라는 우리의 가정과 모순이다. 비슷한 방식으로, 우리는 만약 f가 G'에서 maximum flow라면, 그것의 대응되는 matching이 G에서 maximum matching이라는 것을 보여줄 수 있다.
따라서, bipartite undirected graph G가 주어진다면, 우리는 flow network G'를 만들고 Ford-Fulkerson method를 작동시키고, 직접적으로 발견된 정수값 maximum flow f로부터 maximum matching M을 얻어서, maximum matching을 찾을 수 있다. 이분 그래프에서 어떤 matching은 최대 min(L, R) = O(V)를 갖기 때문에, G'에서 maximum flow의 값은 O(V)이다. 그러므로 우리는 이분 그래프에서 O(VE') = O(VE) 시간안에, maximum matching을 찾을 수 있다. |E'| = O(E)이기 때문이다.
댓글 없음:
댓글 쓰기