유량 네트워크편집자 확인

유량 네트워크에서 모든 유량의 흐름은 소스에서 시작하여 싱크에서 끝난다. 소스는 유량이 생성되어 나가는 지점이며, 싱크는 유량이 모여들어 소멸하는 지점이다. 이 두 특별한 정점은 네트워크 내 유량의 시작과 끝을 명확히 정의함으로써, 네트워크를 통해 얼마나 많은 유량을 보낼 수 있는지 계산하는 최대 유량 문제의 핵심이 된다.

소스와 싱크는 네트워크의 경계를 설정한다. 소스는 일반적으로 들어오는 간선이 없거나, 들어오는 간선의 용량이 0으로 설정된다. 반대로 싱크는 나가는 간선이 없거나, 나가는 간선의 용량이 0으로 설정된다. 이러한 구조는 유량이 외부에서 소스로 주입되어 싱크로 빠져나간다는 개념을 그래프로 모델링한 것이다.

실제 문제에 적용할 때는 소스와 싱크의 설정이 매우 중요하다. 예를 들어, 공급 창고에서 소비지로의 물자 이동, 데이터 센터에서 클라이언트로의 패킷 전송, 또는 한 직원 그룹에서 다른 작업 그룹으로의 업무 할당 문제를 유량 네트워크로 풀기 위해서는 먼저 공급 지점을 소스로, 수요 지점을 싱크로 정의해야 한다. 이렇게 모델링된 네트워크에서 포드-풀커슨 알고리즘이나 에드먼즈-카프 알고리즘과 같은 방법을 통해 소스에서 싱크로 흘려보낼 수 있는 최대 유량을 찾을 수 있다.

유량 네트워크는 방향 그래프로 표현되며, 이 그래프를 구성하는 기본 요소는 정점과 간선이다. 정점은 네트워크 내의 교차점이나 지점을 나타내며, 간선은 이러한 지점들을 연결하고 유량이 흐르는 통로의 역할을 한다.

정점은 소스, 싱크, 그리고 중간 정점으로 구분된다. 소스는 유량이 시작되는 지점이고, 싱크는 유량이 도착하는 지점이다. 소스와 싱크를 제외한 모든 중간 정점에서는 들어오는 유량의 총합과 나가는 유량의 총합이 항상 같아야 한다. 이는 유량 보존 법칙으로, 네트워크 내에서 유량이 생성되거나 소멸하지 않음을 의미한다.

간선은 두 정점을 연결하는 방향성을 가진 선이다. 각 간선에는 용량이라는 속성이 부여되어 있으며, 이는 해당 간선을 통해 흐를 수 있는 유량의 상한선을 정의한다. 또한, 각 간선에는 현재 흐르고 있는 유량의 값이 할당된다. 이 유량은 항상 0 이상이며, 해당 간선의 용량을 초과할 수 없다.

정점과 간선의 이러한 구조는 그래프 이론의 기본적인 틀을 따르면서도, 용량과 유량이라는 제약 조건을 추가함으로써 조합 최적화 문제를 모델링하는 강력한 도구가 된다. 네트워크의 전체 구조는 정점의 집합과 간선의 집합으로 완전히 정의될 수 있다.

유량 네트워크의 핵심은 각 간선에 부여된 용량과 그 위를 실제로 흐르는 유량이라는 두 가지 수치이다. 용량은 해당 간선을 통해 단위 시간당 흐를 수 있는 유량의 상한선을 의미한다. 예를 들어, 파이프라인의 최대 수송량이나 도로의 최대 통행량에 비유할 수 있다. 각 간선 e에 대해 용량 c(e)는 음이 아닌 실수로 정의된다.

반면 유량은 소스에서 싱크로 실제로 흐르고 있는 양을 나타낸다. 각 간선 e에 할당된 유량 f(e)는 두 가지 중요한 제약을 만족해야 한다. 첫째, 용량 제약으로, 유량은 용량을 초과할 수 없다. 둘째, 유량 보존 법칙으로, 소스와 싱크를 제외한 모든 중간 정점에서 들어오는 유량의 합과 나가는 유량의 합이 같아야 한다. 이 법칙은 물이나 차량, 데이터 패킷이 중간에서 새거나 쌓이지 않고 안정적으로 흐른다는 것을 보장한다.

