이산 수학 - 14 그래프의 활용

연결선에 가중치가 부여된 가중 그래프

- 이동하는데 걸리는 시간

- 어느 경로를 선택해야 목적지에 빠르게 도착할까?

-> 최단 경로 문제

 

 

네비게이션 시스템은 복잡한 지도와 그래프를 사용.

 

다익스트라 알고리즘

- 최단 경로 문제를 해결할 수 있는 알고리즘

 

 

특수 그래프

1. 오일러 그래프

2. 해밀턴 그래프

 

 

오일러 그래프

- 오일러 경로 : 그래프의 모든 연결선을 한번씩만 지나는 경로

- 오일러 순환 : 시작노드와 끝노드가 같은 오일러

- 오일러 그래프 : 오일러 순환을 가지는 그래프

 

 

 

오일러 그래프에 대한 정의

- 연결 그래프의 모든 노드들이 짝수 노드이면 오일러 그래프 

 -> 노드의 차수 : 노드에 근접하는 연결선 개수

 -> 짝수 노드 : 차수가 짝수인 노드

- 연결 그래프의 노드 중 홀수 노드의 개수가 0 또는 2이면 오일러 경로를 가짐

 

오일러 그래프와 한붓그리기

- 한붓 그리기 : 그래프에서 연필을 떼지 않고 모든 변을 오직 한 번만 지나는 것

- 한붓 그리기가 가능하려면 연결 그래프의 홀수 노드의 개수가 0 또는 2여야 함

 

쾨니히스베르크 다리 문제

- 오일러는 쾨니히스베르크 다리 문제를 (다중 그래프에서의) 오일러 순환의 존재 여부 문제로 변환하여 해결함

- 오일러 순환이 존재하지 않음 -> 쾨니히스베르크 다리들을 모두 한번씩만 건너서 출발한 곳으로 다시 돌아올 수 없음

 

해밀턴 그래프

- 해밀턴 경로 : 시작 노드와 끝 노드 빼고 모든 노드를 한번씩만 지나는 경로

- 해밀턴 순환 : 시작노드와 끝노드가 같은 해밀턴 경로

- 해밀턴 그래프 : 해밀턴 순환을 가지는 그래프

 

 

NP-complete

- 어떤 그래프에 해밀턴 경로가 존재하는지 여부를 결정하는 문제를 NP-complete 문제라 함.

- 어떤 그래프가 해밀턴 그래프인지 여부를 구하는 문제

 

 

윌리엄 로언 해밀턴

- 아일랜드 수학자, 물리학자, 천문학자

- 사원수를 발견할 인물

- 광학, 동역학 및 대수학의 발전에 큰 공헌을 함

 

 

순회 판매원 문제

- 방문할 도시들과 이들 도시 사이의 거리가 주어질때, 순회 판매원이 어떤 특정 도시를 출발하여 어떠한 도시도 두 번 방문함 없이 모든 도시를 거쳐 처음 출발한 도시로 돌아오는 경우의 '최소 경로'를 찾는 문제

- 일반적인 해결 알고리즘이 존재하지 않음

- 도시가 많아질 수록 경우의 수가 크게 늘어남 -> NP-hard 문제(NP-complete 보다 어려운 문제)

 

최단 경로 문제

- 최단 경로 : 가중 그래프에서 가장 짧은 거리의 경로

 

 

다익스트라 알고리즘

- 가중치가 모드 음수값이 아닌 방향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로를 찾아주는 알고리즘

ex) 1에서 2까지 최단 거리는? 1에서 3까지 최단 거리는? 1에서 4까지 최단 거리는?

 

 

에츠허르 다익스트라

- 네덜란드 출신 컴퓨터 과학자

- 전산학이 정립되지 않은 시절 전산학의 여러 분야에 기여함

- 다익스트라 알고리즘을 개발하여 최단 경로 문제에 대한 학문적 연구를 시작

- GOTO문 사용하지 말것을 주장

- 세마포어에 대한 연구를 처음 시작함

- 1972년 튜링상 수상

 

다익스트라 알고리즘의 Pseudo-code

