L-R flow : 하한이 있는 플로우

L-R flow

L-R flow란?

네트워크 플로우에서 각 간선에 흐를 수 있는 용량이 정해져 있듯이

무조건 흘러야 하는 하한이 정해지는 것이다.

이 하한을 어떻게 만족시켜야 할까? 

또는 하한을 만족시키면서 유량을 흘릴 수 있는지 어떻게 검사할까?

만약 a->b 간선을 e 라고 할 때, 이 간선에 흘러야 하는 하한을 l, 상한을 r이라고 하자.

또한 기존의 S,E 이외에 새로운 source 와 sink인 s,t 를 정의하자.

이떄 간선을 다음과 같이 구성하자

1. s -> b 로 cap = l 인 간선 (①에서 그래프에 하한인 l만 흐르게 하기 위함)

2. a -> t 로 cap = l 인 간선 (①에서 그래프에 하한인 l만 흐르게 하기 위함)

3. E -> S 로 cap = INF 인 간선 (①에서 S가 처음에 흘릴 유량에서 source가 아니기 때문에 무한한 유량을 제공하기 위함이다)

4. a -> b 로 cap = r-l 인 간선 (②에서 추가로 흐를 유량을 구하기 위함이다)

① 간선을 다음과 같이 구성한 후에 s에서 t로의 maxflow 를 구한다.

이 때의 maxflow == 간선 하한들의 합 과 같다면, 이 그래프는 하한을 만족하는 maxflow를 구할 수 있다는 것이다.

② 그 후에 한번 더 유량이 차있는 그래프 그대로 S에서 T로의 maxflow 를 구한다면, 하한을 만족한 후에 더 흘릴 수 있는 추가 유량을 구할 수 있다.

따라서 흐를 수 있는 유량은 ①maxflow(하한의 합)  + ②maxflow(추가 흐른양) 가 된다.