[그래프] Graph 12: 네트워크 모델링(Network flow): 예제를 통한 그래프 표현

1. 네트워크 모델링

네트워크 유량 문제를 풀 때는 특히나 주어진 문제를 어떻게 그래프로 표현할 것인가가 중요하다.

 

예제를 통해 그래프를 어떻게 표현할 것인지를 알아보자

 

 

 

2. MILEAGE 마일리지로 여행하기: 자원 분배

신용카드 포인트와 항공사 마일리지 포인트, 이동 통신사 멤버십 포인트 등을 모아서 

 

여행중 쓰려고 한다.

 

한 종류의 마일리지를 여러 개의 결제 항목에 나눠서 쓸 수 있으며,

 

한 가지 항목을 여러 개의 마일리지와 현금을 합쳐 결제 하는 것도 가능하다.

 

단 각 마일리지마다 사용할 수 있는 항목에 제한이 있기 때문에, 어느 마일리지로 무엇을 결제할지 신중해야한다.

 

결제해야하는 항목들의 가격과 각 마일리지에 쌓인 금액,

 

각 결제 항목마다 사용할 수 있는 마일리지의 목록이 주어질 때,

 

사용해야하는 최소 현금은 얼마인지 계산하는 프로그램을 작성하여라.

 

풀이

이 문제 자체는 그래프와 아무런 관련이 없어보인다.

 

하지만  양과 사용처가 제한된 자원을 효율적으로 분배하는 방법을 찾는 문제는 네트워크 유량으로 해결할 수 있다.

 

 

각 마일리지가 각 결제 항목에 사용 금액을 '보내 준다'고 생각하는 것이다.

 

마일리지 금액에 따라 사용 금액을 보내줄 수 있는 결제 항목이 다르고,

 

각 마일리지 항목마다 보내줄 수 있는 최대 금액,

 

각 결제 항목마다 받을 수 있는 최대 금액이 정해져 있다.

 

이 때 마일리지 사용량을 최대화하는 것이므로 유량 네트워크로 충분히 표현할 수 있다.

 

 

 

위 그래프는 이 문제를 유량 네트워크를 표현한 것이다.

 

노란 정점 = 마일리지

0, 9를 제외한 흰 정점 = 결제 항목

 

0 = 소스

9 = 싱크

 

각 마일리지는 사용할 수 있는 결제 항목으로 유량을 무한정 보낼 수 있다.

 

그러나 각 마일리지가 보낼 수 있는 유량의 최대량과 각 결제 항목이 받을 수 있는 유량의 최대량은

 

각각 소스와 싱크로 이어진 간선의 용량에 의해 제한된다.

 

따라서 이 간선들의 용량을 마일리지 잔액 혹은 해당 결제 항목의 가격으로 두면 된다.

 

이 그래프에서 최대 유량은 사용 가능한 마일리지의 양을 최대화 하며

 

따라서 결제해야하는 금액에 이것을 빼면 사용해야 하는 현금의 양의 최소값을 구할 수 있다.

 

 

 

 

3. SAINTTAIL 도난당한 조각상: 정점의 가중치

박물관 s에서 훔친 조각상들을 항구 도시 t로 보냈다고 한다.

 

이때 조각상들을 화물 열차를 이용하여 여러개의 기차역과 노선을 이용했다고 한다.

 

경찰이 모든 차량을 감시하려고하는데 이때 기차역의 혼잡도에 따라 배치해야할 수사관의 수가 달라진다.

 

s에서 t로 가는 모든 경로가 수사관이 배치된 역을 한 번 이상 지나도록 하기위해 

 

배치해야 할 최소 수사관의 수를 구하여라.

 

 

 

풀이

두 정점 s 와 t 사이에 가능한 모든 경로를 감시한다는 문제를

 

s와 t 사이의 연결을 끊어 버리는 문제로 변형해보자.

 

둘은 사실상 같은 문제이다.

 

