2024-06-11-22. Graphs

그래프의 사용

자동차 네비게이션
그래프형 데이터베이스
웹 크롤링에서 페이지 탐색
외부 요청에 따른 서버 상태 변화 표현

그래프의 정의

그래프 G는 정점(노드)의 집합 V와 간선의 집합 E로 구성된다.

G = (V, E)

정점 집합 V의 원소들의 구성에 대해서는, V가 공집합이면 안된다는 것을 제외하면 제한이 없다.

간선 집합 E의 정의는 그래프의 종류가 simple graph인지 아니면 digraphs 인지에 따라 다르다.

Simple Graph (Undirected Graph)

E가 V의 원소로부터 만들어지는 무순서쌍(원소 개수가 2개인 집합) 으로 구성된다.
ex) V = {1, 2, 3, 4, 5, 6}, E = { {1, 2}, {1, 5}, {2, 5}, {3, 6} }

Digraph (Directed Graph)

E가 V의 원소로부터 만들어지는 순서쌍으로 구성된다.
E가 V에 대한 이항 관계(relation)라고도 할 수 있다.
ex) V = {1, 2, 3, 4, 5, 6}, E = {(1, 2), (2, 2), (2, 4), (2, 5), (4, 1), (4, 5), (5, 4), (6, 3)}

Simple Graph를 Digraph로 변환하여 표현하는 것이 가능하다.

Simple graph의 임의의 간선 {a, b}를 Digraph의 두 간선 (a, b)와 (b, a)로 나타내면 된다.

따라서 Digraph에서 적용 가능한 알고리즘은 Simple graph에도 적용 가능하다.

Graph의 최대 간선 개수와 Complete Graph

노드가 n개인 Simple graph와 Digraph는 각각 최대 몇 개의 간선을 가질 수 있고, 가능한 만들어질 수 있는 그래프가 몇 개 존재할까?

Simple Graph의 경우 간선은 V에서 원소 두 개를 선택한 것이므로, 간선은 최대 _nC_2, 즉 n(n-1)/2 개 존재 가능하다.

각각의 존재 가능한 간선이 실제로 존재하거나 존재하지 않거나 둘 중 하나이므로, 만들어질 수 있는 그래프의 개수는 2^{n(n-1)/2} 개이다.

Digraph에서는 간선 순서쌍에 왼쪽에 올 수 있는 V의 원소 개수가 n개, 오른쪽에 올 수 있는 V의 원소 개수도 n개이다. 따라서 간선은 총 n^2개 존재 가능하다.

Simple Graph에서 구했던 것과 마찬가지로, 각각의 간선이 실제로 존재하거나 존재하지 않거나 둘 중 하나이므로, 만들어질 수 있는 그래프의 개수는 2^{n^2}개이다.

정점에 대해 존재할 수 있는 모든 간선들이 존재하는 그래프를 Complete Graph라고 한다.

정점이 n개인 complete graph는 K_n이라 표기한다.

K₄를 그리면 다음과 같다.

Incident와 Adjacent

incident와 adjacent는 둘 다 ‘인접’으로 번역되기도 한다. 하지만 그 둘의 뜻은 다르다.

incident는 정점과 간선의 관계를 나타내는 데 쓰이며, adjacent는 정점 간의 관계를 나타내는 데 쓰인다.

Digraph의 정점 u, v와 간선 e = (u, v) 에 대해, e 는 u로부터 떠난다(e is incident from u)라고 하고, 또한 e는 v로 들어간다(e is incident to v) 라고 한다.

Simple Graph에서는, 간선 e = {u, v} 는 정점 u와 v에서 부속한다(e is indident on u, v) 라고 한다.

Digraph에 간선 (u, v)가 존재할 때, 정점 v가 정점 u에 인접한다(v is adjacent to u)고 한다.

v를 u의 인접 정점이라고도 한다.

간선 (u, v)가 존재하더라도 (v, u)가 존재하지 않는다면, 정점 u가 v에 인접하다고 할 수는 없다.

반면 Simple Graph에서 간선 {u, v}가 존재한다면, v가 u에 인접함과 동시에 v가 u에 인접한다.

Degree

simple graph에서, 정점의 Degree는 해당 정점에 부속하는(incident on) 간선의 개수이다.

앞에서 정의한 simple graph에서는 self loop 간선(양 끝이 같은 정점에 붙은 간선)이 존재할 수 없다. 하지만 self loop를 허용하는, 즉 원소가 정점 두개가 아닌 한개뿐인 집합도 간선으로 허용하는 simple graph의 정의도 존재한다.

이 경우, self loop 간선은 Degree를 2 증가시킨다.

간선 하나가 그래프의 degree 총합을 2 증가시키므로, 다음 식이 성립한다.

2*|E| = sum(deg(v_i))