네트워크 전체의 유량은 소스 정점에서 나가는 모든 유량의 합, 또는 싱크 정점으로 들어오는 모든 유량의 합으로 계산된다. 최대 유량 문제의 목표는 바로 이 네트워크 전체 유량을 최대화하는 유량 배분을 찾는 것이다. 이때 각 간선의 유량은 용량 범위 내에서 자유롭게 설정할 수 있지만, 유량 보존 법칙을 위반해서는 안 된다.

*유량 보존 법칙: 소스(s)와 싱크(t)가 아닌 모든 정점 v에 대해, v로 들어오는 유량의 합과 v에서 나가는 유량의 합이 같아야 한다.

최대 유량 문제는 유량 네트워크에서 가장 기본적이고 중요한 문제이다. 이 문제는 주어진 유량 네트워크에서 소스 정점에서 싱크 정점으로 흘려보낼 수 있는 유량의 최대값을 찾는 것을 목표로 한다. 여기서 유량은 네트워크의 각 간선을 따라 흐르는 양을 의미하며, 각 간선마다 정해진 용량을 초과할 수 없다.

이 문제를 공식적으로 정의하기 위해서는 유량이 만족해야 할 두 가지 기본 제약 조건이 있다. 첫째는 용량 제약으로, 각 간선을 흐르는 유량은 그 간선의 용량을 초과할 수 없다. 둘째는 유량 보존 법칙으로, 소스와 싱크를 제외한 모든 중간 정점에서 들어오는 유량의 총합과 나가는 유량의 총합이 항상 같아야 한다. 즉, 중간 정점에서는 유량이 쌓이거나 감소하지 않는다.

이러한 조건 하에서 소스에서 싱크로 흘러가는 총 유량을 최대화하는 것이 최대 유량 문제의 핵심이다. 이 문제는 1956년 레스터 R. 포드 주니어와 델버트 R. 풀커슨에 의해 체계적으로 연구되기 시작했으며, 그래프 이론과 조합 최적화 분야의 중요한 주제로 자리 잡았다. 이 문제의 해법은 이후 다양한 알고리즘의 개발로 이어졌다.

최대 유량 문제는 단순히 이론적인 문제를 넘어, 실제 통신 네트워크의 대역폭 계산, 교통 체계의 최대 수송량 분석, 물류 시스템의 효율화 등 운용 과학의 다양한 분야에서 폭넓게 응용된다.

잔여 네트워크는 주어진 유량 네트워크와 현재의 유량 배분 상태를 바탕으로, 추가적인 유량을 보낼 수 있는 가능성을 나타내는 보조 그래프이다. 이 개념은 포드-풀커슨 알고리즘과 같은 최대 유량 알고리즘의 핵심 동작 원리이다. 알고리즘은 초기 유량(보통 0)에서 시작하여, 잔여 네트워크 상에서 소스에서 싱크로 가는 경로를 반복적으로 찾아 유량을 증가시킴으로써 최종 해를 도출한다.

잔여 네트워크는 원래 네트워크의 각 간선에 대해 두 가지 정보를 고려하여 구성된다. 첫째는 해당 간선에 추가로 보낼 수 있는 잔여 용량이다. 간선의 현재 유량이 f이고 용량이 c라면, 순방향으로는 c - f만큼의 유량을 더 보낼 수 있다. 둘째는 이미 흐르고 있는 유량을 반대 방향으로 "되돌릴" 수 있는 가능성이다. 이는 반대 방향 간선에 f만큼의 용량을 부여하는 것으로 해석되며, 이를 통해 알고리즘이 이전에 선택한 유량 경로를 부분적으로 취소하고 더 나은 경로를 재구성할 수 있게 한다.

