제 7 장 네트워크 이론과 응용

기본정의와 주로 다루는 문제들 교점, 호, 경로, 사슬 주로 다루는 네트워크 문제들 Shortest path problem Minimal spanning tree problem Maximum flow problem

교점, 호, 경로, 사슬 경로면서 사슬임 경로와 순환로는 방향성 고려 사슬은 방향성 고려 경로지만 사슬은 아님

7.2 최단경로문제 임의의 교점에서 다른 교점까지 가는 가장 짧은 길을 찾는 문제 해법으로는 다익스트라해법 (Dijkstra’s algorithm) 이 대표적이다. 기본가정과 기호정의

다익스트라 해법 단계1: 시작교점에 영구표지 을 붙인다. 시작교점과 직접 연결된 교점들에는 임시표지 , 단계1: 시작교점에 영구표지 을 붙인다. 시작교점과 직접 연결된 교점들에는 임시표지 , 그렇지 않은 교점들에는 임시표지 를 붙인다. 단계2: 남은 모든 임시표지들 중, 가장 최근에 영구표지가 붙여진 교점과 직접 연결된 각 교점들을 대상으로 다음 (i)과 (ii)를 수행한다. 만약 그런 교점이 없으면 단계3으로 간다. (i) 영구표지로 부터의 거리값 계산 (ii) (i) 의 계산값과 기존 임시표지 값 중 작은 값을 새로운 임시표지값으로 한다. 단계3: 남아있는 모든 임시표지값 중 가장 작은 값을 택하여 영구표지로 만든다. 교점 t 가 영구표지화 되었으면 멈추고 그렇지 않으면 단계2로 간다.

예제 7.2 Dijkstra’s algorithm 단계(1)-(2) 6 4 1 S 5 t 3

예제 7.2 Dijkstra’s algorithm 단계(3)-(4) 6 3 4 S 1 7 5 t 3

예제 7.2 Dijkstra’s algorithm 단계(5)-(6) 1 6 2 3 4 S 1 2 7 5 t 3 기존의 값

예제 7.2 Dijkstra’s algorithm 단계(7)-(8) 1 2 6 2 4 S 1 2 5 t 3

예제 7.2 Dijkstra’s algorithm 단계(9)-(10) 6 2 4 S 1 4 5 t 3

예제 7.2 Dijkstra’s algorithm 단계(11)-(12) 2019-05-03 예제 7.2 Dijkstra’s algorithm 단계(11)-(12) 2 6 4 S 1 2 4 5 t 3

예제 7.2 Dijkstra’s algorithm 단계(13) 6 4 S 1 t 5 3

예제 7.2 Dijkstra’s algorithm 단계(14)-(16) 3 4 S 1 2 4 5 t 3

네트워크 상의 모든 교점을 포함하는 나무를 최소비용으로 구성 7.3 최소걸침나무 문제 네트워크 상의 모든 교점을 포함하는 나무를 최소비용으로 구성 나무란 (방향성 없는) 순환로가 없이 연결된 네트워크 좌측은 걸침나무, 우측은 순환로가 존재하므로 나무가 아님

예제 7.4 Minimal spanning tree algorithm (1) 5 2 7 3 1 1 3 7 4 6 4

예제 7.4 Minimal spanning tree algorithm (2) 5 2 7 5 4 7 3 1 3 7 4 6 4

예제 7.4 Minimal spanning tree algorithm (3) 5 2 7 5 2 5 7 3 1 1 7 4 6 4

예제 7.4 Minimal spanning tree algorithm (4) 5 2 5 2 5 7 3 1 7 4 6 4

예제 7.4 Minimal spanning tree algorithm (5) 2 5 2 5 7 3 1 7 4 6 4

예제 7.4 Minimal spanning tree algorithm (6) 5 2 5 7 3 1 7 6 4

예제 7.4 Minimal spanning tree algorithm (7) 5 2 5 2 2 1 7 3 1 3 1 6 4 총 길이=2+2+1+3+1+5=14, 이 값이 걸침나무를 구성하는 나무중 최소인 나무의 길이임

7.4 최대 유량 문제 표지에 관하여 네트워크상의 시점에서 종점으로 최대유량을 흘려보내는 문제 임의의 노드를 기준으로 변화시킬 수 있는 양과 관련된 노드번호를 표시한 것. 순방향과 역방향 표지가 있다. 순방향은 유량증가 역방향은 유량감소

순방향 표지 기존의 표지이며 (증량가능량, 이전노드 번호) (6, 1) 2 3 [0, 4] 현재 유량과 용량 Min(6, 4-0) 위와 같은 경우는 교점 3에 (4, 2) 의 표지를 붙일 수 있다. 즉, 교점 2에서 교점 3으로 4 의 유량을 증량할 수 있다는 표시를 할 수 있다.

순방향 표지 (계속) 이고 단 인 경우 현재 교점이 음의 증량값 (qi 가 음) 인 경우에도 표지를 붙일 수 있다. 일반적으로 j 현재 교점이 음의 증량값 (qi 가 음) 인 경우에도 표지를 붙일 수 있다. 순방향 표지 (계속) 일반적으로 라는 표지를 붙일 수 있다. 이고 단 인 경우 이 아닌 것에 注意

예제 7.7 최대유량문제 S 2 3 1 4 [0, 2] [0, 1] [0, 3] [0, 4]

