9-1. 그래프란?
그래프란?
그래프(graph)는 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다.
지하철 노선도를 생각하면 그래프에 대한 이미지가 연상이 될 것이다.
지하철 노선도를 보면 많은 역들이 어떻게 연결돼 있는지 알 수 있고
, 어떤 역에서 어떤 역으로 이동하는 가장 빠른 경로(최단 경로)를 알 수도 있다.
앞에서 다뤘던 선형 자료구조들이나 트리도 그래프의 한 종류로 볼 수 있다.
그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다. G = (V, E)
정점은 여러 가지 특성을 가질 수 있는 객체를 의미라고, 간선은 객체 정점들 간의 관계를 의미한다.
정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
정점은 노드(node)라고도 불리고, 간선은 링크(link)라고도 불린다.
위 그림처럼 그래프는 시각적으로 표현하기도 한다.
하지만 시각적인 형태가 그래프의 정의는 아니다.
위 두 그래프의 그림은 달라 보이지만 실제로는 같은 그래프이다.
그래프는 오직 정점과 간선의 집합이며, 시각적 표현은 이해를 돋는 역할만 한다는 것을 기억하자.
그래프의 역사
그래프는 수학자 오일러(Euler)에 의해 처음 창안되었다.
왼쪽 그림같은 지형에서 "모든 다리를 한번씩 건너서 출발했던 장소로 돌아올 수 있는가?"라는 질문의 답이 없다는 것을 그래프 이론을 이용해 증명했다.
오일러는 이 문제에서 핵심적인 것이 '각 도시(A~D)의 위치가 어떤 관계로 연결되었는가?'라고 생각했다.
그래서 "위치"라는 객체는 정점(vertex)로, 위치간의 관계는 간선(edge)으로 표현해 오른쪽 그림과 같은 그래프(graph) 문제로 변환했다.
그래프에 존재하는 모든 간선을 한번씩만 통과하면서 처음 정점으로 되돌아오는 경로를 오일러 경로(Eulerian tour)라 정의하고, 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다는 오일러의 정리를 증명했다.
그래프의 종류
그래프는 간선의 종류에 따라 몇 가지로 구분된다.
• 무방향 그래프(undirected graph) : 간선에 방향이 표시되지 않은 그래프
무방향 그래프에서 하나의 간선은 양방향으로 갈 수 있는 길을 의미하고, (A, B)와 (B, A)는 같은 간선이다.
• 방향 그래프(directed graph) : 간선에 방향성이 존재하는 그래프
방향 그래프에서 간선은 보통 화살표로 표시한다.
정점 A에서 정점 B로 가는 간선은 <A, B>로 표시한다. <A, B>와 <B, A>는 다른 간선이다.
• 가중치 그래프(weighted graph) : 간선에 비용이나 가중치가 할당된 그래프
가중치 그래프에서의 간선은 두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있어 더 복잡한 관계도 표현할 수 있다.
• 부분 그래프(subgraph) : 그래프 G를 구성하는 정점의 집합 V(G)와 간선의 집합 E(G)의 부분 집합으로 이루어진 그래프
그래프의 용어
- 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
- 정점의 차수(degree) : 그 정점에 연결된 간선의 개수
- 무방향 그래프에서는 모든 정점의 차수를 합하면 간선 수의 2배가 된다.
- 방향 그래프에서는 외부에서 오는 간선의 수를 진입 차수(in-degree)
, 외부로 향하는 간선의 수를 진출 차수(out-degree)라고 한다.
- 경로(path) : 간선을 따라 갈 수 있는 길, 정점의 나열로 표시된다.
- 경로의 길이 : 경로를 구성하는데 사용된 간선의 개수
- 단순 경로(simple path) : 경로 중에서 반복되는 간선이 없는 경로
- 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 같은 경로
- 연결 그래프(connected graph) : 그래프의 모든 정점들 사이에 경로가 존재하는 그래프
- 트리(tree) : 사이클을 가지지 않는 연결 그래프
- 완전 그래프(complete graph) : 모든 정점 간에 간선이 존재하는 그래프