따라서 잔여 네트워크의 정점 집합은 원래 그래프와 동일하지만, 간선 집합과 그 용량은 다르다. 구체적으로, 원래 그래프의 모든 간선 (u, v)에 대해 잔여 용량이 양수이면 잔여 네트워크에 동일한 방향의 간선을 포함시키고, 그 용량을 잔여 용량으로 설정한다. 동시에 현재 유량 f가 양수인 모든 간선에 대해, 잔여 네트워크에는 반대 방향의 간선 (v, u)를 포함시키고 그 용량을 f로 설정한다. 이 반대 방향 간선을 역간선이라고 부르기도 한다.

잔여 네트워크 상에서 소스에서 싱크로 가는 경로를 증가 경로라고 한다. 이 경로를 따라 흘려보낼 수 있는 유량의 최대값은 경로 상 모든 간선의 잔여 용량 중 최솟값으로 결정된다. 알고리즘은 이러한 증가 경로가 더 이상 존재하지 않을 때까지 유량을 증가시키며, 이 상태가 바로 원래 네트워크에서의 최대 유량에 도달했음을 의미한다. 에드먼즈-카프 알고리즘은 이 증가 경로를 찾는 방법을 너비 우선 탐색으로 특정함으로써 알고리즘의 효율성을 크게 향상시킨 대표적인 예이다.

증가 경로는 유량 네트워크에서 현재의 유량을 더 증가시킬 수 있는 가능성을 나타내는 경로이다. 소스에서 싱크까지 이어지는 일련의 간선들로 구성되며, 이 경로를 따라 추가적인 유량을 보낼 수 있어야 한다. 증가 경로의 존재 여부는 현재 유량이 최대인지 아닌지를 판단하는 핵심 기준이 된다. 포드-풀커슨 알고리즘과 에드먼즈-카프 알고리즘을 비롯한 많은 최대 유량 알고리즘은 증가 경로를 반복적으로 찾아 유량을 증가시키는 방식을 기본 원리로 삼는다.

증가 경로는 잔여 네트워크 상에서 정의된다. 잔여 네트워크는 현재 유량 상태에서 추가로 유량을 보내거나 기존 유량을 되돌릴(역방향으로 흘릴) 수 있는 잔여 용량을 간선의 가중치로 가지는 그래프이다. 따라서 소스에서 싱크까지의 경로가 잔여 네트워크 상에 존재한다는 것은, 그 경로를 구성하는 모든 간선에 아직 사용하지 않은 용량이 남아 있거나, 역방향 간선을 통해 유량을 상쇄할 수 있음을 의미한다. 이 경로를 따라 흘릴 수 있는 유량의 최대량은 경로 상 간선들의 잔여 용량 중 최솟값으로 결정된다.

증가 경로를 이용한 유량 증가 과정은 다음과 같다. 먼저 잔여 네트워크에서 소스에서 싱크로 가는 임의의 경로를 찾는다. 이 경로를 따라 흘릴 수 있는 최대 유량, 즉 경로 상 최소 잔여 용량을 계산한다. 그 후, 원래의 유량 네트워크에서 이 경로를 따라 해당 양만큼 유량을 추가한다. 이때 순방향 간선에는 유량을 증가시키고, 역방향 간선(유량이 상쇄되는 경우)에는 유량을 감소시킨다. 이 과정을 잔여 네트워크에서 더 이상 증가 경로를 찾을 수 없을 때까지 반복한다.

증가 경로 기반 알고리즘의 효율성은 증가 경로를 찾는 방법과 선택하는 증가 경로의 특성에 크게 의존한다. 예를 들어, 에드먼즈-카프 알고리즘은 너비 우선 탐색을 사용해 가장 짧은(간선 수가 가장 적은) 증가 경로를 찾아 성능을 보장하며, 디닉 알고리즘은 레벨 그래프를 구성하고 깊이 우선 탐색을 통해 여러 증가 경로를 한꺼번에 찾는 방식을 사용한다. 증가 경로가 더 이상 존재하지 않는 상태가 바로 최대 유량에 도달한 상태이며, 이는 최대 유량 최소 컷 정리에 의해 최소 컷의 용량과 같음을 알 수 있다.