증량가능경로 탐색및 유량증가 [0, 4] [0, 2] [0, 2] [0, 3] [0, 3] [0, 1] [0, 2] (3, S) (2, S) [0, 4] 1 2 [0, 2] [0, 2] [0, 3] [0, 3] S 4 [0, 1] [0, 2] [0, 1] 3 (1, S)

증량가능경로 탐색및 유량증가 (3, S) (2, S) [0, 4] [0, 2] [0, 2] [0, 3] [0, 3] 1 2 [0, 2] [0, 2] [0, 3] [0, 3] S t [0, 1] (2, 1) [0, 2] [0, 1] 3 (1, S)

증량가능경로 탐색및 유량증가 로 2 를 증량하였다. 더 이상의 증량이 불가능할 때까지 반복 역방향 표지에 주의한다.

예제 7.8 역방향 표지를 붙이는 경우 현재의 상태에서는 더 이상의 증량이 불가능해 보인다. 그러나 … [5, 5] 1 [5, 5] [2, 4] [3, 3] t S 2 [3, 3] [5, 5] [2, 4] 3 현재 위로 흐르는 유량중 2 만큼을 변경시키면 2 만큼이 증량가능하다.

예제 7.8 역방향 표지를 붙이는 경우 S 에서 탐색을 시작하여 우선 교점 1 에(2, S) 의 표지를 붙였다. (2, S) [5, 5] [2, 4] [3, 3] t S 2 [3, 3] [5, 5] [2, 4] 3

예제 7.8 역방향 표지를 붙이는 경우 교점 3에는 표지를 붙일 수 없다. 현재의 교점이 교점 1 로 변한 후 교점 2에 역방향 표지를 붙일 수 있다. 예제 7.8 역방향 표지를 붙이는 경우 (2, S) 1 [5, 5] [2, 4] [3, 3] t S 2 (-2, 1) [3, 3] [5, 5] [2, 4] 3

예제 7.8 역방향 표지를 붙이는 경우 교점 3에 역방향 표지 (-2, 2) 를 붙인다. (2, S) [2, 4] [5, 5] 1 [2, 4] [5, 5] [3, 3] t S 2 (-2, 1) [3, 3] [5, 5] [2, 4] 3 (-2, 2)

예제 7.8 역방향 표지를 붙이는 경우 교점 t 에 (2, 3) 의 표지를 붙이면 증량경로가 완성된다. (2, S) 1 [2, 4] [5, 5] [3, 3] t S 2 (-2, 1) (2, 3) [3, 3] [5, 5] [2, 4] 3 (-2, 2)

예제 7.8 역방향 표지를 붙이는 경우 이전의 7에서 9로 2 의 증량이 이루어 짐 (2, S) (-2, 1) (2, 3) 2 →4 5 →5 3 →1 t S 2 (-2, 1) (2, 3) 3 →1 5 →5 2 →4 3 (-2, 2)

현재교점이 2번인 경우, 흘러들어오는 유량이 있으면 역방향 표지의 가능성이 있다. 기존의 표지이며 (여기까지 증량가능량, 이전노드 번호) 역방향 표지 (-2, 2) (6, 1) 흐르는 방향 2 3 [2, 4] 유량과 용량 Min(6, 2) 위와 같은 경우는 교점 3에 (-2, 2) 의 표지를 붙일 수 있다. 즉, 교점 3에서 교점 2 방향으로 현재 흐르고 있는 2 의 유량을 감량할 수 있다는 표시.

역방향 표지 (계속) 단 이고 인 경우 현재 교점이 음의 증량값 (qi 가 음) 인 경우에도 표지를 붙일 수 있다. 현재교점이 i 일때 인접교점 j 에 역방향표지를 붙이는 경우 i j 흐르는 방향 라는 표지를 붙일 수 있다. 단 이고 이 아닌 것에 注意 인 경우

표지 붙이기 연습 현재교점이 6 일때 인접교점들에 표지를 붙이는 문제 4 4 7 7 6 6 5 5 8 8

표지 붙이기 연습 현재교점이 6 일때 인접교점들에 표지를 붙이는 문제 4 4 7 7 6 6 5 5 8 8

예제 7.9 Ford and Fulkerson algorithm [1, 4] 1 2 [1, 2] [2, 2] [2, 3] S t [1, 1] [1, 2] [0, 1] 3

예제 7.9 Ford and Fulkerson algorithm [1, 4] 1 2 [1, 2] [2, 2] [2, 3] S t [1, 1] [1, 2] [0, 1] 3 (1, S)

예제 7.9 Ford and Fulkerson algorithm 교점 2에는 이미 표지가 있으므로 순방향표지 불가능 예제 7.9 Ford and Fulkerson algorithm (1, S) (1, S) [1, 4] 1 2 [1, 2] [2, 2] [2, 3] S t [1, 1] (1, 3) [1, 2] [0, 1] 3 (1, S)

예제 7.9 Ford and Fulkerson algorithm [1, 4] 1 2 [1, 2] [2, 2] [2, 3] S t [1, 1] [2, 2] [1, 1] 3

예제 7.9 Ford and Fulkerson algorithm [1, 4] 1 2 [1, 2] [2, 2] 유량갱신후 다시 1 과 2 에 (1,S) 의 표지설치했으나 더 이상 유량증가가 불가능하다. 따라서 현재의 유량이 문제의 최적해이다. [2, 3] S t [1, 1] [2, 2] [1, 1] 3