그래프

개요

Vertex 와 Edge 로 이루어진 자료구조이다. $G(V,E)$ 같은 식으로 쓰기도 하고, Vertex 와 Edge 사이즈를 $n,m$ 으로 부르는 편이다.

• Direction Edge 는 방향성을 가질 수도 있고 아닐 수도 있다. 방향성이 없는 edge 는 arc 라고도 한다.

• Weight Edge, Vortex 는 단순한 연결 정보 외에도 추가로 정보를 가질 수 있다. (길찾기 알고리즘을 보면 자주 나온다.)

• Parallel edge 같은 vortex 를 잇는 edge 가 여러개일 수 있다. 도메인에 따라 다르지만, 여러개인 쪽이 더 일반적이라 생각해도 된다.

표현 방법 및 중요 개념

배열을 이용한 방법(Adjacency array)과 매트릭스를 이용한 방법(Adjacency matrix)이 있다. 배열을 사용하면 $O(n+m)$ 의 저장공간을 사용하게 되고, 매트릭스를 사용하면 $O(n^2)$ 을 사용한다. 매트릭스를 쓰면 Vortex 로 Edge 를 찾는게 쉽고, 배열을 쓰면 Edge 로 Vortex 를 찾는게 쉬워보인다.

Min Cut

정점들을 두 그룹으로 나눌 때, 두 그룹을 잇는 엣지 수가 가장 작도록 나누는 방법이다.

응용으론 네트워크에서 핫스팟을 찾거나, 그래프 내부에서 다시 그룹을 분류하는 데 사용한다.

Min cut 을 구하는 데엔 랜덤 알고리즘과 확정 알고리즘이 있다.

그래프 탐색

그래프는 구체적인 구조가 아니라 추상적인 상태를 가르킬수도 있음.

이미 탐색한 정점은 다시 탐색할 필요가 없다. (directed tree 에선 쉽게 만족. 아닌 경우엔 메모를 해 둬야 한다.)

다음 노드를 정하는 데 있어서, 너비우선탐색과 깊이우선탐색이 있다.

• 너비우선탐색
  • 층위별로 먼저 탐색.
  • 큐 자료구조 사용
  • 최단경로 탐색
  • 방향성 없는 그래프 (undirected)
• 깊이우선탐색
  • 필요한 경우에만 백트랙
  • 방향성 있는 그래프
  • 스택사용. 재귀를 사용하는 경우 call stack 을 자연스레 사용하게 된다.

Strong Coupled Components

두 노드 u, v 에 대해 u → v 로 가는 경로와 v → u 로 가는 경로가 모두 있을 때.

두 노드는 하나의 그룹으로 압축해서 생각할 수 있게 된다. Kosaraju’s Two-Pass Algorithm

Minimum Spanning Tree

Connected graph 에서, 모든 노드들을 거치면서, 합계 코스트가 가장 작은 트리를 생각할 수 있다.

Clustering 에 응용됨. (n 개의 요소들을 grouping 하는 것을 의미)

k 개의 클러스터를 찾는 문제는, 먼저 MST 를 구하고 가장 비싼 k-1 개의 엣지를 없애는 것과 동일하다. (왜 그런지는 조금 생각해보면 자명하다.)

Union find (by rank, path compression)

Kruskal 알고리즘에서 사이클 체크를 위해 사용하는 자료구조.

모든 노드들이 각자 하나의 소스 노드를 가르키게 되고, connect 되지 않은 component 들은 서로 다른 소스 노드를 가르킨다.

소스 노드 자체가 하나의 set 을 의미하기 때문에, 가르키고 있는 소스 노드를 조회하면 두 노드가 같은 셋에 들어있는지 체크할 수 있다.

두 노드를 이을 때 두 노드가 모두 같은 소스 노드를 가르킨다면 이미 하나의 set 내부에 있으므로 사이클을 형성하게 된다는걸 constant time 에 알 수 있다.

Set 자체를 (정확힌 pointing node 를) 값으로 하는 해시 테이블이라 생각해도 좋다.

두 셋트가 머지될 때, 한쪽 셋의 pointing node 를 전부 교체하는 대신 적은 깊이 (낮은 rank) 의 셋의 pointing node 가 큰 쪽의 pointing node 를 가르키게 할 수 있다. 이런 방식이면 셋을 판별하기 위해 한번 이상의 참조가 필요할 수 있지만, 여전히 빠르다. (참조 횟수는 rank 를 따라가는데, 알고리즘을 잘 짜면 rank 의 최댓값은 매우 느리게 증가하기 때문.)

Hopcroft-Ullman 의 정리 : Union by rank with path compression $m$ times takes $O(m{\log }^{\ast }n)$ time. ${\log }_2^{\ast }n$ is inverse of tower function, $T_2(n)=2^{2^{\mathrm{2...}}}$ (there are $n$ nested powers)

Clustering

그래프가 주어졌을 때, 정점들을 $k$ 개의 그룹으로 나누는 방법.

모든 엣지가 주어졌을 때

• MST 를 구한다.
• $k-1$ 개의 가장 비싼 엣지를 끊는다.
• 남아있는 component 들이 클러스터들이며, 마지막으로 끊은 엣지가 maximum spacing 이 된다.

모든 엣지를 구하기 힘들 때

• Eucleadian graph, Hamming graph 같은 경우는 모든 엣지를 구할 필요가 없고, 그러기도 힘들다.
• Hamming graph 같이 거리가 quantize 된 경우는 짧은 거리부터 필요한 만큼 비싼 거리까지만 HashMap 과 UnionFind 를 사용해 그래프를 구성하면서 풀면 된다.
  • 이런 상황에선 maximum spacing 이 문제의 조건이어야 하고, $k$ 값이 답이 되어야 한다.
• Eucleadian graph 같은 경우도 정렬과 threshold 를 이용해 엣지수를 줄여 계산하면 된당.

그래프의 지름과 반지름

• 지름 : 두 정점을 잇는 가장 짧은 path 들 중 가장 긴 것.
  • 원 안의 점에 대해서도 똑같이 정의할 수 있다!
• 반지름 : 한 정점에 대해 가장 짧은 path 들 중 가장 긴 것을 정의할 수 있다. 이 값을 최소화 하는 정점을 찾을 수 있고, 그 때의 값.
  • 마찬가지로 그냥 원에 대해서도 반지름을 정의하는 데 사용 가능하다.

그래프에선 $d\ge r\ge d/2$ 이다.

몇가지 유용한 성질들

• Cut 을 횡단하는 엣지 중 가장 값싼 엣지는 Minimum spaning tree 의 부분이다.