포드-풀커슨 알고리즘은 최대 유량 문제를 해결하기 위한 일반적인 방법론이다. 이 알고리즘은 1956년 레스터 R. 포드 주니어와 델버트 R. 풀커슨에 의해 제안되었으며, 그래프 이론과 조합 최적화 분야의 기초적인 알고리즘 중 하나로 자리 잡았다. 알고리즘의 핵심 아이디어는 소스에서 싱크까지 유량을 보낼 수 있는 경로, 즉 증가 경로를 반복적으로 찾아 유량을 흘려보내는 것이다.

알고리즘은 잔여 네트워크 개념을 바탕으로 작동한다. 초기 유량을 0으로 설정한 후, 소스에서 싱크로 향하는 증가 경로를 탐색한다. 탐색된 경로를 따라 흘릴 수 있는 최대 유량, 즉 잔여 용량 중 최소값을 결정하고, 해당 경로의 모든 간선에 그만큼의 유량을 추가한다. 이 과정은 더 이상 증가 경로를 찾을 수 없을 때까지 반복되며, 이때 네트워크에 흐르는 총 유량이 최대 유량이 된다.

포드-풀커슨 알고리즘은 방법론의 틀을 제시하지만, 증가 경로를 찾는 구체적인 방법은 다양하다. 가장 단순한 방법은 깊이 우선 탐색이나 너비 우선 탐색을 사용하는 것이다. 그러나 증가 경로를 선택하는 전략에 따라 알고리즘의 성능이 크게 달라질 수 있다. 특히 용량이 무리수인 경우 알고리즘이 종료되지 않거나 최적해에 수렴하지 않을 수도 있다는 점이 이론적으로 알려져 있다.

이 알고리즘은 구현이 비교적 간단하고 개념이 직관적이라는 장점이 있다. 그러나 효율성 측면에서는 한계가 있어, 이후 에드먼즈-카프 알고리즘이나 디닉 알고리즘과 같이 보다 효율적인 알고리즘들이 개발되었다. 그럼에도 불구하고 포드-풀커슨 알고리즘은 최대 유량 문제에 대한 근본적인 접근법을 제공한다는 점에서 중요한 의미를 지닌다.

에드먼즈-카프 알고리즘은 포드-풀커슨 알고리즘의 구체적인 구현 방식 중 하나이다. 이 알고리즘은 잔여 네트워크에서 소스에서 싱크까지의 증가 경로를 찾을 때 너비 우선 탐색을 사용한다는 점이 핵심 특징이다. 이로 인해 경로를 찾는 순서가 정해져 있으며, 이는 알고리즘의 시간 복잡도를 보장하는 데 결정적인 역할을 한다.

포드-풀커슨 알고리즘은 증가 경로를 임의로 선택할 수 있어 비효율적인 경우가 있었으나, 에드먼즈-카프 알고리즘은 항상 가장 적은 수의 간선으로 구성된 최단 증가 경로를 우선적으로 찾는다. 이 전략은 알고리즘이 최대 유량을 찾기 위해 필요한 증가 경로 탐색 횟수를 제한한다. 결과적으로, 정점의 수를 V, 간선의 수를 E라고 할 때, 이 알고리즘의 시간 복잡도는 O(V * E^2)으로 보장된다.

이 알고리즘은 그래프 이론과 네트워크 흐름 문제를 다루는 기본적인 도구로 널리 사용된다. 특히 구현이 비교적 간단하면서도 효율성이 보장되기 때문에 최대 유량 문제를 학습하고 이해하는 데 있어 중요한 교재 역할을 한다. 이후에 개발된 더 빠른 디닉 알고리즘이나 프리플로우-푸시 알고리즘과 같은 고급 알고리즘들의 기초를 이루는 개념을 제공하기도 한다.