두 번째 형태로 풀어 쓰면 그래프의 최소 컷 문제와 비슷하게 된다.

 

 

최소 컷은 s를 포함하는 정점의 집합과 t를 포함하는 정점의 집합으로 나눈 뒤,

 

두 집합을 잇는 간선 용량의 합을 최소화한다.

 

따라서 만약 이 문제가 각 간선을 감시하는 문제였다면 최소 컷 으로 간단하게 풀렸을 것이다.

 

 

그래프의 변경

하지만 이 문제에서는 정점을 감시해야 한다.

 

그러므로 그래프의 구조를 바꿈으로써 기존의 알고리즘을 이용할 수 있게 해야한다.

 

그 방법은 각 정점을 '들어오는' 정점과 '나가는' 정점으로 쪼개는 것이다.

 

 

원래 정점으로 들어오는 모든 간선은 들어오는 정점으로 들어오고,

원래 정점에서 나가는 정점으로 부터 나가도록하는 것이다.

그리고 들어오는 정점과 나가는 정점을 단방향 간선으로 연결하면

이 정점을 지나가는 모든 유량은 이 간선을 지나야한다.

따라서 이 간선에 용량을 부여함으로써 정점의 용량을 구현할 수 있다.

 

다른 간선들의 용량은 무제한으로 설정하면 이 그래프의 최소 컷은 결국 정점 내부의 간선들로만 구성될 것이고

 

결과적으로 정점 용량의 합을 최소로 하는 컷을 찾게된다.

 

 

 

 

 

 

 

4. PROJECTS 국책 사업: 최소 컷 용량 최대 유량

 

국책사업으로 필요한 장비들만 마련만 하면 예상 수익 x원 얻을 수 있다고 한다.

 

이러한 국채 사업 여러개를 잘 선택하여 최대 순이익을 얼마인지를 구하는 프로그램을 작성하여라.

(장비들은 유료로, 하나만 구입하면 여러 사업에 이용할 수 있다)

 

 

풀이

일단 이 문제 또한 자원 배분 문제랑 똑같다.

 

'돈' 이라는 자원을  '장비'에 배분한다는 것이다.

 

현재 가지고 있는 '돈'을 사업을 함으로써 얻는 예상 수익의 합 이라고 생각하여

 

장비에 흘러 보내는 것이다.

 

그렇게 흘러 보내면 '못사는 장비' 가 생길 수 도 있다.

 

이는 그 장비가 필요한 사업의 금액이 남지 않음을 의미하고, 수익이 생기지 않음을 의미한다.

 

따라서 전체 사업의 예상수입 - 최대 유량 = 최대 순이익이 된다.

 

 

 

이는 다음과 같이 증명할 수 있다.

 

S에 포함된 집합: 선택한 사업들과 거기에 필요한 장비들

T에 포함된 집합: 선택받지 못한 사업들과 S에 필요없는 장비들

 

S -> T 로가는 컷 용량은 항상 유한하다.

(무한할 경우는 필요한 장비가 T에 속해있는 경우이다.)

(s -> p , e->t 로가는 간선의 가중치의 합이므로)

 

 

컷의 용량을 C라 하자 그러면 다음과 같다

 

C = ∑P(i) + ∑E(j)  ( i∈ P-S ,  j  ∈ E∩S)

 

해당 컷의 순이익을 X라고 하자 그러면 다음과 같다

 

X =  ∑P(i) - ∑E(j)  ( i∈ S ,  j  ∈ E∩S)

 

 

위 두식을 더하면

 

X + C = ∑P(i) (i∈P)

 

X = ∑P(i) -  C  (i∈P)

 

따라서 해당 컷의 순이익은 C에 지배된다.

 

그러므로 최대 순이익은 C가 최소라는 의미이고 

 

이것은 최소 컷 문제이므로

 

포드-풀커슨 알고리즘으로 충분히 문제를 해결 할 수 있다.

 

 

 

 

- 알고리즘 문제해결전략 1002p