최대 유량 문제

강한 다항 시간 알고리즘은 입력의 크기, 즉 정점의 수 |V|와 간선의 수 |E|에만 의존하는 다항 시간 복잡도를 가지며, 간선의 용량 값 자체의 크기에는 의존하지 않는 알고리즘들을 말한다. 이는 입력 네트워크의 구조적 특성만으로 실행 시간이 결정됨을 의미한다.

초기의 대표적인 강한 다항 시간 알고리즘으로는 1969년에 발표된 에드먼즈-카프 알고리즘이 있다. 이 알고리즘은 포드-풀커슨 알고리즘의 변형으로, 너비 우선 탐색을 사용하여 증가 경로를 찾아 시간 복잡도 O(|V| * |E|^2)를 보장한다. 1970년에는 에프게니 디니츠가 O(|V|^2 * |E|)의 복잡도를 가지는 디니츠 알고리즘을 제안했으며, 이는 블로킹 흐름 개념을 도입하여 성능을 개선했다.

이후 알고리즘들은 더 빠른 실행 시간을 목표로 지속적으로 발전해왔다. 1974년 알렉산드르 카르자노프는 O(|V|^3) 알고리즘을 제안했고, 1978년 말호트라-쿠마르-마헤슈와리 알고리즘은 동일한 복잡도를 가지면서 더 간결한 방법을 제시했다. 2013년에는 제임스 B. 올린이 이론적으로 O(|V| * |E|)의 선형 시간에 가까운 알고리즘을 발표하여 주목을 받았다. 이러한 발전은 최대 유량 최소 컷 정리를 바탕으로 한 다양한 최적화 기법과 데이터 구조의 개선을 통해 이루어졌다.

의사 다항 시간 알고리즘과 약한 다항 시간 알고리즘은 입력 네트워크의 최대 간선 용량 값(U)에 의존하는 실행 시간을 가진다. 이들은 강한 다항 시간 알고리즘과 구분되는데, 강한 다항 시간 알고리즘은 정점 수(V)와 간선 수(E)에만 의존하며 용량 값의 크기에는 영향을 받지 않는다.

의사 다항 시간 알고리즘의 대표적인 예는 포드-풀커슨 알고리즘이다. 이 알고리즘의 실행 시간은 O(EU)로 표현되며, 이는 최대 흐름 값이 U에 비례할 수 있기 때문에 U가 매우 큰 경우 비실용적일 수 있다. 반면, 약한 다항 시간 알고리즘은 log U에 대해서만 다항식 시간을 보장한다. 즉, 입력 크기를 이진수로 표현했을 때의 길이(비트 수)에 대해 다항식 시간이 걸린다. 골드버그와 라오의 이진 블로킹 흐름 알고리즘이나 최근의 천, 킹, 리우, 펭, 구텐베르크, 사흐데바의 알고리즘은 이러한 약한 다항 시간 범주에 속하며, 거의 선형 시간에 가까운 성능을 보인다.

이러한 구분은 계산 복잡도 이론에서 중요하다. 강한 다항 시간 알고리즘은 입력의 수치적 크기에 무관하게 효율성을 보장하는 반면, 의사 다항 시간 알고리즘은 큰 수치 값이 주어지면 실질적으로 매우 느려질 수 있다. 최대 유량 문제를 해결하는 많은 역사적 알고리즘 발전은 이러한 복잡도 클래스 간의 경계를 개선하는 데 초점을 맞추어 왔다.

다중 소스 다중 싱크 최대 흐름 문제는 최대 유량 문제의 일반화된 형태이다. 기존 문제가 하나의 소스와 하나의 싱크를 가진 네트워크 흐름을 다룬다면, 이 변형 문제에서는 여러 개의 소스와 여러 개의 싱크가 존재한다. 즉, 소스 집합 S = {s1, s2, ..., sn}에서 싱크 집합 T = {t1, t2, ..., tm}으로 가능한 최대의 총 유량을 보내는 실행 가능한 흐름을 찾아야 한다.

이 문제는 슈퍼소스와 슈퍼싱크를 도입하여 기존의 단일 소스-단일 싱크 최대 유량 문제로 효율적으로 변환할 수 있다. 원래 네트워크에 새로운 가상의 소스 노드 s'와 싱크 노드 t'를 추가한다. 그런 다음, s'에서 원래 소스 집합 S의 각 정점으로 무한한 용량을 가진 간선을 연결한다. 마찬가지로, 싱크 집합 T의 각 정점에서 새로운 싱크 t'로 무한한 용량의 간선을 연결한다. 이렇게 구성된 새로운 네트워크에서 s'에서 t'로의 최대 유량을 구하면, 그것이 원래 다중 소스 다중 싱크 문제의 최대 유량 값과 정확히 일치한다.