디닉 알고리즘은 최대 유량 문제를 해결하는 효율적인 알고리즘 중 하나이다. 이 알고리즘은 1970년 야코프 디닉에 의해 제안되었으며, 에드먼즈-카프 알고리즘과 마찬가지로 포드-풀커슨 알고리즘의 일반적인 프레임워크 내에서 작동하지만, 레벨 그래프를 구성하고 차단 유량을 찾는 방식을 통해 시간 복잡도를 개선하였다.

알고리즘은 반복적으로 두 단계를 수행한다. 첫 번째 단계에서는 너비 우선 탐색을 사용하여 소스로부터 각 정점까지의 최단 거리(간선의 개수)를 계산하고, 이를 기반으로 잔여 용량이 있는 간선만을 포함하며 소스에서 싱크로 향하는 레벨 그래프를 생성한다. 두 번째 단계에서는 생성된 레벨 그래프 위에서 깊이 우선 탐색을 수행하여 소스에서 싱크로 가는 여러 경로를 동시에 탐색하며 차단 유량을 찾아 네트워크에 흘려보낸다. 차단 유량이 더 이상 발견되지 않으면 다시 레벨 그래프를 구성하는 단계로 돌아간다.

디닉 알고리즘의 시간 복잡도는 O(V²E)이다. 여기서 V는 정점의 수, E는 간선의 수를 의미한다. 특히 이분 그래프에서의 최대 유량 문제와 같이 특정 조건에서는 O(√V E)의 더 빠른 수행 시간을 보인다. 이는 각 단계에서 찾은 차단 유량이 상당히 크기 때문에 레벨 그래프를 재구성해야 하는 횟수가 크게 줄어들기 때문이다. 이러한 효율성 덕분에 간선의 수가 많은 조밀한 그래프에서도 실용적으로 사용된다.

최대 유량 최소 컷 정리는 유량 네트워크 이론의 핵심 정리이다. 이 정리는 소스에서 싱크로 흐를 수 있는 최대 유량의 값이, 네트워크를 소스와 싱크로 분리하는 모든 컷 중 가장 작은 컷의 용량과 정확히 일치함을 보여준다. 즉, 네트워크의 전체적인 흐름 용량은 가장 좁은 병목 지점에 의해 결정된다는 직관을 수학적으로 엄밀하게 증명한 것이다.

컷은 정점의 집합을 소스가 포함된 집합 S와 싱크가 포함된 집합 T로 분할하는 것을 의미한다. 이때 S에서 T로 향하는 모든 간선을 가로지르는 유량의 총합을 컷의 유량이라 하며, 이들 간선의 용량 합을 컷의 용량이라 한다. 최대 유량 최소 컷 정리는 최대 유량 f의 값이 모든 가능한 컷의 용량 중 최솟값, 즉 최소 컷의 용량 c와 동일함(f = c)을 주장한다.

이 정리는 1956년 레스터 R. 포드 주니어와 델버트 R. 풀커슨에 의해 증명되었으며, 그들의 포드-풀커슨 알고리즘은 이 정리를 바탕으로 최대 유량을 찾는 구체적인 방법을 제시한다. 알고리즘은 증가 경로를 반복적으로 찾아 유량을 증가시키다가 더 이상의 증가 경로가 존재하지 않을 때 종료하는데, 이 시점에서의 유량이 최대 유량이자 동시에 최소 컷의 용량이 된다.

이 정리는 단순히 이론적 중요성을 넘어 실용적 가치가 크다. 최대 유량 문제를 해결하는 알고리즘의 정당성을 보장할 뿐만 아니라, 네트워크에서 병목 현상을 정확히 찾아내는 최소 컷 문제를 푸는 데 직접적으로 활용된다. 이는 통신 네트워크의 대역폭 분석, 교통 흐름 분석에서의 정체 구간 식별, 운용 과학의 다양한 자원 배분 문제 등에 응용된다.

