Maximum Flow.

Presentation on theme: "Maximum Flow."— Presentation transcript:

1 Maximum Flow

2 Flow Networks Flow Networks G=(V,E)
각 edge (u,v) 가 capacity c(u,v)≥ 0 를 갖는 directed graph. one source (s), one sink (t) 모든 vertex v ∈ V 에 대하여, path s → v → t 존재 (connected) |E| ≥ |V| -1

3 Flow Networks Flow f(u,v) value of flow maximum-flow problem
edge (u,v) 를 통과하는 양 (i) f(u,v) ≤ c(u,v), ∀u,v ∈ V (capacity constraint) (ii) f(u,v) = -f(v,u), ∀u,v ∈ V (skew symmetry) (iii) ,∀u ∈ V- {s,t} (flow conservation) value of flow source 에서 방출되는 flow 의 합 maximum-flow problem maximum value of flow 를 찾는 문제

4 Flow Networks Networks with multiple sources and sinks
M 개의 sources {s1, s2, … , sm} 와 n 개의 sinks {t1, t2, … , tn} 을 갖는 max-flow problem 1 개의 source 와 1개의 sink 를 갖는 표준 문제로 변환 1) super-source s 와 super-sink t 추가 2) c(s, si) = ∞, i=1,…,m , c(ti, t) = ∞, i=1,…,n

5 Ford-Fulkerson Method
Residual capacity Edge (u,v) 에 대한 잔여 허용량 또는 추가 가능한 flow (ex) Residual network Residual edge 로 구성된 network (residual network)

6 Ford-Fulkerson Method
Augmenting Path (p) residual network Gf 에서, s 부터 t 까지의 path 모든 edge 는 positive flow Residual capacity of augmenting path New flow

7 Ford-Fulkerson Method
Max-flow min-cut theorem Basic Algorithm f is a maximum flow in G ↔ residual network Gf contains no more augmenting paths

8 Ford-Fulkerson Method
Ford-Fulkerson (G,s,t) Running Time: O(E |f*|) Line 1-3: Q(E) while loop (line 4-8) 반복횟수: 최대 |f*| 번 (1씩 증가될 수 있으므로) while loop 내의 Gf 에서 s->t path 찾기: O(E) - breadth-first search or depth-first search

9 Ford-Fulkerson Method
Operations

10 Ford-Fulkerson Method
(Q)

11 Ford-Fulkerson Method
Edmonds-Karp Algorithm Ford-Fulkerson algorithm 개선 residual network 에서 augmenting path 를 BFS(breadth-first search) 로 찾음 running time= O(V E2) Edmonds-Karp 알고리즘으로 수행되는 flow augmentation 의 총 수 = O(V E) (Theorem 26.9) 각 augmenting path 에 대한 수행: O(E)

12 Maximum Bipartite Matching
Bipartite graph (i) undirected graph G = (V, E) (ii) V = V1 ∪ V2, 단, V1 ∩ V2 = ∅ (partitioned) (iii) (u, v) ∈ E 에 대하여, u ∈ V1, v ∈ V2 또는 u ∈ V2, v ∈ V1 Matching (i) M ⊆ E (ii) 모든 v ∈ V 에 대하여, 최대 1 개의 edge 가 연결(incident on)됨 cardinality : matching 의 수, |M| Maximum bipartite matching Bipartite graph 에서 최대의 cardinality 를 갖는 matching

13 Maximum Bipartite Matching
(ex)

14 Maximum Bipartite Matching
Corresponding flow network G=(V, E) : bipartite graph , V = L ∪R G’= (V’, E’): corresponding flow network V’ = V ∪ { s, t } E’ = { (s,u) | u ∈ L} ∪ {(u,v) | u∈ L, v ∈ R, and (u,v) ∈ E} ∪ {(v,t) | v ∈ R} c(u’,v’) = 1, ∀(u’,v’) ∈ E’ |M| = |f| M: matching in G f: flow in G’

15 Maximum Bipartite Matching
Algorithm S1. bipartite graph G 를 corresponding flow network G’ 로 변환 S2. G’ 에 대하여 Ford-Fulkerson 알고리즘 적용