이 변환은 포드-풀커슨 알고리즘이나 에드먼즈-카프 알고리즘과 같은 기존의 최대 유량 알고리즘을 그대로 적용할 수 있게 해준다. 이 접근법은 통신 네트워크에서 여러 발신지와 수신지 간의 데이터 전송 용량을 계산하거나, 물류 시스템에서 여러 공장에서 여러 창고로의 최대 물자 이동량을 계획하는 등 실제 문제에 널리 응용된다.

최대 이분 매칭 문제는 주어진 이분 그래프에서 가능한 한 많은 간선을 선택하되, 어떤 정점도 두 개 이상의 선택된 간선에 포함되지 않도록 하는 매칭을 찾는 문제이다. 이는 조합 최적화의 대표적인 문제 중 하나로, 작업 할당, 스케줄링, 자원 배분 등 다양한 실용적인 문제에 응용된다.

이 문제는 최대 유량 문제로 효율적으로 환원하여 해결할 수 있다. 주어진 이분 그래프 G = (X ∪ Y, E)에 대해, 새로운 유량 네트워크 N을 구성한다. 네트워크 N은 소스 정점 s와 싱크 정점 t를 추가하며, s에서 X의 모든 정점으로, Y의 모든 정점에서 t로 용량 1의 간선을 연결한다. 또한 원래 그래프 G의 각 간선 (x, y) (여기서 x ∈ X, y ∈ Y)을 x에서 y로 향하는 용량 1의 간선으로 변환하여 추가한다. 이렇게 구성된 네트워크 N에서의 최대 s-t 유량의 값은 원래 이분 그래프 G의 최대 매칭 크기와 정확히 일치한다.

이 환원의 핵심은 정수 유량 정리에 기반한다. 모든 간선의 용량이 정수이므로, 최대 유량 알고리즘은 각 간선의 유량이 0 또는 1인 정수 최대 유량을 찾는다. 이때 유량값이 1인 네트워크 내부 간선들(즉, X에서 Y로 향하는 간선들)이 바로 최대 이분 매칭을 구성한다. 이 방법을 통해 에드먼즈-카프 알고리즘이나 디니츠 알고리즘과 같은 최대 유량 알고리즘을 이용하여 최대 이분 매칭을 다항 시간 내에 구할 수 있다.

이러한 접근법은 최대 이분 매칭을 직접 푸는 헝가리안 알고리즘과는 다른 관점을 제공하며, 네트워크 유량 이론의 강력한 응용 사례를 보여준다. 또한 이는 보다 복잡한 매칭 문제나 할당 문제를 해결하는 기초가 되기도 한다.

유향 비순환 그래프의 최소 경로 커버 문제는 주어진 유향 비순환 그래프(DAG)에서 모든 정점을 덮는 최소 개수의 정점-분리 경로를 찾는 문제이다. 여기서 정점-분리 경로란 경로들이 서로 공유하는 정점이 없음을 의미한다. 이 문제는 최대 유량 문제와 최대 이분 매칭 문제로 환원하여 효율적으로 해결할 수 있다.

문제를 해결하기 위해 먼저 주어진 DAG G로부터 이분 그래프 G'을 구성한다. G의 각 정점 v는 나가는 간선이 있다면 v_out, 들어오는 간선이 있다면 v_in이라는 두 개의 정점으로 분할되어 G'에 속한다. 그리고 G에서 (u, v)가 간선일 때, G'에는 (u_out, v_in) 간선을 추가한다. 이렇게 생성된 이분 그래프 G'에서 최대 이분 매칭을 구하면, 그 매칭의 크기 m이 원래 그래프 G에서 구성할 수 있는 최소 경로 커버의 크기와 직접적인 관계를 가진다.

구체적으로, G'에서 크기 m의 최대 매칭 M을 찾았다면, G는 n - m개의 정점-분리 경로로 구성된 최소 경로 커버를 가진다. 여기서 n은 G의 정점 수이다. 매칭 M의 각 간선 (u_out, v_in)은 원래 그래프 G에서 경로 상의 간선 (u, v)에 대응된다. 매칭되지 않은 정점들은 각 경로의 시작점이나 끝점이 된다. 이 변환을 통해 복잡한 경로 커버 문제는 잘 알려진 최대 이분 매칭 문제로 귀결되며, 이는 다시 최대 유량 문제 알고리즘(예: 에드먼즈-카프 알고리즘이나 디니츠 알고리즘)을 적용하여 해결할 수 있다.