컷은 유량 네트워크의 정점 집합을 두 개의 부분집합으로 나누는 것이다. 구체적으로, 소스 s가 속한 집합 S와 싱크 t가 속한 집합 T로 정점 전체 집합 V를 분할(S ∪ T = V, S ∩ T = ∅)한 것을 (S, T) 컷이라 부른다.

컷의 용량은 S에 속한 정점에서 T에 속한 정점으로 나가는 모든 간선의 용량 합으로 정의한다. 반대 방향(T에서 S로 들어오는 간선)의 용량은 계산에 포함하지 않는다. 이는 네트워크를 가로지르는 병목 현상을 수치화한 개념으로, 컷의 용량은 해당 분할을 통해 싱크로 흘려보낼 수 있는 최대 유량의 이론적 상한을 의미한다.

최대 유량 최소 컷 정리에 따르면, 어떤 유량 네트워크에서 소스에서 싱크로 흘려보낼 수 있는 최대 유량의 값은 모든 가능한 컷 중 최소 용량을 가진 컷의 용량과 정확히 일치한다. 이 정리는 조합 최적화의 중요한 정리 중 하나이며, 최대 유량 문제와 최소 컷 문제가 쌍대 관계에 있음을 보여준다.

최소 컷을 찾는 것은 네트워크의 취약점을 분석하거나 자원 배분의 효율성을 평가하는 데 활용된다. 예를 들어, 통신망에서 최소 컷은 네트워크 신뢰성을 결정하는 핵심 링크 집합을 의미하며, 교통 흐름 분석에서는 도로망의 병목 지점을 식별하는 데 사용될 수 있다.

이분 매칭 문제는 유량 네트워크를 활용하여 효율적으로 해결할 수 있는 대표적인 응용 사례이다. 이 문제는 두 개의 정점 집합이 존재할 때, 각 집합 내 정점들끼리는 간선으로 연결되지 않고 오직 서로 다른 집합의 정점들 사이에만 간선이 존재하는 이분 그래프에서, 서로 인접한 정점들을 최대한 많이 짝지어주는 것을 목표로 한다. 이러한 매칭은 구인구직, 과제 배정, 주차 공간 할당 등 다양한 실생활 문제를 모델링하는 데 사용된다.

이분 매칭 문제를 최대 유량 문제로 변환하는 방법은 다음과 같다. 먼저, 주어진 이분 그래프에 하나의 소스 정점과 하나의 싱크 정점을 새로 추가한다. 그리고 소스 정점은 첫 번째 정점 집합의 모든 정점에, 싱크 정점은 두 번째 정점 집합의 모든 정점에 각각 용량 1의 간선으로 연결한다. 원래 이분 그래프의 간선들은 방향을 첫 번째 집합에서 두 번째 집합으로 설정하고, 용량을 1로 설정한다. 이렇게 구성된 유량 네트워크에서 소스에서 싱크로 흐를 수 있는 최대 유량의 값이 바로 최대 매칭의 크기가 된다.

이 변환을 통해 포드-풀커슨 알고리즘이나 더 효율적인 에드먼즈-카프 알고리즘과 같은 최대 유량 알고리즘을 직접 적용할 수 있다. 특히 모든 간선의 용량이 정수 1이므로 알고리즘의 동작이 단순화되고, 시간 복잡도 측면에서도 유리한 경우가 많다. 이 접근법은 기본적인 이분 매칭뿐만 아니라, 각 정점이 여러 개의 간선에 연결될 수 있는 등 더 복잡한 제약이 있는 문제로도 확장하여 적용할 수 있다.

유량 네트워크는 도로, 철도, 항공로 등 복잡한 교통망의 흐름을 모델링하고 분석하는 데 효과적으로 활용된다. 교통 시스템은 차량, 열차, 항공기 등이 특정 지점에서 다른 지점으로 이동하며, 경로별 수용 능력과 실제 통행량이 존재한다는 점에서 유량 네트워크와 구조적으로 유사하다. 따라서 도시의 교통 체증 완화, 주요 간선 도로의 용량 설계, 대중교통 노선의 효율성 평가 등 다양한 문제를 최대 유량 문제나 최소 비용 최대 유량 문제로 변환하여 해결할 수 있다.

