비방향성에서의 spanning tree는 원본 그래프에서의 모든 노드와 하위 엣지를 모두 포함한다.
Spanning trees 는 다양한 실생활 응용프로그램에서 사용되고 있다.
케이블 회사에서 케이블을 가설하기를 원하는데 모든 지역(노드)를 커버하면서 비용역시 최소로 이용해서 이 작업을 완료하고 싶어한다(케이블이 엣지가 된다).
소셜 미디어 마이닝에서는, 사용자 개인에게 정보를 제공하는 구간을 예로 들수있다.
정보는 친구를 통해 퍼지게 되는데, 이때 비용의 산출은 두 노드(친구) 사이의 관계를 통해 산출된다.
네트워크 상에서 minimum spanning tree는 모든 유저에게 정보를 전달하는 최소의 비용을 산정하는데 도움을 준다.
minimum spanning trees 에는 다양한 알고리즘이 존재한다.
가중치 그래프에서 MST산출중 가장 유명한 알고리즘으로 Prim을 들수 있는데 이는 233페이지에서 확인할수 있다.
관심있는 독자는 다음 레퍼런스들은 참고하면 더 좋다.
Prim 알고리즘의 정의.
Prim’s 알고리즘은 도표 Algorithm 2.5 에서 볼수있다.
시작은 아무 노드를 선택해서 시작하고 spanning tree에 하나씩 추가하는 방식으로 진행된다.
진행되는 방식은 트리에 엔드포인트가 있고 아직 선택되지 않은 노드중에서 엔드포인트가 하나 있는 가장 자리를 선택해서 트리를 성장시키게 된다.
진행이 가능한 엣지들 가운데, 종단점을 포함해 최소의 가중치를 가진것이 다음 진행 노드로 선택된다.
이 단계는 그래프가 모두 확장될때까지 계속 진행된다.
그림 2.21을 살펴보면 Prim 알고리즘의 진행방향을 확인할수 있다.
그림2.21: Prim 알고리즘 수행의 예시.
2.6.4 네트워크 Flow 알고리즘 정의.
무한 급수원을 싱크대에 연결하는 수도 파이프 라인을 생각해보자.
이 네트워크 상에서, 파이프의 용향이 있다면 매우 흥미로운 질문이 될수있다, 얼마나 많은 양의 물을 싱크대로 보낼수 있을까?, 바로 여기서 네트워크 플로우 알고리즘이 등장하게 된다.
이런 종류의 질문은 많은 분야에서 언제나 발생한다.
언뜻 살펴보면, 이런 문제는 네트워크 플로우 알고리즘과 연관성이 없어보인다,하지만 상당히 높은 연관성을 가진다.
예를들면, 사용자들의 하루 전송 메시지 사용량 제한이 있는 소셜 미디어 매체가 있을때(여기서 이걸 허용량이라고 생각하자),이를 대비하기 위해 얼마나 많은 메시지 량을 준비해야 대비할수 있을까?.
세부사항을 탐구하기 이전에, flow 네트워크를 정의해보자.
플로우 네트워크.
플로우 네트워크 G(V,E,C)^2는 방향성 가중치 그래프이다,이때 다음과 같은 상황을 따른다고 하자.
엣지의 캐파를 의미한다.
수식2의 역은 성립하지 않는다.S는 소스노드, T는 sink 노드를 의미한다.
소스에서 무한한 양이 공급된다.
샘플 플로우 네트워크에서, 가능한 허용량의 크기를 그림 2.22에서 보여주고 있다.
흐름Flow.
엣지에 특정 허용량이 정해져 있을때, 허용량의 최대치까지 채울수 있다.
이걸 보통 허용량 제한조건 (capacity constraint)라고 한다.
더 나아가서,flow가 소스 s와 sink t 를 지나는 동안 flow가 없어지지 않는한 flow 의 양은 동일함을 보장해야한다.
수식으로 표현하면
해당 식은 엣지를 통과하는 flow를 의미한다
허용량 제한조건.
flow 보존량 제한조건일반적으로, 용량 c와 흐름 f로 엣지를 시각화 하기위해 표기법 f=c를 사용한다.
그림 2.23에서 예시로 flow와 허용량에 대한 예시를 보여주고 있다.
흐름의 량(flow의 값)은 어떤 네트워크에서든 나가는 양은 인입되는 양에서 차감된다.
그 대신에, sink에서 나가는 흐름은 들어오는 값에서 빼서 이 값을 산출할수 있다.
연습문제 2.4. 그림 2.23을 대상으로한 flow 양 계산 연습, 19가 나온다.
이 상황에서 목적은 엣지에서 허용가능한 최대의 흐름양을 구하는것이다.
이건 최대 흐름 알고리즘을 통해 찾을수 있다.
90페이지에 있는 Ford-Fulkerson를 대표적으로 잘 정립되어 있는 알고리즘이라고 할수있다.
Ford-Fulkerson 알고리즘.
이 알고리즘의 이면에는 다음과 같은 내용이 내포되어 있다: 소스에서 sink까지 가는 엣지에서 사용되지 않은 캐파가 있는 경로를 찾는것이다.
(사용하지않는 옹량을 다른곳으로 조절하는 과정을 통해) 사용 용량을 증가시킬수 있다.
그리고 이 과정을 가능한한 최대로 반복하게 된다.
일반화 시키기 전에,몇가지 컨셉에 대해 정의내릴 필요가 있다.
주어진 네트워크 G(V,E,C)에서 ,다른 네트워크 Gr(V,ER,CR)을 정의할수 있는데, 이건 나머지 네트워크로 정의한다.
이 네트워크는 원본 네트워크에서 얼마나 용량이 남아있는지 알려주는 네트워크이다.
노드 u 와 v 사이의 나머지 네트워크는 (u,v) 와 (v,u)가 원본 그래프에서 존재할때만 엣지를 u와 v사이에 엣지를 가진다.
원본 네트워크에 2가지가 존재할때,나머지 네트워크에 2개의 엣지를 가지고 있는데: 하나는
(u,v) 이고 나머지는 (v,u) 이다.
intuition 이란 원본 네트워크에서 엣지를 지나가는 flow가 없을때를 의미한다,엣지의 용량이 남아 있는한 흐를수 있다.
그러나, 나머지 네트워크에서, 반대방향으로도 flow를 보냄으로서 어느정도의 flow를 상쇠시켜 취소할수도 있다.
그림 2.24를 살펴보면 (u,v)사이의 엣지에 남아있는 용량과 해당 결과를 볼수 있다.
나머지 네트워크 상에서, 남은 용량이 없는 엣지는 표현되지 않았다.
증강(Augmention)과 증강하는 경로(path)
잔존 그래프상에서, 엣지가 원본 그래프와 같은 방향성을 가질때, 당연히 용량은 원본 그래프와 같은 방향으로 얼마나 흐를수 있는지 보여준다.
엣지가 반대방향일때, 원본 그래프의 엣지보다 얼마나 반대로 보낼수 있는지 보여준다.
그래서, 잔존량을 찾아낸다면, 원본 그래프보다 flow의 양을 증진시킬수 있다.
s에서 t로가는 간단힌 내용의 잔존량 그래프는 증가 경로를 의미한다.
모든 잔존량 그래프에서 용량이 양수라면, 이 path는 용량을 더 증진 시킬수 있다고 판단할수 있다.
엣지에 해당하는 용량 제한이 있기때문에 해당 경로를 통한 flow의 총 량은 경로를 따라 지나간 최소 용량과 같다.
원본 경로 f(u,v)와 잔존량 그래프에서 Fr(u,v) Fr(v,u)를 통해,flow의 양을 증진시킬수 있다.
예시 2.5.
그림 2.24의 아래 그래프에서 s,v1,v3,v4,v2,t의 경로를 살펴보자.
최소용량이 1인 경로가 있는데, 당연히 이 경로의 flow양은 1이다.
이 경로에 해당하는 용량을 늘리는 방안을 고민해 보자.
그림 2.25를 보면 flow그래프와 잔존량 그래프를 확인할수 있다.
새로운 잔존량에서, 증가시킬수 있는 path가 더이상 없음을 알수있다.
Ford-Fulkerson을 이용하면 네트워크에서 가장 많은 flow를 사용하는 path를 사용할수 있지만, 여기서 해당 이론의 증명은 하지 않기로 한다.
흥미있는 독자들은 찾아보는것도 좋은 방안이 될것이다.
해당 알고리즘은 알고리즘 도표 2.6에 설명되어 있다.
알고리즘은 증가경로를 탐색하는데, 증가가 가능한 경로가 탐색되면 해당 경로의 flow양을 늘리게 된다.
탐색 방법은 그래프 탐색 알고리즘을 이용하는데 위에서 학습한 BFS등이 그 예가 될수 있다.
댓글 없음:
댓글 쓰기