지금까지는 일반적인 컨셉의 그래플를 살펴보았다면, 이제는 다양한 현태의 특별한 그래프를 살펴보도록 하자.
이 특별한 그래프는 다른 문제를 해결하는데 사용할수 있기때문에.
이번장에서는 잘 알려진 몇가지의 특별한 그래프를 살펴볼것이다.
2.5.1 트리와 숲 그래프(Trees and Forests).
트리는 특별한 형태의 비 방향성 그래프이다.
트리의 그래프의 구조는 cycle이 없다는것이 특징중 하나이다.
트리에서, 특정 path는 모든 노드를 통과하게 된다.
숲(forest) 그래프는 여러개의 트리(tree) 그래프를 묶어서 부르는 명칭이다.
그림 2.11에서 숲 그래프의 예시를 볼수있다.
그림 2.11: 3개의 tree그래프로 이루어진 숲그래프.
그림 2.12: Minimum Spanning Tree 그래프(번역하면 더 이상함).
각 노드는 도시를 의미라혹 엣지의 숫자 가중치는 각 도시간의 거리를 의미한다.
하이라이트된 엣지는 전체 길이를 최소화 하는 방안을 표시한것.
트리상의 V개의 노드가 있다면, 엣지의 수는 |E| = |V| -1로 표시할수 있다.
이건 모순된 상황을 만들수 있는데 해당 상황은 연습문제(Exercises)에서 설명한다.
2.5.2 특별한 subgraph.
속성에 따라 몇개의 subgraph가 자주 사용된다.
여기서는 2개의 subgraph를 살펴보도록 하자.
Spanning Tree 그래프.
어떤 연결된 그래프에서든, Spanning Tree 그래프는 그래프 상에서 모든 노드를 포함하는 보조 그래프이다.
당연하게도, 원본 그래프가 트리가 아닐경우, spanning tree 에서는 모든 노드는 포함하지만, 엣지는 포함하지 않는다.
한개의 그래프에는 여러개의 spanning tree가 존재할수 있다.
가중치 그래프와 해당하는 spanning tree에서, spanning tree의 가중치는 트리의 모든 엣지의 가중치 합과 같다.
가중치 그래프에서 여러개의 spanning tree 그래프가 있을때, 그중 가장 최소 비용의 spanning trees를 가리켜 minimum spanning tree (MST) 라고 부른다.
그림 2.13 : V' = {v2,v4,v7}에서의 Steiner tree(슈타이너 트리라는 명사임).
예를들면, 도시의 set이 있다고 가정해볼때, 도로를 건설해 도시들을 연결해야 한다고 하자.
이때 도시 사이의 거리를 알고 있는 상황이라고 가정하면.
각 도시를노드로, 거리를 엣지로 지정해 노드 사이에 명시하며 보기쉽게 만들수 있다.
그림 2.12를 보면 그래프 기반 도표를 보여준다.
이 그래프에서, 노드 v1,v2...v9까지는 도시를 의미하며, 엣지에 적혀있는 숫자는 도시 사이간 거리를 의미한다.
엣지는 차후 잠재적 도로가 될때 사용할수있는 거리다, 즉 아직 도로는 건설되지 않은 상황이다.
건설비용을 산정할때, 정부측에서는 마일당 최소한의 비용을 들여서 건설하려 할것이고, 당연히 도시간은 연결이 되어야 한다.
최소비용 spanning tree 는 이 문제를 해결하는 좋은 방안이 될수 있다.
MST에서 엣지가 모든 도시를 연결하고 비용은 최소로 할수 있는 가능성을 제시하기 때문이다.
그림 2.2의 굵게 표시된 상황이 최소비용 spanning tree이다.
Steiner Tree 슈타이너 트리.
슈타이너 트리는 MST 와 비슷한 상황에서 사용할수 있다.
그래프의 가중치 G(V,E,W)와 노드의 서브셋이 주어지는 상황에서, 슈타이너 트리가 주목하는 부분은 모든 노드를 확장시키며 트리의 가중치를 최소화 시키는것에 그 목적을 두는 트리이다.
MST와 슈타이너 트리는 다른 트리이다, 왜냐면 MST는 노드 일부만을 대상으로 하지만 슈타이너 트리는 노드를 확장해서 적용하기 때문이다.
그림 2.13에서 슈타이너 트리의 예시를 볼수 있다.
이 예시에서 v'는 {v2,v4,v7}을 대상으로 한다.
그림2.14 : Ki 가 1에서 4까지의 완성형 그래프.
그림 2.15: Planar 와 Nonplanar그래프, 좌측이 planar 우측이 nonplanar 그래프이다.
2.5.3 완성형(Complete)그래프.
완성형 그래프는 전체 노드 SET V에 대한 그래프이다, 그래프에서 모든 가능한 엣지가 존재할때 구성된다.
다른의미로는, 모든 노드의 쌍은 엣지로 연결되어 있다는것이다.
그러므로 완성형 그래프는 Kn ( K1,2,3,4.. )으로 표기되며 그림 2.14에서 볼수 있다.
2.5.4 Planar 그래프 정의.
Planner 그래프를 정의하면 종착지를 제외하고 엣지가 겹쳐지지 않는 상황을 의미한다.
당연히 planar가 아닌 그래프는 nonplanar라고 할수 있다.
그림 2.15에서는 planar와 nonplanar 그래프의 예시를 보여주고 있다.
그림 2.16 : Bipartite 그래프(좌) 와 Affiliation 네트워크(우).
2.5.5 Bipartite 그래프의 정의.
그래프 G(V,E)를 보면 두개의 set으로 구분할수 있다, 모든 엣지에 대해서, 종착지점(endpoint)를 기준으로 두개의 set으로 나누어진다.
다른의미로, 두개의 셋으로 엣지는 연결된다, 하지만 같은 set상에서는 엣지가 없다.
이 그림에서, VL = {v1, v2}을 ,VR = {v3, v4, v5}를 의미한다.
소셜미디어에서, affiliation네트워크는 bipartite 그래프의 대표적인 예이다.
이 네트워크 상에서, 노드(VL VR) 부분은 개개인을 나타내며, 노드의 다른 부분은 그룹 부분을 의미한다.
각 개개인이 그룹과 연관되어 있다면, 엣지는 해당 노드를 연결한다.
그림 2.16의 b를 살펴보면 연관되어있는 네트워크에 대한 예시를 볼 수 있다(kyle은 독서클럽과 푸드뱅크 봉사단체 모두에서 활동하고 있다).
2.5.6 규칙적(Regular)의 그래프의 정의.
regular 그래프란 모든 노드가 같은 degree를 지니는 그래프를 의미한다.
regular 그래프에서 모든 노드가 2의 degree를 지닐때는 2-regular 그래프라고 부븐다.
일반화 시키면, 그래프의 모든 노드가 k degree를 지닐때 k-regular 그래프라고 한다.
그림 2.17: k가 3을 가지는 Regular 그래프의 예시
regular 그래프는 연결되거나 연결되지 않을수 있다.
regular 그래프 상에서 Complete 그래프의 예시를 보면, 모든 노드 n은 n-1의 degree를 가질때 Complete 그래프라고 할수 있다,즉 k = n-1이 성립 된다.
Cycles 상황은 regular 그래프라고 볼수 있는데 이때 k=2를 지닌다.
다른 예로 k=3인 상황을 그림 2.17에서 볼수 있다.
2.5.7 브릿지(Bridges)의 정의.
그래프가 몇개의 구성요소와 견결되어 있다고 가정해보자.
이때 브릿지(Bridges)의 정의는 그래프상의 엣지가 제거되서 연결된 구성요소 (component)가 증가하는 상황을 말할수 있다.
이름에서 알수 있듯이, 이 엣지는 두개의 구성요소를 이어주는 다리가 되기 때문이다.
엣지를 제거하면서 연결되어 있던 컴포넌트가 연결이 끊어지고 component의 전체의 수가 증가하게 된다.
그림 2.18을 보면 그래프와 브릿지를 볼수있다.
댓글 없음:
댓글 쓰기