그래프란?(What is a Graph?)
그래프의 개념은 1736년 수학자 레온하르트 오일러가 쾨니히스베르크의 다리에 대한 문제를 풀면서 처음 등장했다. 오일러는 각 섬을 정점으로 표현하고 다리는 엣지로 표현하면서 모든 다리를 한번씩만 거쳐서 원래대로 돌아오는 방법은 존재하지 않는다는 것을 증명했다. 이러한 그래프는 현대에 와서는 전기 회로의 분석, 최단 경로 검색, 컴퓨터 통신 네트워크, 인공지능등 많은 분야에서 사용되고 있다.
자료구조에서 그래프(graph)는 공집합이 아닌 정점들(vertex)의 집합과 이 정점들을 서로 연결하는 엣지들의 집합으로 정의할 수 있다. 그래프에서 정점(vertex)은 데이터를 가지는 노드이며, 서로 다른 두 정점을 잇는 선을 엣지(edge) 또는 간선이라고 한다. 그래프의 엣지는 (u, v)로 표현하고 V(G)와 E(G)를 각각 그래프 G에 대한 정점과 엣지의 집합이라고 하면 그래프 G는 다음과 같이 표현될 수 있다.
그래프의 종류(Types of graphs)
1. 단순 그래프와 다중 그래프(Simple graph & Multigraph)
단순 그래프(simple graph)는 셀프 루프(self loop)를 가지지 않고, 서로 다른 두 정점 간에 중복된 엣지를 가지지 않는 그래프를 말한다. 단순 그래프는 그래프중에서 가장 기본적인 형태의 그래프이다. 단순 그래프의 두 번째 특징을 가지지 않는 그래프는 다중그래프라고 한다. 즉, 다중그래프는 서로 다른 두 정점 사이에 2개 이상의 간선을 가지는 그래프이다.
2. 무방향 그래프와 방향 그래프(Undirected graph & Directed graph)
무방향 그래프는 엣지에 방향이 없는 그래프이다. 무방향 그래프의 엣지를 표현할 때는 (V0, V1)과 같이 표현한다. 방향을 가지는 그래프인 방향 그래프(directed graph or digraph)는 엣지가 방향성을 가지기 때문에 엣지를 표현할 때는 <v0, v1>, <v1, v0>가 서로 다른 엣지로 표현되어 진다. <v0, v1>에서 v0는 머리(head)라고 하며 v1은 꼬리(tail)라고 한다.
3. 완전 그래프와 부분 그래프(Complete graph & Subgraph)
완전 그래프는 모든 노드들이 엣지로 연결되어 있는 그래프를 말한다. 완전 그래프의 엣지의 개수는 노드의 개수를 N이라고 할 때, 무방향 그래프일 경우 N(N-1)이고 방향 그래프일 경우 N(N-1)/2이다. 두 정점이 엣지로 연결되는 경우 두 정점은 인접(adjacent)하다고 하며, 이 엣지는 두 정점에 부속(incident)되었다고 한다. 부분 그래프는 그래프 G에 대해서 부분 집합인 그래프이다. 부분 그래프의 조건을 식으로 나타내면 다음과 같다.
그래프 G에 대해 다음 조건을 마족하는 그래프 G`은 그래프 G의 부분 그래프라 한다.
V(G`) ⊆ V(G) and E(G`) ⊆ E(G)
4. 가중치가 있는 그래프(weighted graph)
가중치 그래프는 그래프의 엣지에 수치를 부여한 것이다. 예를 들어 서울, 부산, 춘천을 정점으로 하는 그래프가 있다고 하자. 이때 각 도시를 잇는 기차길을 엣지라고 하면 엣지가 나타내는 정보는 기차길의 길이일수도 있고 기차길을 까는 비용일 수도 있다. 이때 이러한 정보를 수치로 나타내는 것을 가중치(weight)라고 한다. 이러한 가중치를 가지는 그래프를 가중치 그래프(weighted graph)라고 한다.
그래프 용어
다음은 그래프 관련 용어를 표로 정리한 것이다. 나온 것도 있고 나오지 않은 것도 있으니 혹시 나오지 않았다면 이 표를 참고하길 바란다. 용어를 이해하는데 그림이 필요한 경우는 이후에 그림과 같이 설명하겠다.
연결 그래프(connected graph)
연결그래프는 모든 정점들이 연결되어 있는 그래프이다. 왼쪽의 두 그래프는 연결 그래프이다. 이진 트리를 보고 이상할 수 있지만 이진 트리도 정점과 엣지를 가지고 있기 때문에 엄연히 그래프이다. 반면, 오론쪽 그래프는 정점 0으로 가는 엣지가 없다. 그러므로 연결이 되지 않은 그래프이다.
연결 요소(connected component)
연결 요소에 대한 정의를 영문 위키피디아에서 찾아보면 어떠한 그래프의 부분 그래프가 아닌 연결된 부분 그래프라고 나온다. 필자도 처음에는 헷갈렸기에 그림을 보면 조금 이해하기 쉬울 것이다.
위 그림을 보면 정점이 0부터 8까지인 그래프가 있다. 이 그래프는 각각 H1, H2로 두 덩어리로 나누어져 있다. 여기서 H1과 H2를 연결 요소라고 부른다. H1과 H2는 각자가 가장 큰 서브그래프이다. 이 그래프는 H1과 H2를 연결 요소로 갖는 연결되지 않은 그래프인 것이다. 그러면 단순 그래프의 경우는 연결 요소가 몇개를 가지는지 생각해보자. 단순 그래프에서 가장 큰 서브 그래프는 자기 자신이다. 즉, 단순 그래프는 1개의 연결 요소를 가지는 것이다. 그래프가 몇 덩어리로 나누어졌나가 곧 연결 요소의 개수이다.
'자료구조' 카테고리의 다른 글
| 깊이 우선 탐색(DFS : Depth First Search) (0) | 2022.03.30 |
|---|---|
| 그래프 표현 (2) | 2022.03.30 |
| AVL 트리(AVL Tree) (0) | 2022.03.29 |
| 이진 탐색 트리(Binary search tree) (0) | 2022.03.29 |
| 일반 트리에서 이진 트리로 변환 (0) | 2022.03.29 |