Total
Search
1. 기본사항
1.1. 주요 용어
•
기본 정의
◦
그래프 G는 꼭지점 (vertex)들과 변(edge)들로 구성
▪
𝑮 = (𝑽, 𝑬), 여기서 𝑽 = {𝒗|𝒗는 꼭지점}, 𝑬 = {𝒆|𝒆는 변}
◦
변은 두 꼭지점을 연결함
▪
연결된 두 꼭지점은 서로 인접(adjacent)한다고 함
▪
변에 의해 발생되었다고 함
◦
병렬 변(parallel edge) : 두 꼭지점을 연결하는 변이 복수개 있을 때
◦
루프(loop) : 동일한 꼭지점을 연결하는 변
◦
고립된 꼭지점(isolated vertex) : 어떠한 변도 연결되지 않은 꼭지점
예제
•
방향 그래프
◦
변이 방향을 가지고 있는 그래프
•
무향 그래프
◦
변이 방향을 가지고 있지 않은 그래프
•
단순 그래프
◦
루프와 병렬 변을 가지지 않는 무향 그래프
•
𝑮 = 𝑽, 𝑬 , 𝑯 = (𝑽′, 𝑬′)가 그래프
◦
𝑽′ ⊆ 𝑽, 𝑬′ ⊆ 𝑬 → 𝑯는 𝑮의 부분 그래프(subgraph)
▪
꼭지점과 변이 모두 부분집합인 경우
◦
𝑽′ = 𝑽, 𝑬′ ⊆ 𝑬 → 𝑯를 𝑮의 신장 부분 그래프(spanning subgraph)
▪
꼭지점의 개수는 같은데, 변의 갯수가 부분집합인 경우
예제
•
𝑮 = 𝑽, 𝑬 , 𝒗 ∈ 𝑽
◦
𝒗의 차수(degree) [𝐝𝐞𝐠 𝒗 ]: 𝒗에 인접한 변의 개수
◦
𝑮의 총 차수(total degree) [𝐝𝐞𝐠 𝑮 ]: 𝑮에 속한 모든 꼭지점의 차수의 합
•
참고) 방향 그래프에서
◦
v의 진입차수: v 로 들어오는 변의 수
◦
v의 진출차수: v에서 나가는 변의 수
•
Handshaking Lemma
◦
그래프에서 차수가 홀수인 꼭지점의 수는 짝수
◦
변은 반드시 2개의 꼭지점을 발생시켜야함. 하나만 있을 수는 없음
◦
총 차수의 개수는 변(edge)의 개수 x 2
예제
1.2. 그래프 탐색
G(V, E) , v0, vk ∈ V 라고 가정
•
v0에서 vk까지의 워크(walk)
•
워크 W의 변들이 모두 서로 다르면 W를 트레일
•
트레일 W의 꼭지점이 모두 다르면 W를 경로
•
참고)
◦
path ⊂ trail ⊂ walk
예제
𝑮 = (𝑽, 𝑬) , 𝑾 = 𝒗𝟎𝒆𝟏𝒗𝟏𝒆𝟐𝒗𝟐⋯ 𝒆𝒌𝒗𝒌 : 워크
•
W가 트레일이고 𝒗𝟎 = 𝒗𝒌이면 W는 닫힌 트레일
•
W가 경로이고 𝒗𝟎 = 𝒗𝒌이면 W는 닫힌 경로로서 사이클(cycle)
◦
길이가 k인 사이클을 k-사이클
예제
𝑮 = 𝑽, 𝑬 : 그래프, 𝒖, 𝒗 ∈ 𝑽
•
𝒖에서 𝒗로 가는 경로가 존재하면 𝒖와 𝒗는 서로 연결되어 있다.
•
𝑽의 꼭지점들은 서로 연결되고 다른 집합과 겹치지 않는 꼭지점들의 집합 𝑽𝟏, 𝑽𝟐,⋯ 𝑽𝒏으로 나눌 수 있음
◦
𝑽𝟏, 𝑽𝟐,⋯ 𝑽𝒏을 𝑮의 연결성분
•
∀𝒖 , ∀𝒗 ∈ 𝑽, 𝒖에서 𝒗로 가는 경로가 존재하면 𝑮는 연결 그래프(connected graph)
◦
𝑮는 오직 하나의 연결 성분으로 구성
예제
2. 그래프의 종류
2.1. 완전 그래프
•
V의 임의의 두 꼭지점을 꺼냈을 때 그 사이에 반드시 Edge(변)이 존재하는 경우
•
완전 그래프의 Kn 은 n(n-1) / 2 개의 변을 가짐
•
모든 꼭지점의 차수는 n-1
2.2. 이분 그래프
•
꼭지점이 2개로 분할되어있고, 모든 변들이 그 꼭지점들을 인접하는 경우
예제
2.3. 완전 이분 그래프
•
꼭지점을 2개로 분할하고, 각 분할된 V1, V2 내 원소들을 임의로 꺼냈을 때 반드시 엣지가 있어야함
예제
2.4. k-정규 그래프
•
𝑮의 모든 꼭지점들이 동일한 수의 인접한 꼭지점을 갖는 경우
•
완전 그래프는 임의의 두 꼭지점을 연결하는 변이 항상 존재함
◦
따라서 완전 그래프 Kn은 (n-1)-정규그래프
◦
여기서 n은 꼭지점의 수를 말함
예제
3. 그래프의 표현
3.1. 발생 행렬 (incidence matrix)
•
𝑮 = 𝑽, 𝑬 : 그래프일 때,
◦
꼭지점을 행으로 변을 열로 하여 변과 꼭지점 사이의 발생관계를 표현한 행렬
발생행렬 𝑴𝑰 = (𝒂𝒊𝒋)
◦
|𝑽| × |𝑬| 크기의 부울행렬
◦
𝒂𝒊𝒋 = 1 (𝒗𝒊가 𝒆𝒋에 의해 발생되는 경우)
◦
𝒂𝒊𝒋 = 0 (그 밖의 경우)
예제
3.2. 인접 행렬
•
𝑮 = 𝑽, 𝑬 : 그래프일 때,
◦
꼭지점을 행과 열로 하여 꼭지점과 꼭지점 사이의 인접관계를 표현한 행렬
⇒ 인접행렬 𝑴𝑨 = (𝒂𝒊𝒋)
◦
|𝑽| × |𝑽| 크기의 행렬
◦
𝒂𝒊𝒋 = 𝒗𝒊에서 𝒗𝒋로의 연결 개수
예제
3.3. 인접 리스트
•
𝑮 = 𝑽, 𝑬 : 그래프일 때,
◦
각 꼭지점에 인접하는 꼭지점들을 차례로 연결 리스트로 표현한 것
예제
4. 그래프의 탐색
4.1. 평면 그래프와 4색 정리
•
평면 그래프
◦
그래프의 모든 변을 서로 교차하지 않게 그릴 수 있는 그래프
•
평면 그래프가 아닌 예
•
평면 그래프의 예
◦
정규 그래프: 모든 꼭지점들이 동일한 수의 인접한 꼭지점을 갖는 그래프
◦
완전 그래프: 임의의 두 꼭지점을 연결하는 변이 항상 존재하는 그래프
◦
Kn은 (n-1) 정규 그래프
•
오일러의 공식
◦
연결된 평면 그래프에서 면(face) 변들로 만들어지는 사이클을 경계로 형성된 공간
◦
예)
▪
𝒇𝟏 : 사이클 (1, 2, 3, 1)을 경계
▪
𝒇𝟐 : 사이클 (2, 3, 4, 2)을 경계
▪
𝒇𝟑 : 사이클 (1, 3, 4, 5, 4, 1)을 경계
▪
𝒇𝟒 : 사이클 (1, 2, 4, 1)을 경계
◦
연결된 평면 그래프에서 꼭지점의 수를 𝒗, 변의 수를 𝒆, 면의 수를 𝒇라고 하면
𝒗 − 𝒆 + 𝒇 = 𝟐 이다.
•
4색정리
◦
지도의 인접한 구역을 서로 다른 색으로 칠하는데 오직 4가지 색이면 충분하다.
4.2. 오일러 투어
•
오일러 트레일 (Eulerian trail)
◦
그래프의 모든 변들을 각각 한 번만 지나는 트레일
•
오일러 투어 (Eulerian tour [circuit/cycle])
◦
닫힌 오일러 트레일 (즉, 시작점과 종점이 같은 오일러 트레일)
•
오일러 그래프 정리
◦
연결 그래프가 오일러 투어를 가지면 모든 꼭지점의 차수는 짝수
▪
연결 그래프 𝑮 = (𝑽, 𝑬)가 오일러 투어를 가진다고 가정함
▪
𝑽의 임의의 꼭지점 𝒗는 다른 꼭지점들과 변에 의해 연결됨
▪
𝒗와 연결된 변은 오일러 투어에 의해 𝒗로 들어오는 변과 나가는 변으로 구분할 수 있음
▪
들어오는 변의 수와 나가는 변의 수는 항상 동일함
▪
따라서 모든 꼭지점의 차수는 짝수임
◦
연결 그래프 𝑮의 모든 꼭지점의 차수는 짝수이면 𝑮는 오일러 그래프
▪
그래프 𝑮가 연결 그래프이고 모든 꼭지점의 차수는 짝수라 가정할때, 오일러 투어는 다음 단계를 거쳐 구할 수 있음
▪
단계
•
[단계1] 𝑮의 임의의 꼭지점 𝒗를 고른다.
•
[단계2] 𝒗에서 시작하고 𝒗에서 끝나는 임의의 사이클 𝑪을 선택한다.
•
[단계3] 𝑪가 오일러 투어이면 증명을 끝낸다. 만약 아니라면 아래 과정을 반복한다.
•
[단계3-1] 𝑮에서 𝑪에 속하는 모든 변을 제거하고 새로운 𝑮′을 만든다.
•
[단계3-2] 𝑪와 𝑮′가 공유하는 꼭지점 중 하나를 고르고 𝒘라 한다.
•
[단계3-3] 𝒘에서 시작하고 𝒘에서 끝나는 임의의 사이클 𝑪′을 선택한다.
•
[단계3-4] 기존의 𝑪와 새로 선택된 𝑪′을 합쳐서 새로운 𝑪를 만든다
4.3. 해밀턴 경로
•
해밀턴 경로 (Hamiltonian path)
◦
그래프의 모든 꼭지점들을 한 번씩만 지나는 경로
•
해밀턴 사이클 (Hamiltonian cycle)
◦
닫힌 해밀턴 경로 (시작점과 종점이 같은 해밀턴 경로)
해밀턴 경로와 해밀턴 사이클 예제
5. 그래프 활용
5.1. 가중 그래프
•
가중 그래프 (weighted graph)
◦
그래프의 각 변에 실수값이 붙여진 그래프
◦
변에 부여된 값은 가중치(weight)라고 함
5.2. 최단 경로 문제
•
최단경로 문제
◦
출발지와 도착지가 주어졌을 때 가장 짧은 경로를 찾는 문제
•
최소 신장 트리 문제
◦
그래프의 모든 꼭지점을 최소 수의 변으로 연결하는 문제
•
신장 트리
◦
그래프 𝑮 = (𝑽, 𝑬)의 모든 꼭지점을 연결하고 사이클이 없는 𝑮의 부분 그래프
◦
𝑮의 신장트리
•
최소 신장 트리
◦
가중치 그래프 𝑮의 신장트리 중 총 가중치가 가장 작은 신장 트리
function Dijkstra(G, w, s, t)
// 초기화
for each vertex v in V[G] do
d[v] ← ∞
prev[v] ← undefined
end for
d[s] ← 0
// 아직 방문하지 않은 정점들의 집합
Q ← V[G]
// 메인 루프
while Q ≠ ∅ do
// Q에서 d[u]가 최소인 정점 u 선택
u ← extract_min(Q, d)
// 목표 정점에 도달했으면 종료
if u = t then
break
end if
// u 제거
Q ← Q − {u}
// u의 인접 정점들에 대해 최단 경로 갱신
for each vertex v in (neighbors(u) ∩ Q) do
if d[v] > d[u] + w(u, v) then
d[v] ← d[u] + w(u, v)
prev[v] ← u
end if
end for
end while
return (d, prev)
end function
JavaScript
복사
예제