그래프(Graph)와 그래프 용어

페이스북 친구 관계나 항공 노선처럼 우리 주변에는 수많은 연결망이 존재한다. 그렇다면 이 방대한 연결 관계를 효율적으로 표현하려면 어떻게 해야 할까?

 

바로 그래프라는 자료구조가 그 해답이다. 여기서 말하는 그래프는 미적분에서 보는 좌표 그래프와는 다르다. 이번 글에서는 그래프 자료구조가 무엇인지 자세히 살펴보겠다.

 

1. 그래프

출처: chatGPT

 

그래프는 현상이나 사물을 정점(vertex)과 간선(edge)으로 표현한 것을 말한다. 위의 내용과 동일하다.

 

이러한 구조는 다:다(M:N) 관계를 보여준다.

 

이를 수식으로는 $$G = (V, E)$$로 표현되는데 

 

여기서 V는 정점(노드)의 집합, E는 간선(링크)의 집합이다. 

 

이러한 그래프는 여러 종류가 있다. 가중치에 따라서 가중치가 없는 그래프, 가중치 그래프, 방향이 있냐 없느냐에 따른 방향그래프, 무방향 그래프로 나눌 수 있다.

 

1.1. 가중치 그래프(Weight Graph)

 

가중치 그래프는 각 간선에 숫자로 표현된 "가중치(weight)"가 부여된 그래프다.

 

이 가중치는 물리적 거리, 시간, 비용, 혹은 사회적 관계의 친밀도처럼 두 노드 사이의 크기나 중요도를 정량적으로 나타내는 데 활용된다.

 

수식으로는 $$G = (V, E, w)$$로 표현할 수 있으며,

 

여기서 $w$는 각 간선에 대응하는 가중치의 집합을 의미한다.

 

1.2. 유향 그래프(directed graph)와 무향 그래프(undirected graph)

 

그래프는 간선에 방향이 있느냐 없느냐에 따라 유향 그래프와 무향 그래프로 나뉜다.

 

- 유향 그래프(Directed Graph, Digraph)

간선이 한쪽 방향으로 연결된 그래프. 

 

예를 들어, A에서 B로만 이동할 수 있는 도로망이나 팔로우 관계가 이에 해당한다.

 

수식으로는 $<V_i, V_j>$로 간선을 나타내며, $<V_i, V_j> \neq <V_j, V_i>$가 성립한다.

 

- 무향 그래프(Undirected Graph)

간선에 방향이 없는 그래프.

 

친구 관계처럼 서로 연결이 양방향으로 이루어지는 경우가 이에 해당한다.

수식으로는 $(V_i, V_j)$로 간선을 표현하며, $(V_i, V_j) = (V_j, V_i)$로 간선의 순서는 구분하지 않는다.

 

간단히 말하면 유향 그래프에서는 A→B와 B→A가 서로 다른 간선으로 취급되고, 무향 그래프에서는 같은 간선으로 취급된다.

 

2. 그래프 용어

지금까지 그래프의 종류와 특징을 살펴보았다.

 

그러나 그래프를 실제로 이해하고 다루려면, 각 그래프를 구성하는 기본 용어를 알아야 한다. 다음으로 그래프 용어에 대해서 자세히 살펴보자.

 

2.1. 인접(adjacent)과 부속(incident)

 

인접과 부속은 괄호와 그 안에 있는 간선의 관계를 의미하는 말이다.

 

만약 정점 $V_i$와 $V_j$를 연결하는 간선 $(V_i, V_j)$ 가 있다면, 두 정점은 서로 인접하다고 하며, 이 간선은 두 정점에 부속되어 있다고 말한다.

 

예를 들어 위의 그래프를 보면 정점 A와 인접한 정점은 B와 D가 되고 정점 A에 부속되어 있는 간선이라고 말하면 (A, B)와 (A, D)로 부를 수 있다.

 

2.2. 차수(Degree)

 

차수는 정점에 부속되어 있는 간선의 수이다.

 

예로 들어 왼쪽 그래프의 A의 경우 차수는 2로 연결된 것만 찾으면 된다. 반면 무방향 그래프인 오른쪽은 다르게 진입차수(in-degreee) + 진출차수(out-degree)로 계산해야 한다.

 

여기서 진입차수는 정점을 머리로 하는 간선의 수를 의미하고 진출차수는 정점을 꼬리로 하는 간선의 수를 의미한다.

 

그러므로 오른쪽의 B의 진입차수는 1개, 진출차수는 2개로 총 3개로 계산할 수 있다.

 

2.3. 경로(Path)

 

경로는 그래프에서 간선을 따라갈 수 있는 길을 순서대로 나열한 것을 의미한다.

 

예로 들어 위의 그래프는 A-B-C, A-B-D-C, A-D-C, A-D-B-C가 경로라고 볼 수 있다. 

 

여기서 경로 길이는 경로를 구성하는 간선의 수로 A-B-C의 경우는 간선이 2개로 2라고 할 수 있다.

 

2.4. 단순경로(Simple Path)

 

단순경로는 모두 다른 정점으로 구성된 경로를 말한다.

 

예로 들어 A-B-C는 단순경로라고 볼 수 있다. 하지만 A-B-D-A-B-C이건 단순 경로가 아니다.

 

추가적으로 사이클(cycle)이라는 것도 있다. 사이클이란 단순 경오 중에서 시작 정점과 마지막 정점이 같은 경우를 의미한다.

 

예로 들어 왼쪽 그래프에서 A-B-C-D-A나, 오른쪽 그림에서 A-B-A와 같은 것도 사이클이라고 볼 수 있다.

 

또 DAG(directed acyclic graph)라는 것도 있는데 이는 방향 그래프인데 사이클이 없는 것이라 보면 된다.

 

2.4. 연결 그래프(connected graph)와 단절 그래프(disconnected graph)

 

연결 그래프는 서로 다른 쌍의 정점들 사이에 경로가 있는 그래프다.

 

두 정점 $V_i$에서 $V_j$까지의 경로가 있으면  $V_i$와 $V_j$가 연결되었다고 한다.

 

반면 단절 그래프는 연결되지 않은 정점이 있는 그래프다

---

출처

 

쉽게 배우는 알고리즘 | 문병로 - 교보문고