구체적인 응용 사례로는 도시 내 교차로를 정점으로, 도로를 간선으로 모델링할 수 있다. 각 도로의 최대 통행 가능 차량 수는 간선의 용량에 해당하며, 실제 통행량은 유량으로 표현된다. 특정 출발지(예: 주거 지역)를 소스로, 도착지(예: 업무 지구)를 싱크로 설정하면, 네트워크를 통해 소스에서 싱크로 흘려보낼 수 있는 최대 차량 수, 즉 최대 유량을 계산함으로써 해당 통행走廊의 이론적 최대 처리 능력을 파악할 수 있다.

이러한 분석은 단순히 이론적 용량을 계산하는 것을 넘어, 교통 신호 제어 최적화, 환승 중심의 대중교통 네트워크 설계, 심지어 물류 배송 경로 최적화와 같은 실용적인 의사결정에도 직접적으로 기여한다. 예를 들어, 화물 터미널에서 여러 배송 차량이 동시에 목적지로 물건을 운반해야 할 때, 네트워크 전체의 효율을 최대화하면서도 각 경로의 제약 조건을 만족시키는 배차 계획을 수립하는 데 유량 이론이 적용될 수 있다.

통신 네트워크는 유량 네트워크 이론이 실질적으로 응용되는 대표적인 분야이다. 통신망은 데이터 패킷이 라우터나 스위치 같은 노드를 거쳐 목적지까지 전달되는 구조로, 이는 소스에서 싱크로 유량이 흐르는 유량 네트워크와 본질적으로 동일하다. 네트워크의 각 링크(간선)는 대역폭이라는 용량을 가지며, 실제 전송되는 데이터 트래픽은 유량에 해당한다. 따라서 네트워크의 전체 처리량을 최대화하거나 특정 링크의 혼잡을 방지하는 문제는 최대 유량 문제나 최소 컷 문제로 모델링하여 해결할 수 있다.

예를 들어, 데이터 센터 내 서버 간 통신이나 광역 통신망에서의 트래픽 엔지니어링에 유량 네트워크 모델이 활용된다. 네트워크 관리자는 포드-풀커슨 알고리즘이나 에드먼즈-카프 알고리즘과 같은 알고리즘을 적용하여, 제한된 대역폭 내에서 가능한 최대 데이터 전송률을 계산하고 효율적인 라우팅 경로를 결정할 수 있다. 또한, 최대 유량 최소 컷 정리를 통해 네트워크에서 병목 현상을 일으키는 가장 취약한 링크 집합(최소 컷)을 찾아내어, 이를 증설함으로써 네트워크 신뢰성과 성능을 개선하는 데 기여한다.

기본적인 유량 네트워크는 하나의 소스와 하나의 싱크를 가정한다. 그러나 실제 문제에서는 유량이 여러 지점에서 시작하거나 여러 지점에서 끝나는 경우가 흔하다. 예를 들어, 여러 공장에서 생산된 물품이 여러 도시의 창고로 배송되는 물류 시스템이나, 여러 송신기가 여러 수신기로 데이터를 전송하는 통신 네트워크가 이에 해당한다.

이러한 문제를 다루기 위해 다중 소스와 다중 싱크를 가진 네트워크는 하나의 가상의 슈퍼 소스와 슈퍼 싱크를 도입하여 기존의 단일 소스-싱크 문제로 변환한다. 구체적으로, 모든 실제 소스들을 새로운 슈퍼 소스에 무한한 용량의 간선으로 연결하고, 모든 실제 싱크들을 새로운 슈퍼 싱크에 무한한 용량의 간선으로 연결한다. 이 변환을 통해 포드-풀커슨 알고리즘이나 에드먼즈-카프 알고리즘과 같은 기존의 최대 유량 알고리즘을 그대로 적용할 수 있다.

