자료구조 34강 - 그래프

쾨니히스베르크(konigsberg) 다리 문제(1736)

 

• 7 bridge problem
• 쾨니히스베르크(독일의 도시) → 칼리닌그라드(리투아니아의 도시)
• 2개의 섬과 7개의 다리
• 어떤 지점에서 출발해도 상관없으니 다리를 한 번씩만 건너도 다시 출발 지점으로 돌아오는 경로
• 오일러(Euler)가 그래프의 개념을 도입해서 해결
• 그래프는 지금도 많이 사용되는 개념
• 다리 문제를 그래프로 추상화함

1. 땅과 섬 → node(vertex)
2. 다리 → edge(link)
3. 다리 문제 → graph에서의 한 붓 그리기 문제

 

- 한붓 그리기 문제

 

• 4개의 vertex
• 각 vertex는 홀수 개의 edge에 연결됨
• 홀수 개의 edge에 연결된 vertex의 수가 4개 이상이면 한 붓 그리기가 불가능한 도형
• 따라서 다리 문제는 " 해가 존재하지 않는다"

 

 

그래프

 

• 개체들 사이의 일대일 관계를 시각적으로 표현하는 수학적 모델

A mathmatical(abstracted) model that represents
the one-to-one(binary) relationship between objects visually

• 그래프는 vertex(꼭지점, 정점)과 edge(간선)의 집합
• G=( V, E )
• V : vertex는 개체를 나타냄
• E : edge는 일대일 관계를 나타내며 vertex의 쌍으로 표현됨

 

- 그래프의 수학적 표현 

 

• V={0, 1, 2, 3}
• E={(0, 2), (0, 3), (1, 2), (1, 3)}

 

- 그래프의 시각적 표현

 

 

- Edge 리스트를 이용한 표현

 

• 4, 4 - vertex의 수, Edge의 수 ( vertex : 0~3 )
• 0, 2
• 0, 3
• 1, 2 - vertex 1과 2를 연결하는 edge
• 1, 3

 

- 방향과 가중치에 따른 그래프의 종류

 

 

- 방향과 가중치에 따른 그래프의 종류2

 

 

 

특별한 그래프

 

- Self edge를 가진 그래프

 

• self edge : (0, 0)
• ex. G=(V, E), V={0, 1, 2}, E={(0, 0), (0, 1), (0, 2), (1, 2)}

 

- Multi edge를 가진 그래프

 

Multi edge : (0, 0), (0, 0)

ex. G=(V, E), V={0, 1, 2}, E={(0, 1), (0, 1), (0, 2), (1, 2)}

 

 

복잡도에 따른 그래프

 

- 완전 그래프(Complete graph)

 

• n개의 vertex들이 서로 연결된 그래프
• 하나의 vertex가 n-1개의 vertex와 연결됨
• Edge의 수 : n(n-1)/2
• 방향 그래프의 경우는 n(n-1)개의 edge를 가짐
• ex. V={0, 1, 2, 3}, n(V)=4, n(E)=4*3/2=6

 

- 밀집 그래프(Dense graph)

 

• n개의 vertex들의 대부분이 서로 연결된 그래프
• Edge의 수 : O(n²)
• 방향 그래프의 경우에도 O(n²)개의 edge를 가짐

 

- 희소 그래프(Sparse graph)

 

• 각 vertex들이 상수 개의 vertex와 연결된 그래프
• 한 vertex에서 연결된 vertex의 수 : O(1)
• Edge의 수 : O(n)

- 복잡도에 따른 그래프의 종류

 

Edge의 수
희소 그래프(sparse graph)	밀집 그래프(dense graph)	완전 그래프(complete)
O(n)	O(n²)	n(n-1)/2