그래프
- 쾨니히스베르크 다리문제를 해결하기 위해 오일러가 최초 사용
- 오일러는 불가능을 증명했으며, 모든 지점과 연결된 다리의 수가 짝수여야만 모든 다리를 한 번씩 거쳐 제자리로 돌아올 수 있음
-> 이를 오일러 경로라고 한다
그래프의 정의
- 그래프는 G(V, E)로 나타낸다
- V : 공집합이 아닌 정점(Vertex)들의 유한집합
- E : 간선(Edge)들의 유한집합으로 정점의 쌍으로 구성
그래프의 종류
- 무방향 그래프(Undirected Graph)
- 간선(Edge)에 방향이 없는 그래프
- 정점 v0와 v1사이의 간선은 (v0, v1)으로 표기한다
- 방향이 없으므로 (v0, v1) == (v1, v0)이 성립한다 - 방향 그래프(Directed Graph, Digraph)
- 간선(Edge)에 방향이 있는 그래프
- 정점 v0과 v1사이의 간선은 <v0, v1>으로 표기한다
- 여기서 v0은 꼬리(tail), v1은 머리(head)라고 한다 v0 -> v1
- 방향이 있으므로 <v0, v1> != <v1, v0>이다
다중간선에 따른 종류
- 단순 그래프(Simple Graph)
- 다중 간선(Multiple Edge)을 가지지 않는 그래프 - 다중 그래프(Multigraph)
- 다중 간선(Multiple Edge) 가지는 그래프
단순 그래프의 분류
- 완전 그래프(Complete Graph)
- 모든 정점들 사이에 간선이 존재하는 그래프
- 정점의 개수가 n이면
-> 무방향 완전 그래프의 전체 간선 개수 : n(n - 1) / 2
-> 방향 완전 그래프의 전체 간선의 개수 : n(n - 1) - 정규 그래프(Regular Graph)
- 모든 정점의 차수가 같은 그래프
- k-정규 그래프란 모든 정점의 차수가 k인 그래프 - 이분할 그래프(Bipartite Graph)
- 정점 집합 V를 두개의 부분집합 X, Y로 분할할 수 있고, X에 있는 정점과 Y에 있는 정점 사이에만 간선이 존재하는 그래프 - 완전 이분할 그래프(Complete bipartite graph)
- 집합 X에 속해 있는 모든 정점들과 집합 Y에 속해있는 모든 정점들 사이에 간선이 존재하는 그래프 - 트리 그래프(Tree graph)
- 사이클이 존재하지 않는 연결된 그래프
그래프 관련 용어
- 인접(Adjacent)
- 두 정점이 하나의 간선에 의해 서로 연결 된 경우 두 정점은 서로 인접한다고 한다.
- 이 때 해당 간선은 두 정점에 부속(Incident)되어 있다고 한다.
-> 간선 (v, w)가 존재한다면 정점 v와 w는 서로 인접하고, 이 간선(v, w)는 정점 v와 w에 부속한다 - 경로(Path)
- 정점 vi ~ vk까지 연결되어 있을 때, 연결까지 사용된 정점들의 나열 vi ........... vk - 단순 경로(Simple Path)
- 한 경로 상에서 처음과 마지막을 제외한 모든 정점들이 다른 경로(중복 방문x) - 경로의 길이
- 경로 내의 간선의 개수. 즉 정점이 n개일 때 n - 1개가 됨 - 부 그래프(Subgraph)
- 그래프 G=(V, E)와 G'=(V', E')가 주어졌을 때
- ① V'(G') ⊆ V(G)
- ② E'(G') ⊆ E(G) - 연결 (Connected)
- 무방향 그래프 G에서 정점 v1 ~ v2에 이르는 경로가 존재하면 v1과 v2는 연결(connected)이라고 한다.
- ① 연결그래프(Connected Graph) : 그래프 G가 속하는 모든 정점들이 연결되어 모든 정점 쌍에 대해 경로가 존재하는 그래프
- ② 단절 그래프(Disconnected Graph) : 모든 정점들이 연결되지 않아, 어느 정점 쌍에는 경로가 존재하지 않는 그래 - 사이클(Cycle)
- 시작점과 끝점이 같은 단순 경로 - 사이클 그래프(Cycle Graph)
- 하나 이상의 사이클을 갖는 그래프 - 정점의 차수(Degree)
- 해당 정점에 부속된 간선의 수
- 방향그래프의 경우
- 진입 차수(in-degree) : 정점으로 들어오는 간선의 수(정점이 head)
- 진출 차수(out-degree) : 정점에서 나가는 간선의 수(정점이 tail)
그래프의 표현
- 인접 행렬(Adjacency Matrix)
- 정점들 사이의 인접 관계를 행렬을 이용하여 표현하는 방법
- 행 번호는 출발정점 즉, tail
- 열 번호는 도착정점 즉, head
- 방향그래프의 경우, tail -> head, head -> tail의 간선을 모두 고려
- 장점 : 임의 두 정점 사이의 간선 존재 여부를 쉽게 결정 가능, 정점의 차수를 쉽게 계산할 수 있음
- 단점 : 간선의 수 계산, 연걸과 단절그래프 결정 등의 연산 시행 시 많은 시간이 요구됨 -> n^2-n개의 원소들을 모두 조사해야 하므로 O(n^2)의 시간복잡도가 필요
- 인접 리스트(Adjacency List)
- 정점의 수가 n일 경우 n개의 연결 리스트로 그래프를 표현하는 방법
- 장점 : 정점의 차수를 쉽게 구할 수 있음
-> n개의 노드를 갖는 그래프에서 간선의 수를 결정하는데 드는 시간 복잡도 = O(e + n)
- 단점 : 방향 그래프를 표현하는 경우에는 진입차수를 결정하기가 매우 복잡해짐
-> 이를 해결하기 위해 역 인접리스트, 직교리스트 사용
기본적 그래프 연산
- 깊이 우선 탐색(DFS)
① 시작 정점 v를 결정
② v에 인접한 정점 중 방문되지 않은 정점 w를 선택하여 DFS를 다시 시작
③ 인접한 모든 정점이 이미 방문된 정점 u를 만나면, 방문되지 않은 인접된 정점을 가진 마지막 정점으로 되돌아가서 DFS를 다시 시작
④ 더이상 방문할 정점이 없을 때 까지 위 과정을 반복
-> 탐색 도중 인접한 모든 정점이 이미 방문된 정점을 만났을 때, 바로 지전 방문 정점으로 되돌아가기 위해 스택 자료구조를 이용
- 인접리스트를 사용하여 그래프를 표현한 경우 시간복잡도는 O(v + e)
- 인접 행렬을 사용하여 그래프를 표현하는 경우 v에 인접한 정점을 찾는데 O(n), 여기에 n개의 정점이 있으므로 O(n^2) - 너비 우선 탐색(BFS)
① 시작 정점 v를 결정
② 정점 v에 인접하며, 방문하지 않은 모든 정점을 방문하고, 한 단계 아래 깊이로 내려가 다시 모든 정점을 방문한다.
③ 더이상 방문할 정점들이 없을 때 까지 위 과정을 반복
-> 먼저 탐색한 정점의 인접 정점을 순서대로 처리하기위해 큐 자료구조를 이용
- 인접리스트를 사용하여 그래프를 표현한 경우 시간복잡도는 O(v + e)
- 인접 행렬을 사용하는경우 DFS와 마찬가지로 O(n^2)
