[알고리즘 #9] Graph Algorithns(4)

 

1. Network Flow

(*개념 보충)

: Vertex 가 n 개인 directed graph G 가 주어지고 G 의 각 edge e 에 non-negative integer capacity c(e) 가 정의되 있다 하자.

- 이제 G 에서 source (indegree 가 0 인 vertex) s 와 sink (outdegree 가 0 인 vertex) t 가 주어졌을 때 다음과 같은 문제를 생각해 보자.

 

 

1. vertex v 에서 incoming edge 와 outgoing edge 존재 가능하다. incoming edge 에 대해 flow 가 정의되어 있고 outgoing edge 에 대해 flow 가 정의 되어 있을 것이다. 임이의 vertex w에서 v로 오는 모든 flow 의 총합은 v에서 나가는 flow 의 총합과 똑같다.

2. Flow 는 언제나 positive integer 

3. 모든 e에 대해 f(e)는 c(e)보다 같거나 작다(capacity: 수용량) 

4. source, sink에 대해서는 1번 성질을 적용하지 않고 capacity 보다 작으면 된다.

-> source 에서 나가는 flow 총합과 sink로 들어오는 flow 총합이 같다

5. source 에서 나가는 flow 의 총합을 val(f) 라고 한다. 

 

=> source 에서 나가는 최대 flow 총합을 구하고 싶다. (=val(f) 구하기 문제) 

 

 

 

2. Ford-Fulkerson Algorithm

Max-Flow 문제 알고리즘은 현재도 연구되고 있는 따끈따끈한 알고리즘이다.

Max-Flow 문제를 풀 수 있는 대표적인 알고리즘이다.

 

-residual graph(잔여 그래프) Gf : 주어진 그래프 G와 source 에서 나가는 total flow f로 정의되는 residual graph 를 만든다

-Augmenting path : G'의 source 에서 sink 까지 가는 path 로써 모든 edge의 capacity 가 positive 인 path 를 augmenting path 라고 한다,

 

<Step>

1. G의 vertex 와 edge를 모두 G0로 copy 한다.

2. G0 의 edge (u, v) 는 있고 (v,u) 는 없는 경우 , 

 

3. Gf 에서 augemnting path P를 아무거나 하나 찾고 해당 path 를 이루는 edge들의 capacity 중 최소값을 f'이라고  하자

 

4. 이제 P를 이루는 각 edge(u, v) 에 대해

        (i) c(u, v) = c(u, v) - f'

        (ii) c(v, u) = c(v, u) + f' 로 update

 

5. f를 f+f'로 업데이트

 

6. augmenting path 가 존재하지 않을 때까지 3,4,5 과정을 반복한다.

 

7.  더 이상 augmenting path 가 존재하지 않는 경우 , 현재 f가 G의 max-flow 가 된다

 

step 1 에서 aumenting path 찾기 해당 path 에서 capacity 최솟값은 2 이므로 f=2 로 업데이트한다. step 2 에서 새로운 augmenting path 를 찾고 해당 apth 에서 capacity 최솟값이 3이므로 f = 2 -> 2+3 = 5 로 업데이트한다. step3 에서 새로운 augmenting path 를 찾고 f = 5 -> 5 + 1 로 업데이트한다. step4 에서도 augmenting path 찾고 해당 path 에서 capacity 제일 작은 1을 더해 f = 6 -> 6+1 = 7 로 업데이트 한다. 그 후 augemting path 가 존재하지 않으므로 max-flow 값은 7이다.

 

 

예시 코드

Ford-Fulkerson Algorithm for Maximum Flow Problem - GeeksforGeeks

Ford-Fulkerson Algorithm for Maximum Flow Problem - GeeksforGeeks

-- 코드는 BFS 를 사용했으므로 Edmond-Karp algorithm 의 구현이라 할 수 있지만 graph 를 adjacency matrix 로 표현 했기 때문에 실제 수행 시간은 O(n3m) 이다.

- 코드의 graph 구현을 adjacency list 를 이용한 구현으로 변경할 경우, O(nm2 ) time implementation 이 된다.

경진 대회에서는 팀노트에 작성해서 가져갈 것 / 해당 알고리즘 코드은 Edmons Algorithm 이다.

 

Ford-Fulkerson Algorithm 특징

- G의 capacity 가 모두 non-negative integer인 경우, G 의 maximum flow 를 f라 하면, 각 step 마다 augmenting path 를 찾기 위해 O(n+m) = O(m) 시간이 소모되므로, FordFulkerson algorithm 의 time complexity 는 O(mf) 가 된다 (why?)

 

- 아래와 같은 graph 인 경우 (capacity 가 큰 edge가 있는 경우) Ford-Fulkerson algorithm 은 비효율적이다.

flow 값은 maximal flow 값에 비례하기 때문에 운이 안좋으면 비효율적이다.

 

 

 

3. Edmonds-Karp Algorithm

앞선 Ford-Fulkerson Algorithm 에서 augmenting path 를 고를 때 edge의 개수가 최소인 path 를 고를 경우 , 최대 O(mn) 번의 update 만 한다.

-> DFS 가 아닌 BFS 를 사용할 때 O(nm^2) 시간에 maximum-flow 구할 수 있다. (= Edmons-Karp Algorithm)

 

- Capacity 작은데 edge 가 많다면 이 알고리즘이 비효율적이다. 그러나 경시대회에선  이 알고리즘 사용하면 된다.

 

위의 방법으로 augmenting path 를 찾을 경우, 각 edge는 최대 O(n) 번 사용한다.

 

 

 

 

4. Network flow 적용 문제

(*보충)

1. min Cut Problem

대표적인 적용 문제이다.

Max-flow 문제와 Min-cut 문제는 Reduction 가능하다.!

Max-flow Min-Cut theorem (증명 생략) : Directed graph G에서 f 가 G의 flow 라 할 때, 아래 조건들 은 equivalent 하다.

(i) f 는 G 의 maximum flow 이다.

(ii) Residual graph Gf 는 augmenting path 를 가지고 있지 않다.

(iii) f는 G의 Min Cut 의 capacity 이다.

 

 

 

2. Edge-disjoint path

아무 두 path 찍어도 mutually disjoint  해야 한다. 

path 간 모든 edge가 공유되지 않는다.

 

3. Vertex-disjoint path(작년 기말)

 

dummy vertex 생성한 새로운 G'를 만든다.  Reduction 을 위해 capacity 모두 1로 정의한다.

 

4. Maximum Matching

Bipartite graph G = (V, E) 에서 서로 vertex 를 공유하지 않는 E 의 maximum subset 찾는 문제이다. 

matching 은 edge set 인데 어떤 vertex 도 공유하지 않는 matching 의 maxumum 을 찾는다. 예를들어 (1,5) (3,5) 은 maximum matching 아니다.

 

 

ex) UVa 0259 – Software Allocation

