수요가 있는 흐름¶
일반적인 흐름 네트워크에서 간선의 흐름은 위로는 용량 $c(e)$에 의해, 아래로는 0에 의해서만 제한됩니다. 이 글에서는 각 간선의 흐름이 일정한 양을 가지도록 추가로 요구하는 흐름 네트워크, 즉 흐름을 수요(demand) 함수 $d(e)$로 아래에서 제한하는 흐름 네트워크를 다룹니다:
따라서 이제 각 간선에는 그 간선을 따라 반드시 흘려보내야 하는 최소 흐름 값이 있습니다.
모든 간선 $e$에 대해 $d(e) = 0$으로 두면 일반적인 흐름 네트워크가 되므로, 이는 일반적인 흐름 문제의 일반화입니다. 일반적인 흐름 네트워크에서는 유효한 흐름을 찾는 것이 매우 자명하다는 점에 주목하십시오. $f(e) = 0$으로 두기만 해도 이미 유효한 흐름입니다. 그러나 각 간선의 흐름이 수요를 만족해야 한다면, 유효한 흐름을 찾는 것만으로도 갑자기 상당히 복잡해집니다.
다음 두 가지 문제를 살펴보겠습니다:
- 모든 제약 조건을 만족하는 임의의 흐름 찾기
- 모든 제약 조건을 만족하는 최소 흐름 찾기
임의의 흐름 찾기¶
네트워크를 다음과 같이 변경합니다. 새로운 소스 $s'$와 새로운 싱크 $t'$를 추가하고, 소스 $s'$에서 다른 모든 정점으로 향하는 새 간선, 모든 정점에서 싱크 $t'$로 향하는 새 간선, 그리고 $t$에서 $s$로 향하는 간선 하나를 추가합니다. 또한 새로운 용량 함수 $c'$를 다음과 같이 정의합니다:
- 각 간선 $(s', v)$에 대해 $c'((s', v)) = \sum_{u \in V} d((u, v))$입니다.
- 각 간선 $(v, t')$에 대해 $c'((v, t')) = \sum_{w \in V} d((v, w))$입니다.
- 기존 네트워크의 각 간선 $(u, v)$에 대해 $c'((u, v)) = c((u, v)) - d((u, v))$입니다.
- $c'((t, s)) = \infty$
새 네트워크에 포화 흐름(saturating flow, $s'$에서 나가는 모든 간선이 완전히 채워진 흐름으로, $t'$로 들어오는 모든 간선이 완전히 채워진 것과 동치입니다)이 존재하면, 수요가 있는 네트워크에 유효한 흐름이 존재하며 실제 흐름은 새 네트워크로부터 쉽게 복원할 수 있습니다. 그렇지 않으면 모든 조건을 만족하는 흐름은 존재하지 않습니다. 포화 흐름은 반드시 최대 흐름이어야 하므로, Edmonds-Karp 알고리즘이나 Push-relabel 알고리즘과 같은 임의의 최대 흐름 알고리즘으로 찾을 수 있습니다.
이러한 변환이 올바른 이유는 이해하기가 더 어렵습니다. 다음과 같이 생각해 볼 수 있습니다: $d(e) > 0$인 각 간선 $e = (u, v)$는 원래 두 개의 간선으로 대체됩니다. 하나는 용량이 $d(i)$이고, 다른 하나는 용량이 $c(i) - d(i)$입니다. 우리는 첫 번째 간선을 포화시키는 흐름을 찾고자 합니다(즉, 이 간선을 따라 흐르는 흐름은 그 용량과 같아야 합니다). 두 번째 간선은 덜 중요합니다. 용량을 초과하지만 않는다면 그 간선을 따라 흐르는 흐름은 어떤 값이든 될 수 있습니다. 포화되어야 하는 각 간선에 대해 다음 연산을 수행합니다: 새 소스 $s'$에서 그 간선의 끝점 $v$로 간선을 긋고, 그 간선의 시작점 $u$에서 새 싱크 $t'$로 간선을 긋고, 간선 자체를 제거한 뒤, 기존 싱크 $t$에서 기존 소스 $s$로 용량이 무한인 간선을 긋습니다. 이러한 조작으로 이 간선이 포화되었다는 사실을 모사합니다. $v$에서는 $d(e)$만큼의 흐름이 추가로 나가게 되고(이는 $v$에 적절한 양의 흐름을 공급하는 새 소스로 모사합니다), $u$ 또한 $d(e)$만큼의 흐름을 추가로 밀어냅니다(다만 이 흐름은 기존 간선을 따라가는 대신 새 싱크 $t'$로 곧바로 갑니다). 원래 경로 $s - \dots - u - v - \dots t$를 따라 흐르던 값 $d(e)$의 흐름은 이제 새 경로 $s' - v - \dots - t - s - \dots - u - t'$를 택할 수 있습니다. 새 네트워크의 정의에서 단순화한 것은 단 하나로, 이 과정에서 같은 정점 쌍 사이에 다중 간선이 생기면 그 간선들을 용량을 합한 하나의 간선으로 합친다는 점입니다.
최소 흐름¶
용량이 $\infty$인 간선 $(t, s)$(이전 싱크에서 이전 소스로 향하는 간선)를 따라 대응하는 이전 네트워크의 흐름 전체가 흐른다는 점에 주목하십시오. 즉, 이 간선의 용량은 이전 네트워크의 흐름 값에 영향을 줍니다. 이 간선에 충분히 큰 용량(즉, $\infty$)을 부여하면 이전 네트워크의 흐름은 제한되지 않습니다. 이 간선의 용량을 더 작게 제한하면 흐름 값이 감소합니다. 그러나 이 간선을 너무 작은 값으로 제한하면 네트워크는 포화된 해를 갖지 못하게 됩니다. 즉, 원래 네트워크에 대응하는 해가 간선들의 요구량을 만족하지 못합니다. 따라서 여기서는 이진 탐색을 사용하여 모든 제약 조건을 여전히 만족하는 가장 작은 값을 찾을 수 있습니다. 이렇게 하면 원래 네트워크의 최소 흐름을 얻을 수 있습니다.