14. Maximum Flow

Maximum Flow

Maximum Flow가 주로 사용되는 분야는 graph에서 최대 flow를 유동하고 싶은 분야이다. 대표적으로 하수도 시스템, 인터넷 네트워크, 교통량 등이 있다. Network는 directed graph G = (V, E, C)로 표현한다. C는 capacity→$R^+$이다. Flow는 f:E=(u, v) →$R$로 표현한다. f는 edge에서 항상 C보다 값이 작다.

 

Augmented Path

Elemently paht: s→t이다. 한마디로 source에서 destination까지 갈 수 있는 elemently path이다.

Bottleneck은 다음과 같이 구한다. b = $min(c(v_i, v_{i+1}))$

 

Flow example

Flow example

가능한 augmented path 아무거나 flow를 보내다 보면, global optimal이 아닌 경우가 생긴다. Global optimal을 찾기 위해 Residual graph를 사용한다.

 

Residual graph

남아있는 capacity를 보여주는 flow graph이다.

역방향으로도 flow가 흐를 수 있게 되어 global optimal을 찾기에 용이해진다.

 

Ford-Fulkerson algorithm

Residual graph를 그리고

Augmenting path를 찾아서

가능한 flow를 흘려 보내는 과정을 반복해서 Maximum flow를 흐르게 만든다.

 

알고리즘은 다음과 같다.

Ford Fulkerson

초기 상태에 flow가 없으므로 f=0이다. 그 후에는 augmented path를 찾고, bottleneck을 찾아서 flow를 흘러보낸다. 예시를 통해 과정을 확인한다.

1st augmented path, bottleneck=4

2nd argument path, bottleneck=12

3rd augmented path, bottleneck=7

이렇게 해서 Maximum flow 23을 얻을 수 있게 된다.

 

그런데 사실 bottlenck이라는 개념에서 시작해 cut이라는 개념을 적용해보면, min cut이 곧 max flow가 됨을 알 수 있다.

 

Cuts in graph

Example of cut

Cut이란 vertices를 S와 T로 나누는 선이다. 당연히 S에는 source가, T에는 destination이 있다.

• Capacity: S→T 방향의 edges의 합
• Flow: S에서 나가는 edge - S로 들어오는 edge

Flow(S,T) ≤ Capacity(S,T)인 관계를 가지고 있다.

 

아까 살펴본 예제의 Min cut을 구해보면 다음과 같고 놀랍게도 Maximum flow와 값이 같다.

Min Cut

Worst case of Ford-Fulkerson

다음의 예제는 Ford-Fulkerson의 worst case이다.

Worst case of Fold fulkerson

Bottleneck이 1로 잡히게 되면서 2000번 반복하게 된다. Min cut을 통해 구하면 바로 Maximum flow는 2000임을 알 수 있다.

Iterates 2000

Augment path야 DFS같은 알고리즘을 사용하여 $O(E)$의 시간이 소모된다. 그러나 위와 같은 경우 bottleneck의 flow양에 따라 시간 복잡도가 결정되게 된다. 따라서 시간 복잡도는 $O(|E||f^*|)$가 소모된다. (f: flow의 양)

 

Edmond-Karp algorithm

Ford-Fulkerson과 유사하다.

 

Residual graph를 그리고

Shortest augmenting pah를 찾고

Bottleneck에 해당하는 flow를 흘리는 것을 반복한다.

 

구체적인 알고리즘은 다음과 같다.

Edmond Karp

Shortest path를 찾는 알고리즘(BFS 사용)의 시간 복잡도는 $O(E+V)≒O(E)$가 된다. 또한 augment path에서 vertex의 최대 수 $O(V)$, edge의 최대 수 $O(2E)$에 따라서 $O(VE)$의 시간 복잡도가 소모된다. 따라서 알고리즘의 시간 복잡도는 $O(VE^2)$이 된다.