이산수학 7. 그래프

 그래프(graph): G = (V, E)는 유한한 개수의 정점(vertex) 또는 노드(node) 집합 V와 연결선(edge) 또는 에지라고 불리는 정점들의 쌍들의 집합 E로 이루어진다

방향이 있는 그래프(direct graph or digraph)와 방향이 없는 그래프(undirected graph)가 있음

경로(path): 정점들의 열

사이클(cycle): 출발점과 끝점이 같을 때

* 아크(arc): 정점들의 순서화된 쌍

 

v -> w라고 할 때 v는 w의 선행자, w를 v의 후속자라고 한다

 

그래프의 용어

단순 그래프(simple graph): 정점 사이에 많아도 하나의 연결선으로 이루어진, 자기 자신으로서의 연결선이 없는 그래프

멀티 그래프(multi graph): 한 쌍의 꼭지점 사이의 연결선의 개수의 제한이 없는 그래프

차수: v에 인접하는 연결선의 개수

부분 그래프, 생성 부분 그래프: V = V' 이고 E' ⊂ E 이면 생성 부분 그래프

연결 그래프(connected graph): 그래프의 모든 정점들이 연결되어 있는 그래프

강한 연결 그래프(strongly connected graph): a에서 b로의 경로와 b에서 a로의 경로들이 존재하는 그래프

연결 요소(connectvity component): 그래프에서 모든 정점들이 연결되어 있는 부분, 연결수(connectivity number)란 그래프G에서 연결 요소의 개수

 

위상기하학(Topological Geometry): 위상적인 형태에만 중점을 두는 것

 

* 경로: 정점들의 열

* 단순 경로: 경로가 같은 연결선을 두 번 포함하지 않는 경로

* 기본 경로: 어떤 정점들도 두 번 방문하지 않는 경로

* 사이클, 순회: 경로에서 종점과 시점이 일치하는 경우

* 단순 사이클: 경로 상에서 같은 정점을 두 번 이상 방문하지 않는 사이클

* 기본 사이클: 시작 정점을 제외하고 어떤 정점도 두 번 이상 방문하지 않는 사이클

 

7.3 그래프의 표현 방법

인접 행렬(adjacency matrix)

그래프 G = (V, E)에서 v를 n으로 정방행렬을 그리는 것

 

인접 리스트(adjacency list)

각 정점에 대해 포인터가 주어지고 그 점으로부터 연결된 정점들을 차례로 연결 리스트(linked list)로 표시한 것인데 같은 리스트 내에서는 순서에 관계가 없다

 

7.4 특수 형태의 그래프

오일러 경로(Eulerian path): 그래프에서 각 연결선을 단 한 번씩만 통과하는 경로

오일러 순회(Eulerian circuit): 그래프에서 꼭지점은 여러 번 지날 수 있지만, 연결선은 단 한 번씩만 통과하는 순회

차수의 합은 연결선의 합의 2배와 같다

어떤 그래프 G가 오일러 경로를 가지기 위한 필요충분조건: G가 연결그래프이고 홀수 차수의 개수가 0 또는 2인 경우

 

한붓그리기(traversable): 붓을 떼지않고 모든 변을 오직 한 번만 지나가는 것 연결된 그래프에서 한붓그리기가 가능하려면 시작점과 끝점을 제외한 모든 꼭지점의 차수가 짝수어야 한다

(오일러경로와 같다)

 

해밀턴 경로(Hamiltonian path): 그래프에서 모든 꼭지점을 오직 한 번씩만 지나지만 시작점으로 돌아오지 않는 경로

해밀턴 순회(Hamitonian circuit): 그래프에서 모든 꼭지점들을 오직 한 번씩만 지나는 순회

 

가중 그래프(weight graph): 각 연결선에 0보다 큰 수가 할당되었을 때 이 값을 가중값(weight)이라고 함

동형 그래프(Isomorphic graph): 두 그래프가 구조적으로 동일하다

모양은 다를 수 있지만 연결 방식(꼭짓점과 간선의 관계)이 같다

평면 그래프: 평면상에서 어떠한 연결선들도 서로 교차할 수 없도록 그려진 하나의 그래프

완전 그래프: 각 꼭지점이 다른 모든 꼭지점들과 연결되는 그래프 / 연결선의 개수: n(n-1)/2

정규 그래프: 모든 꼭지점의 차수가 k이면 k차 정규 그래프다

이분 그래프: 꼭짓점 집합을 두 개의 부분 집합으로 나눌 수 있는 그래프

* 완전 이분 그래프: X 내의 모든 정점들과 Y 내의 모든 정점들 사이에 연결선이 존재하면

 

방향 비사이클 그래프(Directed Actclic Graph: DAG): 사이클이 없는 방향 그래프

 

7.5 그래프의 응용

최단 경로 문제(shortest path problem): 가장 짧은 거리의 경로를 찾는 문제

다익스트라 알고리즘(Dijkstra algorithm): 시작 정점으로부터 모든 정점까지의 최단 거리를 계산하는 알고리즘

 

해밀턴 순회의 응용: 순회판매원 문제

 

7.6 그래프의 탐색

깊이 우선 탐색(Depth First Search: DFS)

1. 먼저 시작점 v부터 방문한다

2. v에 인접한 정점 중에서 방문하지 않은 정점 w를 방문하고 다시 w로부터 탐색을 시작한다

3. 다음 u를 방문하고 u에 인접한 모든 정점들을 이미 방문한 경우에는 그전에 방문한 정점으로 되돌아가서 반복한다

재귀 알고리즘이 좋음

 

너비 우선 탐색(Breadth First Search: BFS)

처음에 방문한 정점과 인접한 정점들을 차례로 방문한다는 점에서 깊이 우선 탐색과 차이가 있음

1. 먼저 시작점 v부터 방문한다

2. v에 인접한 모든 정점들을 차례로 방문한다

3. 방문할 지점이 없으면 맨 처음 방문한 정점과 인접한 정점들을 차례로 방문하고 그 다음 방문한 정점의 인접한 정점들을 방문하고 이걸 반복한다

 

7.7 그래프와 색칠 문제

색칠 문제: 그래프 G에 대해 인접한 어느 영역도 같은 색이 안되도록 각 정점에 색을 칠하는 문제

G를 색칠하는 데 필요한 최소한의 색의 수를 x(G)라고 하고 G의 색칠 수(chromatic number)라고 한다

모든 평면 그래프는 네가지 색으로 색칠이 가능하다 이를 4색문제라고 함

이분 그래프이면 두 가지 색으로 칠할 수 있고 모든 순환은 짝수의 길이를 가진다.