그래프

주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프 방향 그래프(directed graph, digraph) 최단 경로 알고리즘 그래프 순회(graph traversal) 평면 그래프(planar graph) 그래프의 채색(graph coloring)

기본 용어 그래프(graph) 그래프 G는 다음의 두 가지 집합으로 구성되며 G={V, E} 로 표시한다. 여기서 V는 정점(vertex)들의 집합이며, E는 정점들을 연결하는 선(edge)들의 집합이다. e1 e2 v3 e3 e5 e6 e9 e10 v2 v1 v4 v6 v8 v5 v7 v9 e4 e7 e8

임의의 연결선 e=(u,v)에 대해서 정점 u와 v는 서로 인접(adjacent)했다고 하며, u와 v는 e의 끝점(end point) 이라고 한다. e는 정점 u와 정점 v에 접합(incident)한다고 한다. 연결선의 두 끝점이 같은 정점이면 이 연결선을 루프(loop)라고 한다. 또한 두 개 이상의 연결선이 같은 끝점을 가지면 이 연결선을 다중 연결선(multiple edge)이라고 한다. 이와 같이 다중 연결선이나 루프를 갖는 그래프를 다중 그래프(multiple graph)라고 한다. 그리고 다중 그래프가 아닌 그래프를 구분하여 단순 그래프(simple graph)라고 부르기도 한다.

예 e1과 e3, e2와 e4는 다중 연결선이다. e5는 루프이다. v1 e8 e5 e1 e3 v2 e6 v4 e2 e4 e7

정점 u에 접합된 연결선의 수를 정점 u의 차수(degree)라고 한다. 차수는 deg(u)와 같이 표기하기도 한다. v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7 e8 deg(v4)=5 deg(v3)=3,

그래프에서 모든 정점의 차수의 합은 모든 연결선 수의 2배이다. <정리> 그래프에서 모든 정점의 차수의 합은 모든 연결선 수의 2배이다.                          deg(v1)=3, deg(v2)=5, deg(v3)=3, deg(v4)=5이고 연결선 의 수는 8이다. v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7 e8

두 정점 u와 v 사이에 연결선이 존재하면 두 정점은 연결(connected)되었다고 한다. 그래프 G의 모든 정점들이 상호 연결되어 있으면 G는 연결 그래프(connected graph)라고 하며, 그렇지 않은 그래프는 비연결 그래프(disconnected graph) 라고 한다. 예: 연결 그래프와 비연결 그래프 v2 v1 v3 v4 v5 v6 e1 e2 e3 e4 e7 e8 e5 e6

길이(length) 두 정점의 경로를 구성하는 연결선의 수를 경로의 길이라고 한다. 닫힌 경로(closed path) 만약 경로 {v1, v2, ... ,vn}에서 v1=vn인 경로  순환(cylcle 혹은 circuit) 3개 이상의 연결선을 갖는 경로에서 어떤 연결선도 중복되지 않은 닫힌 경로(closed path) 순환 그래프(cylcled graph)와 비순환 그래프(acycled graph) 이러한 경로를 갖는 그래프를 순환 그래프(cycled graph), 그렇지 않은 그래프를 비순환 그래프(acycled graph)라고 한다.

두 정점의 거리(distance)는 두 정점 간의 최단 경로의 길이를 말하며, 직경(diameter)은 그래프 상의 임의의 두 정점 사이의 길이 중 최장 길이, 즉 가장 긴 길이를 말한다. 예 v1과 v6을 연결하는 경로는 {e1, e4, e7}(길이는 3), {e1, e3, e5, e8}(길이는 4), {e1, e3, e5, e6, e7}(길이는 5) 등 여러 가지 경로가 존재하는데 이 중 최단 경로는 {e1, e4, e7}으로 두 정점의 거리는 3이 된다. v2 v1 v3 v4 v5 v6 e1 e2 e3 e4 e7 e8 e5 e6

그래프 G={V,E}가 있을 때, V'⊆V이고 E'⊆E인 그래프 G'={V', E'}를 G의 부분 그래프라고 한다. 부분 그래프(subgraph) 그래프 G={V,E}가 있을 때, V'⊆V이고 E'⊆E인 그래프 G'={V', E'}를 G의 부분 그래프라고 한다. (a) (b) v2 e4 v4 v2 v1 v3 v4 v5 v6 e1 e2 e3 e4 e7 e8 e5 e6 e1 v1 e3 v6 e2 e5 v3 v5 (c) v2 e4 v4 e1 v1 e3 v6 e2 e5 v3 v5