이 접근법은 운용 과학과 조합 최적화 분야에서 광범위하게 사용된다. 특히 교통 흐름 분석에서 여러 출발지와 목적지를 가진 차량 흐름을 모델링하거나, 전력망에서 여러 발전소에서 여러 변전소로의 전력 공급 계획을 수립하는 데 활용된다.

하한 유량은 기본적인 유량 네트워크 문제의 한 가지 확장 형태이다. 기존 모델에서는 각 간선을 흐르는 유량이 0 이상이고 용량 이하라는 제약만 존재한다. 그러나 하한 유량 문제에서는 각 간선에 최소 유량 하한이 추가로 주어진다. 즉, 특정 간선을 반드시 일정량 이상의 유량이 흘러야 한다는 조건이 생긴다.

이러한 제약은 실제 문제를 모델링할 때 유용하다. 예를 들어, 특정 물류 경로에 최소한의 화물을 보장해야 하거나, 통신망에서 특정 회선에 최소 대역폭을 할당해야 하는 경우를 표현할 수 있다. 하한 유량 문제는 주어진 하한 조건을 만족시키면서 소스에서 싱크로 흘려보낼 수 있는 최대 유량을 찾거나, 그러한 유량이 존재하는지 여부를 판단하는 문제로 정의된다.

하한 유량 문제를 해결하는 일반적인 방법은 새로운 유량 네트워크를 구성하여 기존의 최대 유량 알고리즘을 적용하는 것이다. 먼저, 각 간선의 하한을 만족시키는 초기 유량을 찾거나, 존재 가능성을 검증한다. 이후, 잔여 네트워크를 적절히 변형하여 최대 유량 알고리즘을 실행함으로써 하한 조건을 만족하는 최대 유량을 구할 수 있다. 이 과정에서 포드-풀커슨 알고리즘이나 에드먼즈-카프 알고리즘과 같은 기존 알고리즘이 활용된다.

하한 유량은 최소 비용 최대 유량 문제와 결합되어 더 복잡한 조건을 모델링할 때도 사용된다. 즉, 각 간선에 유량의 하한과 상한(용량), 그리고 유량 단위당 비용이 모두 주어질 수 있다. 이러한 확장 모델은 운용 과학과 물류 시스템 설계, 네트워크 공학 등 다양한 분야에서 실용적인 최적화 문제를 해결하는 데 적용된다.

최소 비용 최대 유량 문제는 최대 유량 문제의 중요한 확장 형태이다. 이 문제에서는 각 간선에 용량과 함께 단위 유량을 보내는 데 드는 비용이 추가로 주어진다. 목표는 소스에서 싱크로 보낼 수 있는 최대 유량을 찾되, 그 최대 유량을 달성하는 여러 방법 중에서 총 비용이 가장 작은 유량 배분을 찾는 것이다. 이는 운용 과학과 물류 계획, 통신 네트워크 설계 등에서 자원을 가장 경제적으로 운송하는 방법을 모델링하는 데 유용하다.

이 문제를 해결하는 대표적인 알고리즘으로는 최소 비용 유량 알고리즘이 있다. 이 알고리즘은 기본적으로 포드-풀커슨 알고리즘의 프레임워크를 따르지만, 증가 경로를 선택할 때 비용을 고려한다. 매 단계에서 잔여 네트워크 상에서 소스에서 싱크까지의 최단 경로(비용 기준)를 찾아 그 경로를 따라 유량을 증가시킨다. 이때 경로 탐색에는 벨만-포드 알고리즘이나 다익스트라 알고리즘과 같은 최단 경로 알고리즘이 사용된다.

최소 비용 최대 유량 문제는 최소 비용 최대 유량 알고리즘을 통해 해결되며, 그 결과는 네트워크를 통해 흐르는 총 유량과 그때의 최소 총 비용이다. 이 알고리즘은 선형 계획법의 특수한 경우로도 볼 수 있으며, 교통 흐름 분석이나 공급망 관리에서 운송 경로 최적화, 에너지 배분 시스템 설계 등 다양한 실용적인 문제에 적용된다.