void Dijkstra()
{
	S = {1};
    for (i=2; i <= n; i = i + 1)
    {
    	D[i] = C[1, i];
        // D[i]는 노드 i에서 노드 j까지의 최단 거리
        // C[i, j]는 노드 i에서 노드 j까지의 거리
        // 노드 i에서 노드 j로 가는 연결선이 없다면 C[i, j] = inf
    }
    
    for (i = 1; i <= n - 1; i = i + 1)
    {
    	V - S에 있는 노드 중에서 D[w]가 최소인 노드 w를 선택;
        w를 S에 추가;
        V - S에 있는 각 노드 v에 대해 D[v] = min(D[v], D[w] + C[w, v]);
    }
}

 

다익스트라 알고리즘의 적용 예시

- 1에서 2까지 최단거리 = 10

- 1에서 3까지 최단거리 = 60

- 1에서 4까지 최단거리 = 50

- 1에서 5까지 최단거리 = 30

 

 

 

그래프의 탐색

1. 탐색 정의

2. 깊이 우선 탐색

3. 너비 우선 탐색

 

 

 

 

그래프 탐색

- 그래프의 모든 노드를 체계적으로 방문하는 방법

ex) 깊이 우선 탐색, 너비 우선 탐색

 

메모리 구조

- 스택

- 큐

 

 

스택

- LIFO(Last In First Out) 구조를 가지는 메모리 한 형태

큐

- FIFO(First In First Out) 구조를 가지는 메모리 한 형태

 

 

깊이 우선 탐색 Depth First Search, DFS 과정

1. 임의의 시작 노드 v를 선택하고 탐색

2. v에 인접한 노드 중

  -> 방문하지 않는 노드 w가 있으면 v를 스택에 push하고 w를 방문, 그리고 w를 v로 설정한 뒤 2를 반복

  -> 방문하지 않은 노드가 없으면 스택을 pop하여 받은 가장 마지막 방문 노드를 v로 설정한 뒤 2를 방문

3. 스택이 공백이 될 떄 까지 2를 반복

 

 

깊이 우선 탐색 과정 예

- A를 우선 탐색 -> 스택

- B를 탐색 -> 스택 A

- D를 탐색 -> 스택  A B

- G를 탐색 -> 스택 A B D

- F를 탐색 -> 스택 A B D G

- F에 인접한 노드가 없음 -> G를 Pop

- E를 탐색 -> 스택 A B D

- C를 탐색 -> 스택 A B D E

- C에 인접한 탐색할 노드 없음 -> E Pop -> 스택 A B D

- D에서 탐색할 노드 없음 -> D pop -> 스택 A B

- B에서 탐색할 노드 없음 -> B pop -> 스택 A

- A에서 탐색할 노드 없음 -> A Pop -> 스택 

 

 

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

1. 인의의 시작노드 v를 선택하고 이를 탐색한다.

2. v에 인접한 노드 중

 - 방문하지 않는 노드를 차례로 방문하여 큐에 enQueue 한다.

 - 방문하지 않은 인접한 노드가 없으면 큐에서 deQueue한 노드를 가지고 2를 계속 반복

3. 큐가 공백이 될 때 까지 2를 반복한다.

 

 

너비 우선 탐색 과정 예

1. A를 우선 탐색 . v = A

2. B를 탐색 -> enQueue B -> Queue B

3. C를 탐색 -> enQueue C -> Queue B C

4. v에 더이상 인접한 노드 없음 -> deQueue B -> v = B -> Queue C

5. D를 탐색 -> enQueue D -> Queue C D

6. E를 탐색 -> enQueue E -> Queue C D E

7. v(B)에 인접한 노드 없음 -> deQueue C -> v = C -> queue D E

8. v(C)에 인접한 노드 없음 -> deQueue D -> v = D -> queue E

9. G를 탐색 -> enQueue G -> Queue E G

10. v(D)에 인접한 노드 없음 -> deQueue E -> v = E -> queue G

11. F 탐색 -> enQueue G -> Queue G F

12. v(E)에 인접한 노드 없음 -> deQueue G -> v = G -> queue F

13. v(G)에 인접한 노드 없음 -> deQuque F -> V = F -> queue 

14. 종료