소셜미디어 상에서 다음과 같은 문제를 해결하기 위해 시도중이라고 가정해보자.
n개의 물건과 m 명의 소비자가 있고 그중 몇몇 소비자는 특정 제품에만 관심이 있다, 이상황에서 소비자들이 관심있어하는 최대의 물선을 찾아낸다.
그림 2.25: 증가 흐름 그래프.
그림 2.26을 보면 문제점을 도표화 시킨것을 볼수 있다.
좌측의 노드는 제품들을 의미하고 우측의 노드는 소비자들을 의미한다.
엣지는 소비자들이 관심있어하는 품목에 대한것이다.
강조되어 있는 엣지는 소비자와 물품이 서로 매칭되었음을 의미한다.
좌측의 그림은 매칭을 우측은 최대 매칭을 의미한다, 매칭의 크기를 늘리기 위한 엣지의 추가는 불가능하다.
이 문제는 bipartite 그래프를 사용하면 해결할수 있다.
bipartite 그래프에서, Vl과 Vr은 좌, 우측 노드들을 의미한다 (V전체 = Vl 합집합 Vr이다), 그리고 E는 엣지를 의미한다, 또한 매칭 M을 M <(포함관계) E로 정의하자, 따라서 각 노드 V가 M의 최대 한개의 엣지와 연결되게 한다.
다르게 설명하면, 노드는 매치되거나 매치되지 않는 상황으로 볼수있다.
bipartite 그래프에서 최대의 매치수를 Mmax(max는 아래첨자) 로 정의하자, 이때 그래프에서 M0일때도 있다 |Mmax| >= |M0| 으로 표현할수 있다.
Ford-Fulkerson 알고리즘을 이용해서 maximum bipartite 문제를 해결해보도록 하자.
이 문제는 bipartite 그래프 G(V,E)에서 (V0, E0,C) 를 생성하면 쉽게 해결 가능한데 다음의 예시를 보자:
그림 2.26 : 최대 Bipartite Matching 그래프.
그림 2.27을 보면 그래픽화에 대한 예시를볼수 있다.
이 그래프에서 최대 flow문제를 해결하기 위해서, flow가 최대가 되려면 Vl과 Vr 사이의 최대 엣지수를 사용해서, 최대의 매칭수를 얻을수 있다.
2.6.6 브릿지 탐색 (Bridge Detection)의 정의.
색션 2.5.7에서 살펴보았다,브릿지,잘린 엣지는 서로 연결된 구성요소들을 제거하는것이다.
브릿지를 탐색하는 간단한 알고리즘을 이번에 살펴보게된다.
이 알고리즘은 복잡도가 높지만, 꽤 직관적으로 사용할수 있다.
같은 작업에 대한더 효율적인 알고리즘을 사용할수 있다.
이것을 알고 있을때, 브릿지를 제거하는것은, 연결된 요소들을 제거하는것이다, 하나의 단순한 알고리즘은 엣지를 하나하나 제거하고 테스트하며 구성요소가 분리되는지 테스트 하는것을 의미한다.
이 알고리즘은 알고리즘 도표 2.7에 자세히 설명하고 있다.
엣지 e(u, v)를 삭제하는것은 BFS,DFS 알고리즘을 사용해 어떤 엣지를 삭제할지 분석할수 있다.
노드 u에서 시작해서, BFS알고리즘으로 탐색하게 된다, 라인 6에서처럼 노드 V에 아직 방문하지 않았다면, 라인 10에서 처럼 해당 엣지를 잘라내게 된다.
2.7 요약.
이 챕터에서는 그래프의 기본적 요소에 대해서 살펴보았다, 그래프를 그리는 기본 단위인 노드와 엣지, 그리고 그래프의 속성인 degree와 degree 분배(distribution) 에 대해서 살펴보았다.
모든 그래프를 표시할때 계산 가능성을 위해 자료구조를 사용해서 표시해야한다.
또한 이번 챕터에서 인접행렬, 인접 리스트, 엣지 리스트와 같은 구조적 기술역시 살펴 보았다.
소셜 네트워크의 공백의 특징으로 인해, 두개의 인접 리스트와 엣지 리스트는 인접 행렬에 배해 훨씬 사용 공간을 줄여서 저장이 가능하다(인접 행렬은 시작,끝 노드의 관계가 없으면 0으로 표시되는데 관계의 규모가 적기때문에 수많은 0으로 채워질수 있기때문에 관계가 있는 사항들만 연결한 인접 리스트와 엣지 리스트가 효과적으로 작용할수 있다).
다양한 그래프의 종류에 대해서도 살펴보았다 : null과 empty그래프, 방향/비 방향/혼합 그래프, 단순/멀티 그래프, 가중치 그래프를 살펴보았다.
signed 그래프는 모순되는 행동에 대한 가중치 그래프로 사용하기 좋다.
paths, walks, trails, tours, cycle로 설명 가능한 연결성 그래프 역시 설명했다.
구성요소(Components)와 연결된 보조 그래프.
구성요소간 강/약한 연결성에 대해서도 확인했다.
그래프의 연결을 본다면,다른 노드들간의 가장 짧은 경로를 탐색할수 있다.
또한 그래프의 직경(diameter)는 그래프상에서 가장 긴 경로를 의미한다.
특별한 그래프의 형태는 노드간의 경로와 degree 분배를 기반으로 제작되어 있다.
완전한 그래프는, 모든 노드가 연결되어 있으며, 그래프의 형태이고, 노드의 degree가 모두 같은경우를 의미한다.
트리는 그래프의 종류이지만 cycle이 없는 형태를 의미한다.
여기서 2개의 특별한 트리를 살펴 보았는데 spanning tree 와 Steiner tree 이다.
Bipartite 그래프는 노드를 두개의 셋으로 나눌수 있으며, 이 두개의 셋 사이에는 엣지가 존재할수 없다.
그룹 소속 네트워크는 bipartite 그래프의 한가지 예이다.
브릿지는 단일 포인트 엣지로서 이전 연결된 상태를 끊어내는 기능을 가진다.
그래프 알고리즘에서, 다양한 기술을 살펴보았는데
알고리즘 탐색은 그래프상의 노드에 순서를 부여하는것과 같다.
이런 알고리즘은 노드간의 연결성을 확인하는데 특히 효과적으로 사용할수 있다.
최단거리 알고리즘은 각 노드간의 최소거리를 찾는방법이며, 다익스트라 알고리즘을 살펴보았다.
스패닝 트리 알고리즘은 서브그래프의 제작에 사용할수 있는데 , 이는 모든 노드에 걸쳐 최소값까지 합한 엣지를 선택해서 제작한다, Prim 알고리즘을 대상으로 살펴보았다.
Ford-Fulkerson 알고리즘은, 최대 flow알고리즘으로써 살펴보았다.
이건 그래프 상에서 최대 가중치의 용량을 찾아내게 도와준다.
Maximum bipartite는 bipartite matching 문제를 해결하기 위해 maximum flow 원리를 적용한것이다.
마지막으로, 브릿지 탐색에 대한 간단한 솔루션까지 살펴보며 장을 마무리 지었다.
댓글 없음:
댓글 쓰기