- 앞선 언급한 maximum matching 을 이용하는 문제. 이런 부류의 문제는 항상 주어진 문제가 있을 때 graph 를 ‘적절하게’ 정의해 주는 것이 중요함.

- 입력값은 (앱, 컴퓨터) 으로 bipartition 이 정의된 vertex 26+10 = 36 개의 bipartite graph G로 정의될 수 있음.

- 이제 G에서 directed graph G’ 를 앞선 maximum matching problem 과 비슷하게 정의하되, 이 문제의 경 우 하나의 어플리케이션을 여러 사용자가 필요로 하는 경우가 있으므로 capacity 정의를 신중히 해야함.

- G’ 의 source 에서 각 앱에 해당하는 vertex 로 향하는 edge 의 capacity

 여러 사람이 같은 앱을 필요로 할 수 있고, 따라서 해당 app 을 원하는 사람수로 capacity 를 설정 - G’ 의 컴퓨터에 해당하는 vertex 에서 sink 로 향하는 edge 의 capacit

 각 컴퓨터는 한번만 사용 가능 하므로 capacity 는 1로 정의 - G’ 의 앱에 해당하는 vertex 에서 컴퓨터에 해당하는 vertex 로 향하는 edge의 capacity

 각 컴퓨터당 최대 한대의 앱을 돌릴 수 있으므로, capacity 는 1로 정의

- G’ 의 maximum flow 와 그날 앱의 총 수요량과 같은 경우에만 scheduling 이 가능하다! 원래 matching 문제에서 요구하는 조건과 동일하지 않다는 것에 유의할 것.

- 또한 실제 matching 의 경우 G’ 의 residual graph 에서 (컴퓨터, 앱) 꼴의 edge 들 중 capacity 가 1 인 것들을 출력하면 된다 (why?)