NetWork Flow Algorithm (네트워크 플로우)

NetWork Flow Algorithm

# 네트워크 전송 및 통신 분야에서 사용하는 Algorithm

아래 그림과 같이 간단하게 용량과 유량을 표시합니다.

그림에서 가장 손실 없이 유량을 전달할 때, 가장 적합한 유량은 몇 일까요?

 

만약 5를 유량으로 보내게 된다면, 5는 b에서 c를 갈 때, 3만큼만 갈 수 있으므로,

 

b에서 2만큼의 손실이 발생하게 됩니다.

 

따라서, 위 그림에서 손실 없이 유량을 보내는 방법은 3을 보내는 것입니다. 그리하여 최대한 낭비되는 것 없이 유량을 보낼 수가 있습니다.

 

이를 Max Flow Problem(최대 유량 문제)라고 합니다.

 

이렇게 최대 유량 문제 란 네트워크 상에서 얼마나 많은 데이터를 흘려 보낼 수 있는지를 나타냅니다.

 

최대 유량 문제 는 각 간선에 정해진 용량이 있을 때, start에서 end로 보낼 수 있는 최대 유량의 크기를 구하는 문제입니다.

 

기본적으로 최대 유량 문제를 해결하는 방법은 단순하게 가능한 모든 경우의 수를 탐색하는 방법입니다.

 

이 경우, BFS(너비 우선 탐색)를 이용하는 것이 일반적이며, Edmonds-Karp Algorithm(에드몬드 카프 알고리즘)이라고 합니다.

 

아래 그림은 어떨까요 ?

가능한 모든 경우의 수를 탐색하기 위하여 기본적으로 현재 흐르고 있는 모든 유량(flow)을 0으로 설정합니다.
그리고, 이후 정해진 용량(capacity) 안에서 가능한 용량의 양을 반복적으로 더해주면 됩니다.

위와 같이 S에서 T로 가는 방법을 표시하면 다음과 같습니다.

• S -> a -> d -> T 는 1의 유량이면 됩니다.
• S -> b -> d -> T 는 1의 유량이면 됩니다.
• S -> c -> e -> T 는 4의 유량이면 됩니다.

 

이렇게, 완료된 그림은 다음과 같습니다.

현 상황에서 최대 유량은 2/3 과 1/3, 4/4에서의 유량의 합인 2 + 1+ 4 = 7입니다.

 

그러나, 이 경우 여기서 더 이상 보낼 수 없는 것으로 보입니다.

 

그런데 여기서,

 

"최대 유량 알고리즘의 핵심"이 등장합니다 !   바로 "음의 유량을 계산"하는 것입니다.

 

그러나 이 경우, 음의 유량을 고려하여도 7이 최대 유량이 됩니다.

 

다른 예시를 참고하여 음의 유량 계산을 살펴보시기 바랍니다.

 

정리하자면,

 

최대 유량 알고리즘은 다음과 같은 특징을 갖는다.

• 최대 유량 알고리즘은 순서가 없다.
• 남아있는 양이 1이 넘으면 계속해서 흘러 보내주면 알아서 최적화가 이루어진다.

 

참고 출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ndb796&logNo=221237111220

 

해당 글은 안경잡이개발자님 블로그를 참고하여 만들었으며 문제가 될 시 삭제하도록 하겠습니다.

 

※ 피드백과 오류 정정은 언제나 환영입니다. ※