이 기법은 작업 스케줄링, 소스 코드 의존성 분석, 명령어 스케줄링 등 유향 비순환 그래프의 구조를 최소한의 리소스(예: 실행 스레드 또는 프로세서)로 분해해야 하는 다양한 조합 최적화 문제에 응용된다.

정점 용량 포함 최대 흐름 문제는 기존의 최대 유량 문제에서 각 간선뿐만 아니라 각 정점에도 흐름 용량 제한이 있는 경우를 다룬다. 즉, 소스와 싱크를 제외한 각 정점을 통과하는 흐름의 총량이 그 정점에 주어진 용량을 초과할 수 없다. 이는 실제 문제에서 교차로의 처리 능력, 환승 지점의 수용 한계, 또는 네트워크 허브의 대역폭 제약 등을 모델링할 때 유용하다.

이 문제는 노드 분할(node splitting) 기법을 통해 기존의 최대 유량 문제로 환원하여 해결할 수 있다. 각 정점 v를 들어오는 흐름을 받는 정점 v_in과 나가는 흐름을 내보내는 정점 v_out, 두 개로 분할한다. 원래 정점 v로 들어오던 모든 간선은 v_in으로 연결되도록 변경하고, v에서 나가던 모든 간선은 v_out에서 시작하도록 변경한다. 마지막으로 v_in에서 v_out으로 향하는 용량 c(v)의 간선을 추가한다. 이렇게 구성된 새로운 네트워크에서는 모든 정점 용량 제약이 v_in → v_out 간선의 간선 용량으로 대체되므로, 포드-풀커슨 알고리즘이나 에드먼즈-카프 알고리즘과 같은 표준 최대 유량 알고리즘을 그대로 적용할 수 있다.

이 변환을 통해 정점 용량이 포함된 복잡한 네트워크 흐름 문제도 효율적으로 해결할 수 있다. 이 기법은 통신 네트워크 설계, 도로 교통 흐름 최적화, 생산 라인 밸런싱 등 다양한 분야에서 실제 제약 조건을 모델링하는 데 활용된다. 특히 복합 수송 시스템에서 환승 지점의 처리 용량을 고려해야 하거나, 데이터 센터 네트워크에서 서버 노드의 처리 한계를 반영할 때 유용하게 적용된다.

s에서 t까지의 최대 경로 수 문제는 주어진 유향 그래프와 두 정점 s, t에 대해 s에서 t까지 존재할 수 있는 경로의 최대 개수를 찾는 문제이다. 이 문제는 경로가 서로 간선-분리여야 하는지, 아니면 정점-분리(독립 경로)여야 하는지에 따라 두 가지 주요 변형으로 나뉜다.

간선-분리 경로의 최대 개수를 구하는 문제는 최대 유량 문제로 효율적으로 환원된다. 그래프의 각 간선에 용량 1을 할당하고, s를 소스, t를 싱크로 하는 흐름 네트워크를 구성한다. 이 네트워크에서의 최대 유량 값은 정수 흐름 정리에 의해 정수로 나오며, 이 값이 s에서 t까지의 간선-분리 경로의 최대 수와 정확히 일치한다.

정점-분리 경로의 최대 개수를 구하는 문제는 정점 용량이 포함된 최대 유량 문제로 환원된다. 각 정점을 들어오는 간선과 나가는 간선으로 분할하고, 두 부분을 용량 1의 간선으로 연결함으로써 정점을 통과하는 흐름을 1로 제한한다. 이렇게 변환된 네트워크에서의 최대 유량 값이 s에서 t까지의 정점-분리 경로의 최대 수가 된다. 이는 먼저-퍼커슨 정리의 한 응용으로 볼 수 있다.

그러나 경로의 길이를 제한하는 조건(예: 길이가 정확히 k이거나 최대 k인 경로만 허용)이 추가되면, 대부분의 변형들이 NP-완전 문제가 되어 효율적인 해법을 찾기 어려워진다.

클로저 문제는 유향 그래프에서 특정 조건을 만족하는 정점 부분집합을 찾는 최적화 문제이다. 유향 그래프에서 클로저는 해당 집합 내의 정점에서 나가는 모든 간선이 다시 그 집합 내의 정점으로 향하는, 즉 외부로 나가는 간선이 없는 정점들의 집합을 의미한다. 클로저 문제는 각 정점에 가중치가 부여된 유향 그래프에서 가중치 합이 최대가 되는 클로저(최대 가중치 클로저) 또는 최소가 되는 클로저(최소 가중치 클로저)를 찾는 것이다.