동형 그래프(isomorphic graph) 임의의 두 그래프 G={V, E}와 G'={V', E'}에 대하여 다음의 조건을 만족하는 함수가 1:1 관계의 함수이면 두 그래프 G와 G'를 동형 그래프라고 한다.       함수 f: v → v' (v∈V, v'∈V')       (x,y) ∈ E ⇔ (f(x), f(y)) ∈ E' 그리고 이 관계가 성립하는 함수 f를 동형(isomophic)이라고 한다. a c b d e g f h

예: 동형 그래프들 v1 v2 v3 v4 v1’ v2’ v3’ v4’ v1 v2 v3 v4 v5 v1’ v2’ v3’ v4’

완전 그래프(complete graph) 그래프G={V, E}가 모든 정점 사이에 연결선이 존재하면 완전 그래프는 Km으로 표시한다.(m은 정점의 총 수) (b) K4 (c) K5 (a) K3

이분 그래프(bipartite graph) 그래프G={V, E}의 V가 X⋂Y=∅인 두 부분 집합 X와 Y로 갈라지고, 연결선이 x∈X, y∈Y인 (x,y)의 쌍으로 이루어지면 G는 이분 그래프라고 한다. 또한 X의 모든 정점과 Y의 모든 정점 사이에 연결선이 존재하면 G를 완전 이분 그래프(complete bipartite graph) 라고 하며 Km,n으로 표시한다. (m은 X의 개수, n은 Y의 개수)

이분 그래프 완전 이분 그래프 X Y a b c d e f

정규 그래프(regular graph) 그래프 G={V, E}의 모든 정점의 차수가 같으면, G를 정규 그래프라고 한다. 예: deg=4인 정규 그래프

예: 정규 그래프들

주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프 방향 그래프(directed graph, digraph) 최단 경로 알고리즘 그래프 순회(graph traversal) 평면 그래프(planar graph) 그래프의 채색(graph coloring)

그래프의 표현 인접 행렬(adjacent matrix) 인접 리스트(adjacent list) 접합 행렬(incidence matrix)

인접 행렬 인접 행렬은 그래프를 구성하는 두 정점들 간에 연결선의 존재 여부를 나타내는 방법이다. 그래프를 구성하는 정점들의 집합을 V={1,2,3,...,n}이라고 하면 그래프는 n x n의 행렬로서 표현되는데 행렬의 각 요소는 다음과 같이 정의된다. aij = 1: 두 정점 i와 j 사이에 연결선이 존재하는 경우          0: 두 정점 i와 j 사이에 연결선이 없는 경우

예: 인접 행렬로 표현한 그래프의 예 M = 2 1 3 4 5 e1 e2 e3 e4 e5 1 2 3 4 5 0 1 1 0 0 1 2 3 4 5 0 1 1 0 0 1 0 1 1 0 3 1 1 0 0 0 4 0 1 0 0 1 5 0 0 0 1 0 M =

인접 리스트 인접 리스트는 그래프의 각 정점과 연결선을 갖는 정점들을 연결 리스트(linked list)로 표현하는 방법이다. 2 1 3 4 5 e1 e2 e3 e4 e5

접합 리스트 그래프를 표현하는 또 다른 방법은 각 정점에서 접합되는 연결선의 존재 여부를 행렬로서 나타내는 방법이다. V={1,2,3,...,m}, E={e1,e2,..., en}인 그래프는 m x n의 행렬로서 표현되는데 행렬의 각 요소는 다음과 같이 정의된다. aij =  1: 연결선 ej가 정점 i에 접합된 경우           0: 그렇지 않은 경우

예: 접합 리스트로 표현한 그래프 M = 2 e4 4 e1 e3 1 e5 e2 3 5 e1 e2 e3 e4 e5 1 1 0 0 0 1 0 1 0 0 3 0 1 1 1 0 4 0 0 0 1 1 5 0 0 0 0 1 M =

주요 내용 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프 방향 그래프(directed graph, digraph) 최단 경로 알고리즘 그래프 순회(graph traversal) 평면 그래프(planar graph) 그래프의 채색(graph coloring)

