그래프란?

그래프는 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다.

그래프의 역사

그래프는 오일러에 의해 처음 창안되었다. 오일러는 ‘모든 다리를 한번만 건너서 출발했던 장소로 돌아올 수 있는가’라는 문제가 답이 없다는 것을 그래프 이론을 이용하여 증명하였다. 오일러는 이 문제의 핵심은 ‘A, B, C, D의 위치가 어떠한 관계로 연결되었는가?’라고 생각하고 ‘위치’라는 객체는 정점(vertex)로, 위치간의 관계인 ‘다리’는 간선(edge)로 표현하여 그래프 문제로 변환하였다. 오일러는 그래프에 존재하는 모든 간선을 한번만 통과하면서 처음 정점으로 되돌아오는 경로를 오일러 경로(Eulerian tour)라 정의하고, 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다는 오일러의 정리를 증명하였다.

그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다. 수학적으로는 G = (V, E)와 같이 표시한다. 여기서 V(G)는 그래프의 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다. 정점은 여러 특성을 가질 수 있는 객체를 의미하고, 간선은 이러한 객체 정점들 간의 관계를 의미하는데, 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. 정점은 노드(node)라고 불리며, 간선은 링크(link)라고도 불린다.

Untitled

그래프는 시각적으로 표현하기도 하지만 시각적인 형태가 그래프의 정의는 아니다. 아래 그림의 그래프는 시각적으로 다르게 보이지만, 실제로는 동일한 그래프를 나타낸다.

Untitled

그래프의 종류

무방향 그래프

간선에 방향이 표시되지 않은 그래프를 무방향 그래프라 한다. 하나의 간선은 양방향으로 갈 수 있는 길을 의미하고 (A, B)와 (B, A)는 동일한 간선이 된다. 아래 그림의 G1, G2 그래프를 정점과 간선의 집합으로 표현하면 다음과 같다.

V(G1) = {0, 1, 2, 3}, E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}
V(G2) = {0, 1, 2, 3}, E(G3) = {(0, 1), (0, 2)}

Untitled

방향 그래프

간선에 방향성이 존재하는 그래프를 방향 그래프라 한다. 간선은 보통 화살표로 표시되는데, 일방통행 도로와 마찬가지로 한쪽 방향으로만 갈 수 있음을 의미한다. 정점 A에서 정점 B로만 갈 수 있는 간선은 <A, B>로 표시한다. 방향 그래프에서 <A, B>와 <B, A>는 서로 다른 간선이다. 위 그림의 G3은 방향 그래프로 아래와 같이 표현할 수 있다.

V(G3) = {0, 1, 2}, E(G3) = {<0, 1>, <1, 0>, <1, 2>}

가중치 그래프

간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프 또는 네트워크라 한다. 이제 간선은 두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있어 보다 복잡한 관계를 표현할 수 있다.

Untitled

부분 그래프