Network - 1. 최대흐름그래프

최대흐름 문제는 그래프 이론에서 중요한 문제 중 하나로, 주어진 유향 그래프에서 한 정점에서 다른 정점으로의 최대 흐름을 찾는 문제입니다. 이 문제는 실생활에서 네트워크의 최대 용량을 결정하거나, 자원의 효율적인 배분 문제 등에 응용될 수 있습니다.

주어진 그래프에서 각 간선은 특정 용량(capacity)을 가지고 있으며, 한 정점에서 다른 정점으로 흐를 수 있는 최대량을 결정하는 것이 목표입니다. 예를 들어, 도로망에서 한 지점에서 다른 지점으로 자동차의 최대 통행량을 결정하거나, 컴퓨터 네트워크에서 데이터의 최대 전송량을 결정하는 것과 유사합니다.

최대흐름 문제를 해결하는 대표적인 알고리즘으로는 포드-풀커슨(Ford-Fulkerson) 알고리즘이 있습니다. 이 알고리즘은 너비 우선 탐색(BFS)을 이용하여 증가 경로를 찾고, 해당 경로에서 최대로 흐를 수 있는 양만큼 흐름을 증가시키는 방식으로 동작합니다. 이 과정을 반복하여 최대 흐름을 찾습니다.

최대흐름 문제는 실제로 복잡한 네트워크 상황에서도 적용 가능하며, 최적의 자원 할당이나 데이터 전송 계획 등 다양한 분야에서 중요한 응용 가능성을 가지고 있습니다.

예를 들어 보겠습니다.

한 도시에서 다른 도시로 물자를 최대한 많이 운반하는 문제입니다. 도시 간의 도로 네트워크가 주어지고, 각 도로는 일정량의 물자를 운반할 수 있는 용량(capacity)을 가지고 있습니다. 가능한 한 많은 물자를 운반할 때, 최대 운반량을 구하는 최대흐름 문제를 해결할 수 있습니다. 이 때 그래프에서 각 노드는 도시를 나타내며, 간선은 도로를 나타냅니다. 각 도로의 용량은 그에 연결된 화살표 위에 명시되어 있습니다.

최대흐름 문제를 해결하는 알고리즘은 초기해를 구하는 초기화와 현재해를 개선하는 주반복단계로 이루어집니다. 초기화 단계에서는 손쉬운 가능해를 찾을 수 있습니다. 최대흐름문제의 경우, 모두 호 흐름이 0인 해를 사용합니다. 주 반복단계는 현재 해가 최적이 아닌 경우 개선하는 단계입니다. 알고리즘의 성능을 결정합니다.

해 개선원리에 대해 생각해보겠습니다. 초기 흐름이 단순한 그래프의 경우 단순히 남은 호의 용량아 0보다 큰 경로 중 하나를 선택해 가능한 큰 흐름을 보내는 것만으로는 최대흐름을 보낼 수 없습니다. 최적해가 아니기 때문에, 다른 방법을 생각할 수 있습니다. 여기서 아이디어는 호의 흐름을 감소시키는 것을 역방향으로 흐름을 보내는 것으로 해석하는 것입니다. 호에 흐름이 흐르고 있다면, 양방향으로 남은 용량을 모두 고려합니다. 이를 잔여용량(residual capacity)라고 하며, 잔여 용량을 표시한 네트워크를 잔여용량 네트워크로 표기합니다. 용량이 0보다 큰 호로 이루어진 s-t 유향경로는 s-t 흐름증가경로라고 부릅니다.

다시 위의 예를 생각해보겠습니다.

초기화 단계. 모든 호의 흐름을 0으로 둡니다. 모든 마디에서 용량이 0입니다.

단계 2. 남은 호의 용량이 모두 0보다 큰 경로 중 임의로 선택하여 흐름을 보냅니다.

단계 3. 원래 문제의 가능해를 초기해로 사용합니다. 흐름증가경로를 적용했을 때 잔여용량네트워크는 다음과 같이 나타낼 수 있습니다.

단계 4. 새로운 해의 잔여용량네트워크는 다음과 같습니다. 더 이상 s-t가 흐름증가 경로가 없음을 알 수 있습니다. 알고리즘을 종료합니다.

참고자료 : 경영과학, 홍성필, 율곡출판사