[이산수학] 그래프

 

그래프 용어 정리 

 

그래프는 꼭지점(vertex)과 변(edge)의 집합 

G = (V, E)

loop = 동일한 꼭지점을 연결하는 집합 

동형 isomorphic: 꼭지점과 변의 이름을 제외하고 모두 동일한 그래프 

 

방향 그래프 directed graph: 변이 뱡향을 가지고 있음

무향 그래프 undirected graph: 변이 방향을 가지고 있지 않음 (꼭지점들 사이에 전후 관계가 없음) 

 

단순 그래프 simple graph: 루프나 병렬 변을 가지지 않는 무향 그래프 

 

부분 그래프 subgraph: H의 모든 꼭지점이 G의 꼭지점이고, H의 모든 변이 G의 변인 경우 H는 G의 부분 그래프

V' ⊆ V, E' ⊆ E 

신장 부분 그래프 spanning subgraph: 부분 그래프 중 H와 G의 꼭지점이 완전히 일치하는 경우 V' = V, E' ⊆ E

 

그래프의 총 차수는 변의 수의 2배 (총 차수는 언제나 짝수) 

 

워크: v0에서 vk까지의 꼭지점과 변들을 순서대로 나열한 것 

v0: 시작점

vk: 종점

k: W의 길이 

시작점과 종점이 같은 워크는 닫혀 있다 

 

트레일: 변들이 모두 서로 다른 워크 (병렬 변이 존재하지 않음)

경로 path: 꼭지점이 모두 다른 트레일 

 

path ⊂ trail ⊂ walk 

 

사이클: 닫힌 경로 (꼭지점이 모두 다르고, 시작점과 종점이 동일하다) 

k-사이클: 길이가 k인 사이클 

 

연결성분: 서로 연결되고 다른 집합과 겹치지 않는 꼭지점의 집합 

연결 그래프: 하나의 연결 성분으로만 이루어져 있는 그래프 (그래프 안의 임의의 꼭지점 v, u간에 경로가 존재)

 

완전 그래프 complete graph: 그래프에 속한 모든 꼭지점이 다른 꼭지점과 인접

Kn: n개의 꼭지점을 가진 완전 그래프 

 

이분 그래프 bipartite graph: 연결 성분이 V1, V2로 분할되어 있고 모든 변들이 V1의 꼭지점과 V2의 꼭지점을 인접

(그래프의 꼭지점을 두 색으로 칠해보면 각 변의 양 끝이 서로 다른 색!)

+ 이분 그래프의 내부에는 홀수 길이의 사이클이 존재하지 않음 

 

완전 이분 그래프 complete bipartite graph: 이분 그래프 중 V1과 V2의 모든 꼭지점이 인접되어 있을 때 

 

정규 그래프 regular graph: 모든 꼭지점들이 동일한 차수를 가짐 

 

 

그래프의 표현 

 

발생행렬 incidence matrix: 행렬의 행은 꼭지점, 열은 변으로 꼭지점과 변의 연결 관계 표현 (인접시 1) 

크기가 |V| x |E|인 부울 행렬 

 

인접행렬 adjacency matrix: 행과 열이 모두 꼭지점으로 인접 관계 표현

|V| x |V| 크기의 정방 행렬 

무향 그래프의 인접 행렬은 대칭 행렬 

 

인접 리스트: 각 꼭지점에 인접하는 리스트들을 차례로 연결 리스트로 표현 

 

 

그래프 탐색

 

평면 그래프 planar graph: 그래프의 모든 변을 서로 교차하지 않게 그릴 수 있음 

 

오일러 공식 Euler's Formula

v - e + f = 2 (v = 꼭지점, e = 변, f = 면) 

 

오일러 트레일: 그래프의 모든 변들을 한 번씩만 지나는 트레일 (=한붓그리기) 

오일러 투어: 시작점과 종점이 동일한 오일러 트레일 

오일러 그래프: 오일러 투어를 갖는 그래프 

연결된 그래프이면서 모든 꼭지점의 차수가 짝수라면 오일러 투어를 가진다. 

 

해밀턴 경로: 모든 꼭지점을 한 번씩만 지나는 경로

해밀턴 사이클: 시작점과 종점이 같은 해밀턴 경로 

 

 

 

 

 

 

출처: 이산수학(손진곤, 2021)