이 문제는 최대 유량 문제와 최소 컷 문제로의 환원을 통해 다항 시간에 해결할 수 있다. 환원 방법은 주어진 유향 그래프를 흐름 네트워크로 변환하는 것이다. 변환 과정에서는 원래 그래프의 각 정점을 네트워크의 노드로 포함시키고, 각 간선을 용량이 무한대인 네트워크 간선으로 추가한다. 여기에 소스 노드와 싱크 노드를 새로 생성한 후, 양의 가중치를 가진 정점에는 소스에서 해당 정점으로 향하는 간선을 추가하고 그 용량을 정점 가중치로 설정한다. 음의 가중치를 가진 정점에는 해당 정점에서 싱크로 향하는 간선을 추가하고 용량을 가중치의 절댓값으로 설정한다.

이렇게 구성된 네트워크에서 최소 컷을 계산하면, 최소 컷에 의해 소스 측에 속하는 정점들의 집합이 원래 그래프의 최대 가중치 클로저가 된다. 이는 최소 컷의 용량이 소스 측 정점들의 음의 가중치 합과 싱크 측 정점들의 양의 가중치 합을 나타내며, 이를 최소화하는 것이 결국 클로저의 가중치 합을 최대화하는 것과 동치이기 때문이다. 이 환원은 최대 유량 최소 컷 정리에 기반하여 이루어진다.

클로저 문제와 그 최대 유량 기반 해법은 프로젝트 선택 문제, 작업 스케줄링, 그리고 특정 유형의 자원 할당 문제를 모델링하는 데 응용된다. 예를 들어, 상호 배타적인 선행 관계를 가진 작업들 중에서 최대 이익을 내는 집합을 선택하는 문제는 클로저 문제로 정형화될 수 있다.

야구 토너먼트 탈락 문제는 최대 유량 문제의 대표적인 실제 응용 사례이다. 이 문제는 야구 리그에서 특정 시점에 각 팀이 시즌을 1위로 마칠 수 있는 가능성이 있는지, 즉 탈락하지 않았는지를 판단하는 것이다.

이를 해결하기 위해 최대 유량 문제로의 환원이 사용된다. 특정 팀 k가 탈락하는지 확인하기 위해 흐름 네트워크를 구축한다. 네트워크에는 소스와 싱크 외에도 각 경기 쌍을 나타내는 게임 노드와 각 팀을 나타내는 팀 노드가 추가된다. 소스는 각 게임 노드에 연결되고, 그 용량은 두 팀 간의 남은 경기 수로 설정된다. 각 게임 노드는 해당 경기에 참여하는 두 팀의 노드에 연결된다. 마지막으로, 각 팀 노드는 싱크에 연결되며, 그 용량은 팀 k가 시즌을 1위로 마칠 수 있는 최대 승리 수를 제한하도록 설정된다.

이 네트워크에서 계산된 최대 유량 값이 특정 임계값(리그 내 남은 모든 경기 수)과 같다면, 팀 k는 아직 탈락하지 않았다고 판단할 수 있다. 이 방법은 복잡한 스포츠 리그의 시나리오 분석을 체계적인 최적화 문제로 변환하여 효율적으로 해결할 수 있게 한다. 이는 최대 유량 최소 컷 정리와 같은 네트워크 흐름 이론의 핵심 개념이 스포츠 분석과 같은 실용적인 분야에 직접 적용될 수 있음을 보여준다.

항공사 스케줄링 문제는 최대 유량 문제의 중요한 실제 응용 분야 중 하나이다. 이 문제는 항공사의 승무원이나 항공기를 효율적으로 배정하여 주어진 항공편 집합을 모두 수행할 수 있는 실행 가능한 스케줄을 찾는 것을 목표로 한다. 이때 최적화의 목표는 최소한의 승무원 수로 모든 항공편을 커버하거나, 주어진 제한된 수의 승무원으로 가능한 많은 항공편을 수행하는 것이다.

이 문제는 네트워크 흐름 문제의 일반화된 형태인 순환 문제의 변형, 특히 경계 순환(bounded circulation) 문제로 모델링될 수 있다. 네트워크는 각 항공편을 노드로 표현하고, 한 항공편의 도착지에서 다른 항공편의 출발지로 합리적인 시간 내에 이동 가능한 경우를 간선으로 연결하여 구성된다. 간선에는 용량과 더불어 흐름의 하한을 설정하는 제약이 추가된다. 이렇게 구성된 네트워크에서 특정 값의 흐름을 찾는 것은 주어진 항공편 집합을 수행하는 실행 가능한 승무원 스케줄을 찾는 것과 동치이다.

