Graph(그래프) 기본 용어 정리 및 표현

Graph(그래프) 기본 용어 정리 및 표현

Graph(그래프)란?

• 현실세계의 사물이나 추상적인 개념간의 연결관계를 정점(vertex)과 간선(edge)으로 표현한것

정점(vertex) : 데이터를 표현 (사물, 개념)

간선(edge) : 정점들을 연결 하는데 사용

 

 

 

 

G = (V, E) 

V = {A, B, C, D, E}      //정점들의 집합

E = {e1, e2, e3, e4, e5} //간선들의 집합

e1 = (A, B) //부속해 있는 정점들

e2 = (A, C)

e3 = (B, C)

e4 = (B, D)

e5 = (D, E)

 

 

 

코드로 표현하기

간선들의 가중치가 모두 동일하다는 전제하에 아래처럼 2차원 배열로 표현할 수 있다.

2차원 배열의 세로, 가로 모두 Vertex 들을 가리킨다

가로의 인덱스는 곧 vertex들의 순서이고

순서대로 A, B, C, D, E를 가리킨다

이때 0 또는 1로 표현하는데, 인접(adjacent)해 있다면 1로 표현하고

그렇지 않으면 0으로 표현한다

위와 같이 인접관계를 행렬(2차원 배열)로 표현한 것을 "인접 행렬" 이라고 한다

그외에도 2차원 배열이 아닌 리스트를 통해 인접관계를 표현한 것을 "인접 리스트" 이라고 한다 

 

그래서

vertex A는 인접해 있는 vertex가 B와 C 이므로

B index = 1

C index = 2

 

이기 때문에 1번째, 2번째 값에 1(true)이 들어간다

{0, 1, 1, 0, 0}, //A

 

vertex B는 A,C,D 이다

A index = 0

C index = 2

D index = 3

배열의 0번째, 2번째, 3번째에 1(true)이 들어간다

{1, 0, 1, 1, 0}, //B

 

이런식으로 정리하다 보면, 아래와 같이 정리가 된다.

 

{
    {0, 1, 1, 0, 0}, //A
    {1, 0, 1, 1, 0}, //B
    {1, 1, 0, 0, 0}, //C
    {0, 1, 0, 0, 1}, //D
    {0, 0, 0, 1, 0} //E
};

 

 

용어 정리

sparse graph : 노드의 수보다 엣지 수가 적은 그래프, vertex > edge

 

 

dense graph : 노드의 수 보다 엣지 수가 큰 그래프, vertex < edge

 

 

인접(incident), 부속(adjacent) : 위 그래프에서 vertex A와 C는 edge e2로 연결되어 있다, 이때 vertex A와 C는 서로 인접(adjacent)해 있다. 그리고 edge e2는 두 vertex A 와 C에 부속(incident)해 있다고 한다

 

degree : 하나의 vertex 에 연결된 edge 의 수

 

loop : 하나의 edge가 하나의 노드에만 부속해 있을때

 

 

isolated vertex : 하나의 vertex에 부속해 있는 edge가 전혀 없을때

 

adjacency matrix(인접 행렬) : 그래프 이론에서 인접 관계를 행렬로 표현한 것

 

adjacency list(인접 리스트) : 그래프 이론에서 인접 관계를 리스트로 표현한 것