그래프

개요

그래프는 점(Vertex)과 이음선(Edge)으로 이루어진 수학적 구조이다. 이를 형식화하면 다음과 같이 표현할 수 있다.

• G = (V, E)
• V = {v₁, v₂, v₃, ... , v_n}
• E = {(v_i, v_j), ... }

즉, 그래프는 점 집합과 이음선 집합의 순서쌍이다. 이음선 집합의 이음선은 V²의 부분집합이다. V², 즉 V×V는 집합론에서 교차곱(Cross Product) 또는 데카르트곱(Cartesian Product)이라고 불리는 연산의 결과물이다. 위와 같이 집합론의 기호들을 사용하여 표현된 그래프는 비교적 쉽게 행렬 표기로 바꿀 수 있다. 예를 들어, v_i와 v_j가 서로 연결되어 있을 경우, 그래프를 나타내는 행렬 G의 원소 G[i][j]는 1이며, 연결되어 있지 않을 경우 0이다.

특수한 그래프

용도에 따라 방향 있는 그래프(directed graph)와 가중치 있는 그래프(weighted graph)를 정의하여 사용한다. 위의 그래프 G를 의미하는 행렬을 예로 들면, 방향 있는 그래프는 대칭행렬이 아닐 수 있다. 즉, G[i][j]≠G[j][i]일 수 있다. 반면 방향 없는 그래프는 필연적으로 대칭행렬이다. 가중치 있는 그래프는 이음선이 특수한 속성을 가질 때 이용한다. 이 경우, 그래프 G를 나타내는 행렬의 각 원소는 점들 사이의 이어짐 여부를 나타냄과 동시에, 각 이음선에 가해진 가중치를 나타낸다. 따라서 행렬 G는 가중치 행렬(weight matrix)이라고 할 수 있다.

또한, 그래프의 이음선들 사이의 순환(recursion)이 없으면서 모든 점이 하나 이상의 이음선과 연결된 특수한 경우를 트리(Tree)라고 부른다. 학부 과정을 기준으로 볼 때, 단언컨대 트리는 자료구조의 꽃이다.

용도

가중치 있는 그래프의 기초적인 여러 활용방식이 있다. 이 활용방식들은 아주 실용적이다. 예를 들어, 최소비용신장트리(minimum spanning tree) 알고리즘과 최단경로 찾기(shortest path) 알고리즘은 계산 시간을 획기적으로 줄여주는 아주 고마운 알고리즘일 뿐만 아니라, 시험에도 자주 출제되는 단골 문제이다.

점근상한표기법 O(n)이 요구되는 순차검색 알고리즘을, 그래프 개념을 이용한 비교 기반 정렬 알고리즘을 채택하여 O(n·log(n))시간만에 정렬한 후, 이진검색 알고리즘을 이용하여 검색시간을 O(log(n))으로 단축시킬 수 있다. 그러나 정렬되지 않은 데이터는 이진검색을 사용할 수 없다.