최대 흐름 최소 절단 정리(Max-flow min-cut theorem)

물탱크 s에서 마을 t로 관을 통해 물을 보냅니다. 이음매를 꼭짓점⁠(vertex)⁠으로, 관을 방향 있는 변으로 그리면 그래프가 되고, 관마다 1초에 흘릴 수 있는 양(용량)이 정해져 있습니다. 흐름은 두 규칙을 지켜야 합니다. 관의 흐름은 0 이상이고 용량을 넘지 않으며, s와 t가 아닌 이음매에서는 들어온 만큼 나갑니다. 전기 회로의 한 이음점에 들어온 전류는 모두 나간다는 키르히호프의 전류 법칙과 같은 모양입니다. s에서 나가는 알짜 흐름을 최대로 하려면 어떻게 보내야 할까요? 도로의 차, 통신망의 데이터, 공급망의 물건이 모두 같은 문제입니다.

반대쪽에서 보면, 꼭짓점을 s가 든 무리 S와 t가 든 무리 T로 가른 것을 절단이라 하고, S에서 T로 가는 관의 용량을 모두 더한 것을 절단의 용량이라 합니다(T에서 S로 가는 관은 세지 않습니다). s에서 t로 가는 물은 어떻게든 이 경계를 건너야 하니, 어떤 흐름도 어떤 절단의 용량보다 클 수 없습니다. 이 정리가 말하는 것은 그 반대 방향입니다. 가장 큰 흐름과 가장 작은 절단은 언제나 같습니다. 1956년 미국 랜드 연구소의 레스터 포드와 델버트 풀커슨이 증명했고, 같은 무렵 MIT의 피터 일라이어스와 에이미얼 파인스타인, 벨 연구소의 섀넌도 함께 쓴 논문에서 독립적으로 증명했습니다.

처음 용량으로 관 가운데의 숫자(흐름/용량)를 누르면 용량이 1씩 커지고 9 다음에는 1로 돌아갑니다. 지금 흐름은 입니다.

흐름을 늘리는 방법은 s에서 t까지 아직 여유가 있는 길(증가 경로)을 찾아 그 길의 가장 좁은 여유만큼 더 보내는 것입니다. 다만 순진하게 욕심쟁이로 보내기만 하면 막다른 곳에 갇힐 수 있습니다. 그래서 이미 흐르는 관은 거꾸로도 지날 수 있게 합니다. 관을 거꾸로 지난다는 것은 앞서 보낸 물을 되돌려 다른 길로 돌린다는 뜻입니다. 이렇게 여유와 되돌릴 양을 모아 그린 그래프가 잔여 네트워크입니다. 1972년 잭 에드먼즈와 리처드 카프가 발표한 에드먼즈–카프 방법은 잔여 네트워크⁠(residual network)⁠에서 관 수가 가장 적은 증가 경로를 너비 우선 탐색(s에서 한 걸음, 두 걸음 떨어진 점들을 차례로 훑는 방법)으로 찾습니다. 모든 변의 길이가 1인 최단 경로⁠(shortest path)⁠ 찾기인 셈입니다. 이렇게 하면 늘리는 횟수가 꼭짓점 수와 변 수의 곱 정도로 묶입니다(점근 표기법⁠, asymptotic notation⁠). 증가 경로를 아무렇게나 고르면 늘리는 횟수가 용량의 크기에 따라 불어나고, 용량이 무리수⁠(irrational number)⁠이면 끝나지 않을 수도 있습니다. 용량이 모두 정수⁠(integer)⁠이면 한 번에 적어도 1씩 늘어나므로 반드시 끝나고, 최대 흐름도 정수로 고를 수 있습니다.

왜 최소 절단이 나타날까요? 더는 증가 경로가 없을 때, 잔여 네트워크에서 s에서 갈 수 있는 점들의 집합⁠(set)⁠을 S라 합시다. S에서 T로 가는 관은 모두 꽉 차 있고(아니면 더 갈 수 있으니까요), T에서 S로 가는 관은 모두 비어 있습니다(아니면 되돌려 갈 수 있으니까요). 그러니 지금 흐름이 정확히 이 절단의 용량과 같고, 앞의 부등식에 따라 둘 다 최적입니다. 지금 이 네트워크에서 최소 절단은 입니다. 이 정리는 최적화⁠(optimization)⁠에서 말하는 쌍대성⁠(duality)⁠의 대표적인 예입니다. 선형 계획법⁠(linear programming)⁠에서는 일차 부등식 조건 아래 일차식을 최대로 하는 문제마다 짝이 되는 최소화 문제가 하나씩 있습니다. 최대화 문제의 값은 짝 문제의 값을 넘을 수 없고, 두 문제 모두 조건을 만족하는 해가 있으면 두 최적값이 같습니다. 최대 흐름 문제를 선형 계획법으로 적으면, 그 짝 문제를 풀어 최소 절단을 얻을 수 있습니다.

이어지는 곳. 1955년 미국 랜드 연구소의 시어도어 해리스와 프랭크 로스가 쓴 비밀 보고서는 소련과 동유럽 철도망을 이런 네트워크로 그리고 병목을 분석했다고 알려져 있습니다. 모든 용량을 1로 두고 사람 쪽과 일 쪽에 s와 t를 붙이면 최대 흐름이 곧 최대 매칭⁠(maximum matching)⁠이고, 최소 절단이 홀의 정리⁠(Hall's theorem)⁠의 막힌 무리를 보여 줍니다. 1927년 오스트리아의 수학자 카를 멩거가 증명한 멩거의 정리⁠(Menger's theorem)⁠도 같은 모양입니다. 두 점 사이에 변을 함께 쓰지 않는 길이 최대 몇 개 있는지는, 두 점을 떼어 놓으려고 지워야 하는 변의 최소 개수와 같습니다(모든 용량을 1로 둔 최대 흐름 최소 절단). 사진에서 물체와 배경을 가르는 선을 어디에 그을지도 최소 절단으로 풉니다. 화소를 점으로, 이웃한 화소 사이를 색이 비슷할수록 용량이 큰 관으로 둡니다. 사용자가 물체와 배경이라고 표시한 화소를 각각 s와 t에 이어 두면, 가장 싼 절단은 색이 크게 바뀌는 곳을 따라 지나갑니다. 반대로 건너는 변이 가장 많은 절단을 찾는 문제는 NP-난해⁠(NP-hard)⁠하다는 것, 곧 빠른 풀이법이 있다면 모든 NP-완전⁠(NP-complete)⁠ 문제가 빠르게 풀린다는 것이 알려져 있어, 최소와 최대가 전혀 다른 난이도를 가집니다. 관마다 단위 흐름당 비용이 있을 때 정해진 양을 가장 싸게 보내는 최소 비용 흐름⁠(minimum-cost flow)⁠은, 연속적으로 퍼진 양을 옮기는 최적 수송⁠(optimal transport)⁠을 점과 관 위로 옮긴 이산판입니다.