따라서 그래프의 degree의 총합은 짝수이며, degree가 홀수인 정점은 짝수 개 존재한다.

digraphs 정점의 degree는 정점으로 들어가는(incident to) 간선의 개수인 in-degree와, 정점에서 떠나는(incident from) 간선의 개수인 out-degree로 나뉜다.

Path(경로)와 사이클

그래프의 정점으로 구성된 순열 <v_0, v_1, v_2, ..., v_n> 에 대해, 간선 (v_{i-1}, v_i) (i = 1, 2, ..., n) 가 E의 원소인 경우, 해당 순열을 “v_0로부터 v_n까지를 연결하는 길이 n인 경로(path)”라고 한다.

특히, 경로 내에 중복된 간선이 없는 경우 simple path라고 한다.

digraph에서 v_0 = v_n 이고 경로에 간선이 최소 하나가 존재한다면, 해당 경로를 사이클(cycle)이라 한다.

simple graph에서는 v_0=v_n이고 0<n 인 경우, 해당 경로를 사이클이라 한다.

트리

모든 정점의 쌍이 경로로 연결된 simple graph를 연결 그래프(Connected Graph)라고 한다.

특히, 사이클이 존재하지 않는 연결 그래프를 트리라고 한다.

트리의 정점 중 하나를 루트로 지정하면, 그 트리를 루트 있는 트리라고 한다.

루트가 정해짐으로써 트리의 정점 간에 부모와 자식, 조상과 자손 관계가 성립하며, 루트로부터의 경로 길이를 통해 정점의 깊이가 정해진다.

Multigraph

multigraph는 한 정점 쌍에 대해 간선이 두 개 이상 존재할 수 있는 그래프이다.

multigraph에서는 간선 이름에 대해 정점의 무순서쌍을 대응시키는 함수로 간선을 정의한다.

e1 → {1, 2}, e2 → {1, 2}, e3 → {2, 3}, ...

multigraphs에서 self loop 를 허용한 것을 Pseudograph라고 한다.

Bipartite Graph

simple graph의 정접 집합 V 를 다음 조건을 만족하도록 두 집합 V1, V2 로 나누는 것이 가능할 경우, 이를 Bipartite Graph라고 한다.

조건 : V1, V2 각각의 집합 내부에서 서로 인접한 정점의 쌍이 존재하지 않는다.

만약 bipartite graph에서 V1의 각 정점이 V2의 모든 정점과 인접하다면, 이를 complete bipartite graph라 한다.

|V1| = m, |V2| = n 인 complete bipartite graph를 K_{m, n}으로 표기한다.

K_{2, 4}를 그리면 다음과 같다.

Bipartite Graph check

어떤 simple graph가 Bipartite인지 확인하는 알고리즘은 다음과 같다.

비어있는 두 정점 집합 V1과 V2를 준비한다.
그래프 내의 어떤 정점 u를 V1에 넣는다.
u와 인접한 노드들은 모두 u와 다른 집합에 있어야 한다. 따라서 u의 인접 노드들을 모두 V2에 넣는다.
임의의 정점 v를 집합에 넣기 전, 해당 집합 내에 v의 인접 정점이 있는지 확인한다. 인접 정점이 있다면 그래프는 bipartite가 아니다.
정점 v를 집합 V’(V’은 V1 또는 V2)에 넣었다면, v의 인접 노드들 중 아직 V1이나 V2에 들어가지 않은 것들을 모두 V’의 반대편 집합에 넣는다.
4, 5를 반복하여, 모든 정점이 V1이나 V2에 들어갔다면 그래프는 Bipartite이다.

Planar graph (평면 그래프)

그래프를 평면에 그렸을 때, 어떤 간선도 서로 교차하지 않도록 그릴 수 있는 방법이 있다면, 해당 그래프를 평면 그래프라 한다.

예를 들어, complete graph K₄는 아래와 같이 평면에 간선이 교차하지 않도록 그릴 수 있으므로, 평면 그래프이다.

complete graph K₅와 bipartite graph K_3,3은 평면 그래프가 아님이 알려져 있다.

쿠라토프스키와 와그너 정리에 따르면, 어떤 그래프가 평면 그래프가 아닐 필요충분조건은, 해당 그래프의 subgraph로 K₅또는 K_3,3이 존재하는 것이다.

Subgraph (부분 그래프)

그래프 G의 일부분이 그 자체로 그래프가 된다면, 이를 G의 subgraph라 한다.

구체적인 정의는 다음과 같다.

그래프 G = (V, E) 에 대해
V’ 이 V의 부분 집합, E’이 E의 부분 집합이고
G’ = (V’, E’)이 그 자체로 그래프인 경우

즉 E’의 간선들이 V’내의 정점 쌍으로 구성된 경우

G’을 G의 subgraph라 한다.

Adjacency Matrix (인접 행렬)