쾨니스버그의 다리들과 그래프 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7

한 줄로 그리기 문제: 다음의 그래프 중 한 정점에서 시작해서 연결선을 한 번만 지나면서 그래프를 다 그릴 수 있는 것은 어느 것인가?

오일러 경로(Eulerian path) 그래프 G의 오일러 경로는 G의 모든 연결선을 한번만 방문하는 경로이다. 닫힌 오일러 경로(closed Eulerian path)를 오일러 순환(Eulerian cycle 혹은 Circuit)이라고 한다. 오일러 순환이 존재하는 그래프를 오일러 그래프라고 한다.

<정리> 오일러 경로를 갖기 위한 필요충분 조건 2개 이상의 정점을 갖는 연결 그래프에서 홀수 차수(odd degree)를 갖는 정점이 하나도 없거나 오직 두 개만 존재해야 한다. 홀수 차수를 갖는 정점을 홀수점(odd vertex)라고 부르면, 그래프가 오일러 경로를 갖는 것과 그래프가 0 혹은 2개의 홀수점을 갖는 것은 동치 관계(equivalence relation)이다. 특히 모든 정점이 짝수 차수를 가지면 이 그래프는 오일러 그래프이다.

출발점과 종료점이 다른 경우 출발점과 종료점이 일치하는 경우

홀수점이 2개인 그래프는 한 줄로 그리기가 가능하며, 이 때 오일러 경로는 한 홀수점에서 시작하여 또 다른 <정리> 홀수점이 2개인 그래프는 한 줄로 그리기가 가능하며, 이 때 오일러 경로는 한 홀수점에서 시작하여 또 다른 홀수점에서 끝나야 한다. deg=2 deg=3 a b a b (시작점) d c c d deg=3 deg=2 (종료점)

예: 오일러 경로를 갖는 그래프 시작점 종료점 deg=3 deg=4 deg=3 deg=2 a d a b c d b c e f

예: 오일러 순환을 갖는 그래프 deg=4 deg=4 deg=4 deg=2 a a b c d b c d e f g e f g

예제 다음의 그래프는 오일러 경로를 갖고 있는가? deg=3 deg=3 deg=3 deg=6 deg=3 deg=3 deg=3 a b deg=3 deg=6 deg=3 f g c deg=3 deg=3 e d

해밀톤 경로(Hamitonian path) 그래프 G={V,E}에서 모든 정점을 정확히 한 번만 지나는 경로를 해밀톤 경로(Hamilton path)라고 한다. 해밀톤 순환(Hamiltonian cycle 혹은 circuit) 그래프 G={V,E}에서 모든 정점을 정확하게 한 번만 포함하는 순환을 해밀톤 순환이라고 한다.

G2는 해밀톤 경로는 존재하지만 해밀톤 순환은 존재하지 않는다. G3는 해밀톤 경로와 순환이 존재하지 않는다. 예: G1은 해밀톤 순환이 존재한다. G2는 해밀톤 경로는 존재하지만 해밀톤 순환은 존재하지 않는다. G3는 해밀톤 경로와 순환이 존재하지 않는다. a b c a a b c b d f c g f e e d e g d G1 G2 G3

예제: 방문 판매원 문제(traveling salesman problem) 해밀톤 순환은 1857년에 만들어진 Icosian 퀴즈 문제에서 비롯되었다. 이 퀴즈 문제는 12면체의 20개의 각 정점에 도시 이름을 적고 어느 한 도시에서 출발하여 모서리를 따라서 다른 모든 19개의 도시를 방문하고 처음 출발했던 도시로 돌아오는 게임이다. 물론 각 도시는 단 한번만 방문할 수 있다. 1 20 13 2 19 5 14 12 6 18 15 17 11 16 7 8 10 9 3 4

예: 해밀톤 순환(1) 4개 도시의 연결 그래프 A로 부터 해밀톤 순환

예: 해밀톤 순환(2) 탐색해야 되는 경로의 수: 트리의 leaf의 수 트리의 높이 : n+1 Leaf의 수: 2n

해밀톤 순환 찾는 알고리즘 복잡도 알고리즘 복잡도: O(2n) 복잡도 함수는 다항식이 아니라 지수식이다. 몹시 어려운 문제 유사한 복잡도 문제 Bin packing Chess 암호 해독, 등등