[펌]Maximum Flow Problem(2)

최대흐름문제

• 네트워크상에서 각 가지에 흐를 수 있는 용량이 한정되어 있을 때 흘려 보낼 수 있는 최대의 유통량을 구하는 문제(여기서 흐름의 내용은 주로 원유, 식수, 가스 등의 유동체나 교통량, 정보량, 통신량 등)

  

• 예제 모형  : T 지역의 식수공급 문제

식수공급 네트워크

• 최대흐름문제의 발견적기법

1단계 공급지에서 수요지로 양의 용량을 갖는 경로를 선택한다. 이러한 경로를          선택할 수 없으면, 현재의 흐름량이 최대이다. 2단계 선택한 경로에 포함된 가지의 용량중 최소값을 그 경로의 흐름량으로          배정한다. 3단계 각 가지의 용량에 대해, 위에서 결정된 흐름량을 순방향으로는 빼주고          역방향으로는 더해준 다음 1단계로 간다.

• 첫 번째 배정 : 1단계로 양의 흐름용량을 갖는 임의의 경로를 선택
  : S→①→④→T 경로를 선택하면, 각 가지의 용량이 5, 3, 5이므로 3을 배정
  : 그 다음 단계로 흐름량 3을 순방향의 용량에서는 빼주고 역방향의 용량에는 더해준다.

첫 번째 배정 후의 용량 변화

• 두 번째 배정 : 경로 S→③→T를 선택, 흐름량 min{6, 3} = 3을 배정

두 번째 배정 후의 용량 변화

• 세 번째 배정 : S→②→⑤→T 경로에 2 배정

 

• 네 번째 배정 : S→①→②→③→④→T 경로에 2 배정

 

• 다섯 번째 배정 : S→③→⑤→T 경로에 2 배정

• 최종 배정 결과

• 수원지에서 공급할 수 있는 용량은 5 + 6 + 4 = 15이나, 중간경유지의 공급용량에 한계가 있기 때문에 최대흐름량은 12가 된다.

• 경로 선택의 차이에 따라 각 가지에 흐르는 양도 달라질 수도 있으나, 각 경로에 배정되는 양은 서로 다르더라도 네트워크의 최대흐름은 12로 변하지 않는다.

• 최소절단-최대흐름 정리(minimal cut- maximal flow theorem)
  : 네트워크상의 최대흐름은 네트워크를 절단하는 경로들의 집합 중 용량의 합이 최소인 값과 같다.
  : 이 문제에서 최대흐름량 12는 수원지와 수요지를 절단하는 경로의 집합 중 최소의 순방향 흐름량을 갖는 {④→T, ③→T, ⑤→T}의 순방향 용량의 합(5 + 3 + 4 = 12)이다.

 

출처 : http://secom.hanbat.ac.kr/or/ch09/right04.html#최대흐름문제