그래프는 인접 행렬을 통해 컴퓨터에서 표현할 수 있다.

그래프 G를 나타내는 인접 행렬 A는 다음과 같이 정의된다.

그래프의 각 정점에 1, 2, ..., |V| 까지의 고유한 번호가 매겨져 있다고 가정한다.
행렬 크기는 |V| x |V| 이다.
i행 j열 원소는 E에 간선 (i, j)가 존재한다면 1이고, 존재하지 않는다면 0이다.

다음 그림은 인접 행렬을 통해 digraph를 나타낸 예시이다.

Graph Isomorphism

서로 모양이 같은 그래프를 isomorphic 이라 한다.

구체적으로, 두 pseudograph G1 = (V1, E1), G2 = (V2, E2) 에 대해

|V1| = |V2|

이고,

f: V1 → V2
f 는 일대일 대응 함수
V1의 임의의 노드 u, v에 대해, u와 v 사이의 간선 개수가 f(u)와 f(v)사이의 간선 개수와 같다.

위 조건들을 만족하는 함수 f가 존재할 수 있다면, G1이 G2에 isomorphic하다고 한다.

또한 함수 f를 isomorphism이라 한다.

두 그래프가 Isomorphic이라면 다음이 성립한다.

정점 개수가 서로 같고, 간선 개수가 서로 같다.
대응하는 정점의 degree가 같다.
존재하는 subgraph가 서로 같다.
G1의 임의의 정점 a, b 간의 경로들의 길이가 G2의 정점 f(a), f(b)간의 경로들의 길이와 같다.

이러한 특성이 두 그래프가 isomorphic임을 보장하진 않지만, 이 특성 중 만족하지 않는 게 하나라도 있다면 두 그래프가 isomorphic이 아님이 보장된다.

Graph Connectivity

그래프의 정점 u에서 v를 연결하는 경로가 존재한다면, u와 v가 Connected(연결) 되었다고 한다.

경로의 길이가 0인 경우, 즉 u = v인 경우도 connected라 한다.

모든 정점의 쌍에 대해 경로가 존재하는 그래프를 connected graph라 한다.

Connected Component

simple graph G = (V, E)에 대해, 다음 조건을 만족하는 V의 부분 집합 V’을 G의 Connected Component라 한다.

V’의 모든 정점들은 서로 연결되어 있다.
V’의 각 정점에 대해, 해당 정점과 연결되어 있는 모든 정점은 V’에 포함되어야 한다. (즉, V’이 크기가 최대여야 한다. maximal)

위 그래프에는 세 개의 Connected Component가 존재한다.

N-Connectivity, Cut Vertex

연결 그래프가 얼마나 잘 연결되어 있는지 나타내는 척도이다.

연결 그래프가 끊어지도록 하기 위해 최소 n개의 정점을 제거해야 한다면, 해당 그래프가 n-connected라 한다.

어떤 정점 하나만 제외시켜도 연결 그래프가 끊어진다면, 그래프는 1-connected이고, 그래프를 끊어지게 하는 정점을 cut vertex라 한다.

cut vertex를 찾는 알고리즘이 존재하는데, 이 알고리즘을 이용해 그래프를 끊어지게 하는 간선, cut edge를 찾을 수 있다. 모든 간선 사이에 정점을 추가하고, 추가된 정점 중 cut vertex를 찾으면 된다. cut vertex가 추가된 간선이 cut edge이다.

Connectivity in Directed Graph

digraph에서는 정점 간의 연결 상태가 여러 종류이다.

digraph의 두 정점 a, b는

weakly connected : digraph의 각 간선의 방향을 무시하고 simple graph로 간주했을 때, a와 b가 연결되어 있는 경우
semi connected : a에서 b로의 경로가 존재하거나, b에서 a로의 경로가 존재하는 경우
strongly connected : a에서 b로의 경로도 존재하고, b에서 a로의 경로도 존재하는 경우

또한 방향 그래프 G = (V, E)에 대해, 다음 조건을 만족하는 V의 부분 집합 V’을 G의 Strongly Connected Component라 한다.

V’의 모든 정점들은 서로 강하게 연결되어 있다.
V’의 각 정점에 대해, 해당 정점과 강하게 연결되어 있는 모든 정점은 V’에 포함되어야 한다.

정점 a와 b가 강하게 연결되어 있다는 것, 즉 a에서 b로의 경로가 존재하고 b에서 a로의 경로도 존재한다는 것은, a와 b가 사이클 안에 있다는 뜻이다.

또한 사이클 안의 임의의 두 정점은 강하게 연결되어 있다.

따라서 Strongly Connected Component를 찾기 위해서는 먼저 사이클을 찾아야 한다. 서로 붙어 있는 사이클들의 최대 크기(maximal) 집합이 하나의 Strongly Connected Component이다.

← Previous Post Next Post →

목록으로