최소 승무원 수를 찾는 문제는 이분 그래프에서의 최대 이분 매칭 문제로도 환원되어 해결될 수 있다. 각 항공편을 두 개의 정점 집합에 복제하여, 동일한 승무원이 연속적으로 수행할 수 있는 항공편 간에 간선을 연결한다. 이 그래프에서 찾은 최대 매칭은 곧 최소 수의 승무원으로 모든 항공편을 커버하는 스케줄로 해석될 수 있으며, 최대 이분 매칭 문제는 앞서 설명된 바와 같이 최대 유량 문제의 한 응용이다.

순환-수요 문제는 최대 유량 문제의 중요한 응용 분야 중 하나이다. 이 문제는 여러 개의 공장과 마을이 도로 네트워크로 연결된 상황을 다룬다. 각 공장은 일정한 생산율로 물건을 생산하고, 각 마을은 일정한 수요율로 물건을 필요로 한다. 각 도로는 최대 물건 흐름을 위한 용량 제한을 가진다. 문제의 목표는 모든 마을의 수요를 동시에 만족시키는 물건의 순환이 네트워크에 존재하는지 판단하고, 존재한다면 그 흐름을 구체적으로 찾는 것이다.

이 문제는 최대 유량 문제로 변환하여 해결할 수 있다. 먼저, 하나의 가상의 소스 노드와 하나의 가상의 싱크 노드를 네트워크에 추가한다. 소스 노드는 모든 공장 노드와 연결되며, 연결 간선의 용량은 해당 공장의 생산율로 설정한다. 반대로, 모든 마을 노드는 싱크 노드와 연결되며, 연결 간선의 용량은 해당 마을의 수요율로 설정한다. 기존 도로의 용량은 그대로 유지한다. 이렇게 변환된 새로운 네트워크에서 소스에서 싱크로의 최대 유량을 계산한다. 만약 이 최대 유량 값이 모든 마을의 총 수요 합과 정확히 일치한다면, 원래 문제에서 수요를 만족시키는 순환이 존재함을 의미한다. 또한, 최대 유량 알고리즘을 통해 구체적인 해를 찾으면, 각 도로를 통해 얼마나 많은 물건을 운송해야 하는지에 대한 계획을 얻을 수 있다.

이 문제는 더 복잡한 제약 조건으로 확장될 수 있다. 예를 들어, 특정 도로를 통한 흐름이 최소한 일정량 이상이어야 한다는 하한 조건을 추가할 수 있다. 이러한 조건이 포함되면 문제는 유량 하한을 가진 순환 문제가 되며, 이는 최대 유량 문제의 또 다른 일반화 형태로 볼 수 있다. 순환-수요 문제와 그 변형들은 물류 계획, 공급망 관리, 통신 네트워크의 대역폭 할당 등 실제 세계의 다양한 자원 배분 문제를 모델링하는 데 유용하게 적용된다.

이미지 분할은 컴퓨터 비전 및 이미지 처리 분야에서 중요한 작업으로, 디지털 이미지를 의미 있는 부분 또는 영역으로 나누는 과정이다. 최대 유량 문제는 그래프 컷을 최적화하는 방식으로 이를 해결하는 데 효과적으로 활용된다.

이 접근법에서는 각 픽셀을 그래프의 정점으로 모델링한다. 소스 노드는 전경에, 싱크 노드는 배경에 대응되며, 각 픽셀은 소스 및 싱크와 연결된다. 소스와의 연결 간선 용량은 해당 픽셀이 전경에 속할 가능성(예: 픽셀 강도 기반)을, 싱크와의 연결 간선 용량은 배경에 속할 가능성을 반영한다. 인접한 픽셀 사이에도 간선이 존재하며, 이 간선의 용량은 두 픽셀이 서로 다른 영역(하나는 전경, 하나는 배경)에 할당될 때 부과되는 페널티를 나타낸다. 이 페널티는 일반적으로 픽셀 간의 유사도(예: 색상 또는 밝기 차이)에 기반하여 설정되며, 유사할수록 큰 페널티(용량)를 부여하여 분할 경계가 불연속적으로 나타나는 것을 방지한다.

이렇게 구성된 네트워크 흐름 그래프에서 최소 컷을 계산하면, 그래프가 소스 측(전경)과 싱크 측(배경)으로 분할된다. 최대 유량 최소 컷 정리에 따라, 이 최소 컷은 전경/배경 할당 가능성과 경계 부드러움 간의 트레이드오프를 최적으로 조절하여, 정의된 목적 함수를 최소화하는 이미지 분할 결과를 제공한다. 이 방법은 그래프 컷 기반 이미지 분할의 대표적인 예시이며, 영상 편집, 의료 영상 분석, 객체 인식 등 다양한 실제 응용 분야에서 사용된다.