Algorithm - Network Flow, Edmonds-Karp

Network Flow(네트워크 플로우)란?

특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘. / 한 정점에서 다른 정점까지 흐를 수 있는 데이터의 최대 크기가 어느정도 인지를 확인하는 알고리즘. (얼마나 많은 유량(Flow)를 보낼 수 있는지를 계산/ 이러한 알고리즘은 교통 체증, 네트워크 전송, 전자 회로의 전류, 배수관을 흐르는 유체, 유량구하기 등의 다양한 분야에서 활용됨. / 유향 그래프에서 각 간선은 데이터가 흐를 수 있는 정해진 용량으로 제한되어 있으며 이를 최대한의 양으로 얼마나 흐르게 할 수 있는지를 확인함. -> 최대 유량 문제(Max Flow)로 정의하며 해결하기 위한 알고리즘으로 에드몬드 카프 알고리즘(Edmonds-Karp)를 적용함. 

 

- 유량 : 현재 흐르고 있는 데이터의 양

- Source(소스, S) : 시작 위치를 의미

- Sink(싱크, T) : 끝 위치를 의미

- Vertex(정점) : 유량이 모이는 위치

- Edge(간선) : 유량이 흐르는 파이프 역할

- Capacity(용량) : 유량이 흐를 수 있는 크기

- c(u, v) : c는 Capacity를 의미, u에서 v로 흐를 수 있는 간선의 용량을 의미

- f(u, v) : f는 Flow를 의미, u에서 v로 흐른 실제 유량을 의미

 

A -----0/7-----> B -----0/5-----> C -----0/9-----> D

위 그래프가 있을때 A에서 D까지 최대한으로 유량을 보낼때 A에서 7을 보내도 될까?

A -----7/7-----> B -----7/5-----> C -----0/9-----> D

=> 안됨. B까지 가는것은 성공하지만 C까지 갈 수 있는 최대 용량을 벗어남

A -----5/7-----> B -----5/5-----> C -----5/9-----> D

따라서 A에서 D까지 막힘없이 흐를 수 있는 최대 유량은 5가 됨(경로 상에서 가장 적은 용량이 5이기 때문)

 

=> 특정 경로를 따라 유량을 보낼때는 그 경로에 포함된 간선 중 가장 용량이 작은 간선에 의해 결정됨. 

용량 제한 속성 : 흐르는 양이 항상 그 간선의 용량을 넘을 수 없다는 의미

유량의 대칭성 : a -> b로 5라는 유량이 흘렀을때, b -> a로는 -5 만큼 흘렀다는 것과 같다는 뜻이라고 함.

유량의 보존 : 항상 들어오는 유량과 나가는 유량의 합이 같아야 한다는 의미. 유량 10이 들어왔는데 3이 나가고 7이 머무르고 있을 수 없다는 의미. (예외적인 부분으로 S(Source)와 T(Sink)는 그렇지 않다고 함)

 

Edmonds-Karp Algorithm

기본적으로 BFS를 이용해서 단순하게 가능한 모든 경우의 수를 탐색하는 방법을 사용. 가능한 모든 경우의 수를 탐색하기 위해 기본적으로 유량을 모두 0으로 설정함. 이후 정해진 용량(Capacity) 안에서 가능한 용량의 양을 반복적으로 더해줌.

최대 유량 알고리즘은 모든 가능한 경로를 다 계산해주기 위해서 음의 유량도 계산해줌. => 남아있는 모든 가능한 경로를 더 찾아내기 위함. / 최대 유량 알고리즘은 순서가 상관 없음. 남아있는 양이 1이 넘으면 계속해서 흘려 보내주면 알아서 최적화가 이루어진다는 점에서 특별한 상황이 아니면 유량을 보내는 순서를 고려할 필요 없음. / 기본적으로 BFS를 사용해서 모든 가능한 경로를 다 찾아서 남아있는 용량만큼 유량을 흘려 보내주는 것을 반복하면 됨.)

원래 포드 풀커슨 알고리즘이라는 DFS방식으로 이루어지는 알고리즘이 있으나 이 방식보다 에드몬드 카프 알고리즘이 보편적으로 쓰임.

 

 

 

에드몬드 카프 알고리즘의 시간 복잡도 = O(VE^2)  -> (정점 수 * 간선 수) 의 제곱

네트워크 플로우는 에드몬드 카프 알고리즘 외에 더 빠른 알고리즘도 존재하며 이분 매칭 등의 알고리즘으로 다양하게 확장이 가능한 알고리즘.

Edmonds-Karp 알고리즘이 VE^2인 이유를 증명하기 위해서는 증가 경로가 많아야 VE번 찾는다는 것을 보이면 됨. BFS한번이 O(E)이기 때문. 

- 간선의 capacity == 간선에 흐른 flow인 간선을 포화 간선이라 정의. 그렇지 않은 간선을 비포화 간선이라 정의

- 비포화 간선들로 이루어진 그래프를 Residual Graph라고 정의.

- Residual Graph에서 현재의 source - sink 최단경로가 D라고 했을 때, 최단 경로를 D로 유지하는 동안 E번만 증가 경로를 찾는다. / 한번 flow를 흘리면, Residual Graph의 간선 중 최소 하나가 포화 상태로 차버리게 됨. 포화 상태로 차게 된다면, 최단 경로가 D인 한 다시 그 간선을 보게 될일은 없음. 역변을 탈 일이 없으니 간선은 비포화에서 포화로만 변하고, 모든 간선이 포화로 변하면 경로가 없게 됨. -> 최단 경로를 고정했을때 O(E) 개의 증가 경로만을 찾음. 최단 경로의 길이는 V 이하이니 이러한 과정이 V번 일어남. 즉, 많아야 VE번 증가 경로를 찾음.