제 6 장 그래프

그래프 추상 데이타 타입(1) 개요 Koenigsberg 다리 문제 차수(degree) : 정점에 연결된 간선의 수 오일러 행로(Eulerian walk) .. g c C d A D e D A C B c a d b e g f Kneiphof B f a b (a) Koenigsberg의 Pregal강의 일부 (b) 오일러의 그래프

그래프 추상 데이타 타입(2) 정의 그래프 G : 2개의 집합 V와 E로 구성 무방향그래프(undirected graph) V : 공집합이 아닌 정점(vertex)의 유한집합 E : 간선(edges)이라고 하는 정점 쌍들의 집합 표기 : G=(V,E) 무방향그래프(undirected graph) 간선을 나타내는 정점의 쌍에 순서 없음 방향 그래프(directed graph) 방향을 가지는 정점의 쌍 <u,v>로 표시 (u는 꼬리(tail), v는 머리(head)) <v,u>와 <u,v>는 서로 다른 간선

그래프 추상 데이타 타입(3) 예제 그래프 V(G1)={0,1,2,3} E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} V(G2)={0,1,2,3,4,5,6) E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)} V(G3)={0,1,2} E(G3)={<0,1>,<1,0>,<1,2>} 1 2 1 2 1 3 3 4 5 6 2 G1 G2 G3

그래프 추상 데이타 타입(4) 정의 그래프의 제한 사항 자기 간선(self edge) 또는 자기 루프(self loop) 없음 동일 간선의 중복 없음(다중그래프(multigraph)는 이 제한이 없음 1 1 3 2 2 자기 간선을 가진 그래프 다중 그래프 완전 그래프(complete graph) : n개의 정점과 n(n-1)/2개의 간선을 가진 그래프 (u,v)가 E(G)의 한 간선이라면 u와 v는 인접(adjacent)한다 간선 (u,v)는 정점 u와 v에 부속(incident)된다 그래프 G의 부분그래프(subgraph) : V(G')  V(G) 이고 E(G')  E(G)인 그래프 G'

그래프 추상 데이타 타입(5) 정점 u로부터 정점 v까지의 경로(path) 경로의 길이(length) 그래프 G에서 (u,i1), (i1,i2), ..., (ik,v)를 E(G)에 속한 간선들이라 할 때, 정점열 u, i1, i2, ..., ik, v를 말함 경로의 길이(length) 경로상에 있는 간선의 수 단순 경로(simple path) 경로상에서 처음과 마지막을 제외한 모든 정점들이 서로 다름 단순 방향 경로(simple directed path) 사이클(cycle) 처음과 마지막 정점이 같은 단순 경로

그래프 추상 데이타 타입(6) G1 G1의 서브그래프 G3 G3의 서브그래프 1 2 3 1 2 3 2 1 (i) (ii) 3 2 1 G1 1 2 3 (i) (ii) (iii) (iv) G1의 서브그래프 2 1 G3 1 2 (i) (ii) (iii) (iv) G3의 서브그래프

그래프 추상 데이타 타입(7) 연결 요소(connected component) 강력 연결(strongly connected) :최대 연결 부분 그래프(maximal connected subgraph) 강력 연결(strongly connected) :방향그래프에서 V(G)에 속한 서로 다른 두 정점 u, v의 모든 쌍에 대해서, u에서 v로, 또한 v에서 u로의 방향 경로(directed path)가 존재 강력 연결 요소(strongly connected component) :강하게 연결된 최대 부분그래프 두 개의 연결요소를 갖는 그래프

그래프 추상 데이타 타입(8) 차수(degree) : 정점에 부속한 간선들의 수 진입차수(in-degree) G3의 강력 연결요소 1 2 차수(degree) : 정점에 부속한 간선들의 수 진입차수(in-degree) 임의의 정점 v가 머리가 되는 간선들의 수 진출차수(out-degree) v가 꼬리가 되는 간선들의 수 간선의 수 다이그래프(digraph) : 방향 그래프 n-1 e =(ådi)/2 i (n개의 정점과 e개의 간선을 가진 그래프)

그래프 표현법(1) 인접행렬 (Adjacency Matrix) G=(V,E)는 정점의 수가 n(n≥1)인 그래프 간선 (vi, vj)E(G)  a[i][j]=1 간선 (vi, vj)E(G)  a[i][j]=0 필요 공간 : n2 비트 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 2 3 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 2 3 0 1 2 0 1 0 1 0 1 0 0 0 1 2 G1 의 인접행렬 G3 의 인접행렬 G4 의 인접행렬 n-1 ∑a[i][j] 무방향 그래프: 어떤 정점 i의 차수는 그 행의 합 : 방향 그래프: 행의 합은 진출차수, 열의 합은 진입차수 인접행렬의 수행 시간 : 최소한 O (n2) 희소 그래프(sparse graph) : O (e+n) J=0

그래프 표현법(2) 인접리스트 (Adjacency Lists) 인접행렬의 n행들을 n개의 연결리스트로 표현 data와 link 필드 C++ 선언문 n개의 정점, e개의 간선의 무방향 그래프 n개의 헤드노드, 2e개의 리스트 노드가 필요 방향그래프 : e개의 리스트 노드 역인접리스트(inverse adjacency lists) 리스트가 표현하는 정점에 인접한 각 정점에 대해 하나의 노드를 둠 Chain<int> *adjList; LinkedGraph(const int vertice=0) ; n(vertices), e(0) {adjList=new Chain<int>[n];}

인접리스트(1) G1 인접 리스트 G3 인접 리스트 G4 인접 리스트 [0] [1] [2] [3] [0] [1] [2] [0] adjLists data link [0] [1] [2] [3] 3 1 2 2 3 1 3 1 2 G1 인접 리스트 adjLists [0] [1] [2] 1 2 G3 인접 리스트 adjLists [0] [1] [2] [3] 2 1 3 3 1 2 [4] [5] [6] [7] 5 6 4 5 7 6 G4 인접 리스트 (

인접리스트(2) int nodes[n + 2*e +1]; 그래프 G4의 순차 표현 G3의 역인접리스트 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 그래프 G4의 순차 표현 G3의 역인접리스트

인접리스트(3) 헤더노드 1 2 1 1 1 1 2 2 그래프 G3에 대한 직교 리스트 표현

인접다중리스트 (Adjacency Multilists) 간선 (u,v)는 두 개의 엔트리로 표현 : u를 위한 리스트, v를 위한 리스트에 나타남 새로운 노드 구조 m vertex 1 vertex 2 list 1 list 2 1 N1 N3 N0 edge (0,1) 2 N2 edge (0,2) 3 N4 edge (0,3) N5 edge (1,2) edge (1,3) edge (2,3) adjNodes [0] [1] [2] [3] The lists are vertex 0: N0 -> N1 -> N2 vertex 1: N0 -> N3 -> N4 vertex 2: N1 -> N3 -> N5 vertex 3: N2 -> N4 -> N5 G1에 대한 인접 다중리스트

가중치 간선(Weighted Edges) 그래프의 간선에 가중치(weights) 부여 인접행렬 : 행렬 엔트리에 a[i][j]의 가중치 정보 저장 인접리스트 : 노드 구조에 weight 필드를 추가 네트워크(network) : 가중치 간선을 가진 그래프

C++ 그래프 클래스 그래프 클래스에 대해 파생 가능 계층 Graph Matrix WDigraph LinkedWDigraph LinkedDigraph MatrixWGraph MatrixDigraph LinkedWGraph LinkedGraph MatrixGraph 그래프 클래스에 대해 파생 가능 계층

그래프의 기본 연산 깊이-우선 탐색(DFS; Depth-First Search) (1) 출발 정점 v를 방문 (2) v에 인접하고 방문하지 않은 한 정점 w를 선택 (3) w를 시작점으로 다시 깊이 우선 탐색 시작 (4) 모든 인접 정점을 방문한 정점 u에 도달하면, 최근에 방문한 정점 중 아직 방문을 안한 정점 w와 인접하고 있는 정점으로 되돌아감 (5) 정점 w로부터 다시 깊이 우선 탐색 시작 (6) 방문을 한 정점들로부터 방문하지 않은 정점으로 더 이상 갈 수 없을 때 종료

깊이 우선 탐색(1) 예제 6.1 0, 1, 3, 7, 4, 5, 2, 6 순으로 방문 [0] [1] [2] [3] [4] 1 2 3 4 5 6 7 adjLists ( a) [0] [1] [2] [3] [4] [5] [6] [7] 1 2 3 4 5 6 그래프 G와 그 인접리스트 1 7 1 7 2 7 2 7 3 4 5 6 (b)

깊이 우선 탐색(2) DFS의 분석 탐색을 끝내는 시간 O (e) v에 인접한 모든 정점들을 찾는데 O (n)의 시간

너비 우선 탐색(1) 너비 우선 탐색(BFS; Breadth-First Search) 예제 6.2 시작 정점 v를 방문 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문 예제 6.2 0, 1, 2, 3, 4, 5, 6, 7 순으로 방문 1 2 3 4 5 6 7

너비 우선 탐색(2) BFS의 분석 전체 시간 O(n2) 인접 리스트 표현 : 전체 비용 O(e) Virtual void Graph::BFS(int v) // 너비-우선 탐색은 정점 v에서부터 시작한다. // v 방문시 visited[i]는 TRUE로 설정된다. 이 함수는 큐를 이용한다. { visited = new bool[n]; . fill(visited, visited+n, false); visited[v] = true; Queue<int> q; q.push(v); while(!q.IsEmpty()) { v = *q.Front(); q.Pop(); for(v에 인접한 모든 정점 w에 대해) // 실제 코드는 반복자를 사용 if(!visited[w]) { q.Push(w); visited[w] = TRUE; } } // while 루프의 끝 delete [] visited; BFS의 분석 전체 시간 O(n2) 인접 리스트 표현 : 전체 비용 O(e)

연결요소 연결요소(connected component) Component의 분석 방문하지 않은 정점 v에 대해 DFS(v) 또는 BFS(v)를 반복 호출로 구함 Virtual void Graph::Components() // 그래프의 연결요소들을 결정 { // visited는 Graph의 bool* 데이타 멤버로 선언되었다고 가정. visited = new bool[n]; fill(visited, visited+n, false); for(i=0; i<n; i++) if(!visited[i]) { DFS(i); // 연결 요소를 탐색 OutputNewComponent(); } delete [] visited; 연결요소의 결정 Component의 분석 인접리스트로 표현: 모든 연결요소들 생성 시간은 O(n+e) 인접행렬로 표현 : O(n2)

신장트리(1) 신장트리(spanning tree) : G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리 깊이-우선 신장트리(depth-first spanning tree) 너비-우선 신장트리(breadth-first spanning tree) 완전 그래프와 이 그래프의 세 신장트리 1 2 1 2 3 4 5 6 3 4 5 6 7 7 (a) DFS(0) 신장 트리 (b) BFS(0) 신장 트리

신장트리(2) 예제 6.3 [회로 등식의 생성] 신장트리는 G의 최소부분 그래프(minimal subgraph) 전기 네트워크에 대한 신장트리 구함 비트리 간선을 신장트리에 한번에 하나씩 도입 Kirchoff의 제2 법칙 이용하여 회로 등식 얻음 신장트리는 G의 최소부분 그래프(minimal subgraph) G'로서 V(G') = V(G)이고 G'는 연결되어 있음 신장트리는 n-1개의 간선 가짐

이중결합요소(1) 단절점(articulation point) 이중 결합 그래프(biconnected graph) 그래프의 정점들중 이 정점과 이 정점에 부속한 모든 간선들 삭제 시, 최소한 두 개의 연결요소를 만들게 하는 정점 이중 결합 그래프(biconnected graph) 절점이 없는 연결 그래프 이중 결합 요소(biconnected component) 최대 이중결합 부분그래프(maximal biconnected subgraph) 1 2 3 4 5 7 6 8 9 1 2 3 4 5 9 6 7 8 연결 그래프 이중 결합 요소

이중결합요소(2) 연결 무방향 그래프의 이중결합요소 깊이-우선 신장 트리를 이용 연결 그래프 1 2 3 4 5 8 6 7 9 10 1 2 3 4 5 9 6 7 8 10 1 2 3 4 5 9 6 7 8 연결 그래프 루트를 3으로 하는 깊이-우선 신장 트리

이중결합요소(3) 백 간선(back edge) 교차 간선(cross edge) low(w) 1 2 3 4 5 6 7 8 9 u가 v의 조상이거나 v가 u의 조상인 비트리 간선(u,v) 교차 간선(cross edge) 백 간선이 아닌 비트리 간선 low(w) w의 후손들과 많아야 하나의 백 간선으로 된 경로를 이용해 w로부터 도달할 수 있는 가장 적은 깊이 우선번호 low(w) = min{dfn(w), min{low(x) | x는 w의 자식}, min{dfn(x) | (w,x)는 백 간선}} Vertex 1 2 3 4 5 6 7 8 9 dfn 10 low 신장 트리에 대한 dfn 값과 low 값

최소비용 신장트리 최소비용 신장트리(minimum-cost spanning tree) 최저의 비용을 갖는 신장트리 Kruskal, Prim, Sollin 알고리즘 갈망법(greedy method) 최적의 해를 단계별로 구한다 각 단계에서는 몇 개의 판단 기준에 따라 최상의 결정을 내린다 한번 내려진 결정은 뒤에 번복이 불가능하므로 각각의 결정이 가능한 해를 도출해낼 수 있는 지 확인 신장트리의 제한 조건 (1) 그래프내에 있는 간선들만을 사용 (2) 정확하게 n-1개의 간선만을 사용 (3) 사이클을 생성하는 간선을 사용 금지

Kruskal 알고리즘(1) 알고리즘 한번에 하나씩 T에 간선을 추가해가면서 최소비용 신장트리 T를 구축 G는 연결되어 있고 n>0개의 정점을 가지므로 정확하게 n-1개의 간선만이 T에 포함됨.

Kruskal 알고리즘(2) 예제 6.4 Kruskal 알고리즘의 각 단계 28 10 1 10 10 1 1 1 14 5 5 28 10 1 10 10 1 1 1 14 5 5 16 5 5 6 2 24 6 6 2 2 6 2 25 4 4 18 4 4 12 12 3 22 3 3 3 ( d) ( a) ( b) ( c) 10 10 10 10 1 1 1 1 14 14 14 14 5 16 5 16 5 5 16 6 6 6 6 2 2 2 2 25 4 4 4 4 12 12 12 12 22 3 22 3 3 3 ( g) ( h) ( e) ( f) Kruskal 알고리즘의 각 단계

Kruskal 알고리즘(3) T = while ((T가 n-1개 미만의 간선을 포함) && (E가 공백이 아님)) { E에서 최소 비용 간선 (v,w) 선택; E에서 (v,w)를 삭제; if (v,w)가 T에서 사이클을 만들지 않으면 T에 (v,w)를 추가; else discard (v,w); } if (T가 n-1개 미만의 간선을 포함) cout << "신장 트리 없음" << endl; Kruskal 알고리즘 정리 6.1 G를 무방향 연결 그래프라 하자. Kruskal 알고리즘은 최소비용 신장트리를 생성한다.

Prim 알고리즘(1) 알고리즘 한번에 한 간선씩 최소 비용 신장 트리를 구축 각 단계에서 선택된 간선의 집합은 트리 하나의 정점으로 된 트리 T에서 시작 최소 비용 간선 (u,v)를 구해 T U {(u,v)}이 트리가 되면 T에 추가 T에 n-1개의 간선이 포함될 때까지 간선의 추가 단계를 반복 추가된 간선이 사이클을 형성하지 않도록 각 단계에서 간선 (u,v)를 선택할 때 u 또는 v중 오직 하나만 T에 속한 것을 고른다.

Prim 알고리즘(2) Prim 알고리즘의 진행 단계 10 1 10 1 10 1 5 5 5 6 6 6 2 2 2 25 25 4 10 1 10 1 10 1 5 5 5 6 6 6 2 2 2 25 25 4 4 4 22 3 3 3 (a) (b) (c) 10 1 10 1 10 1 14 16 16 5 5 5 6 6 6 2 2 2 25 25 25 4 4 4 12 12 12 22 22 22 3 3 3 (d) (e) (f) Prim 알고리즘의 진행 단계

Sollin 알고리즘 알고리즘 각 단계에서 여러개의 간선을 선택 각 단계에서는 포리스트에 있는 각 트리에 대해 하나의 간선을 선택 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용 간선 선택된 간선은 구축중인 신장트리에 추가 오직 하나의 트리만이 존재 or 더 이상 선택할 간선이 없을 때 종료 10 1 10 1 14 14 16 5 5 6 6 2 2 25 4 4 12 12 22 22 3 3 (a) (b) Sollin 알고리즘의 단계들

최단경로와 이행적 폐쇄 단일 시발점/모든 종점: 음이 아닌 간선 비용 문제 : 시발 정점 v에서부터 G의 모든 다른 정점까지의 최단경로를 구하는 것 45 50 10 경로 길이 1 2 1) 0, 3 10 30 2) 0, 3, 4 25 10 20 15 20 35 3) 0, 3, 4, 1 45 4) 0, 2 45 3 4 5 15 3 (a) 그래프 (b) 0에서부터의 최단 경로 그래프와 정점 0에서 모든 종점까지의 최단경로

단일 시발점/모든 종점: 음이 아닌 간선 비용(1) ShortestPath 함수 : 최단 경로의 길이의 결정 ShortestPath의 분석 n개의 정점을 가진 그래프에 대한 수행시간은 O (n2) void MatrixWdigraph::ShortestPath(const int n, const int v) // dist[j],0  j n은 n개의 정점을 가진 방향 그래프 G에서 정점 v로부터 정점 j까지 // 의 최단 경로 길이로 설정됨. 간선의 길이는 length[j][j]로 주어짐. { for (int i=0; i<n; i++) s[i] = false; dist[i] = length[v][i]; // 초기화 s[v] = true; dist[v] = 0; for (i=0; i<n-2; i++) { // 정점 v로부터 n-1개 경로를 결정 int u = Choose(n); // choose는 s[w]=false 이고 // dist[u] = minimum dist[w]가 되는 u를 반환 s[u] = true; for (int w=0; w<n; w++) if(!s[w]&&dist[u]+length[u][w]<dist[w]) dist[w] = dist[u] + length[u][w]; } // for(i=0; ...)의 끝 }

단일 시발점/모든 종점: 음이 아닌 간선 비용(2) 예제 6.5 Boston 4 1500 Chicago 1200 3 250 San Francisco 800 1 2 1000 Denver 300 5 New York 1000 1400 1700 7 Los Angeles 900 New Orleans 1000 6 Miami (a) 방향 그래프 0 1 2 3 4 5 6 7 1 300 2 1000 800 3 1200 4 1500 250 5 1000 900 1400 6 1000 7 1700 (b) 길이-인접 행렬

단일 시발점/모든 종점: 음이 아닌 간선 비용(3) 반복 선택된 정점 거 리 LA SF DEN CHI BOST NY MIA NO [0] [1] [2] [3] [4] [5] [6] [7] 초기 ---- ¥ ¥ ¥ 1500 250 ¥ ¥ 1 5 ¥ ¥ ¥ 1250 250 1150 1650 2 6 ¥ ¥ ¥ 1250 250 1150 1650 3 3 ¥ ¥ 2450 1250 250 1150 1650 4 7 3350 ¥ 2450 1250 250 1150 1650 5 2 3350 3250 2450 1250 250 1150 1650 6 1 3350 3250 2450 1250 250 1150 1650 방향그래프에 대한 ShortestPath의 작동

단일 시발점/모든 종점:일반적 가중치(1) 음수 길이 사이클이 존재할 경우 최단 길이 경로가 존재하지 않는다. 1 2 5 7 -5 음의 길이 간선을 가진 방향 그래프 1 2 -2 음의 길이 사이클을 가진 방향 그래프 동적 프로그래밍 방법 : 모든 u에 대해 distn-1[u]를 구함 distk[u] = min{distk-1[u], min{distk-1[i] + length[i][u]}} i

단일 시발점/모든 종점:일반적 가중치(2) 예제 6.6 음의 길이 간선을 가진 최단 경로 1 2 3 4 6 5 -2 -1 ( 2 3 4 6 5 -2 -1 ( a) 방향 그래프 (b) distk 음의 길이 간선을 가진 최단 경로

단일 시발점/모든 종점:일반적 가중치(3) Bellman과 Ford 알고리즘 BellmanFord의 분석 void MatrixWDigraph::BellmanFord(const int n, const int v) {// 음의 길이 간선을 가지는 단일 시발점 모든 종점 최단 경로 for(int i=0; i<n; i++) dist[i] = length[v][i]; // dist 초기화 for(int k=2; k<=n-1; k++) for(u!=v이고 최소한 하나의 진입 간선을 갖는 u에 대해) for(그래프의 각 <i,u>에 대해) if(dist[u]>dist[i]+length[i][u]) dist[u] = dist[i] + length[i][u]; } 최단 경로를 계산하는 Bellman과 Ford 알고리즘 BellmanFord의 분석 인접행렬 O(n3), 인접 리스트 O(ne)

모든 쌍의 최단경로(1) uv인 모든 정점의 쌍 u와 v간의 최단경로를 구하는 것 연속적으로 A-1, A0, A1, A2, …, An-1을 생성하는 것 인덱스가 K보다 큰 정점을 통과하지 않는 i에서 j까지의 최단 경로가 인덱스가 k인 정점을 통과하지 않으면 그 길이는 Ak-1[i][j]가 된다. 최단 경로가 k를 통과한다고 하면 경로는 i에서 k까지의 경로와 k에서 j까지의 경로로 구성. 이러한 i에서 k까지 또, k에서 j까지의 부분 경로 둘 다 k-1보다 큰 인덱스를 가진 정점을 통과하지 않음. 이 경로들이 길이는 Ak-1[i][k], Ak-1[k][j]가 된다. Ak[i][j] = min{Ak-1[i][j], Ak-1[i][k] + A k-1[k][j]}, k  0 A-1[i][j] = length[i][j]

모든 쌍의 최단경로(2) uv인 모든 정점의 쌍 u와 v간의 최단경로를 구하는 것 Ak[i][j] = min{Ak-1[i][j], Ak-1[i][k] + A k-1[k][j], k  0 A-1[i][j] = length[i][j] void MatrixWDigraph::AllLengths(const int n) { // length[n][n]은 n개의 정점을 가진 그래프의 인접 행렬이다. // a[i][j]는 i와 j 사이의 최단 경로의 길이이다. for(int i=0; i<n; i++) for(int j=0; j<n; j++) a[i][j] = length[i][j]; // length를 a에 복사 for(int k=0; k<n; k++) // 제일 큰 정점의 인덱스가 k인 경로에 대해 for(i=0; i<n; i++) // 가능한 모든 정점의 쌍에 대해 if((a[i][k]+a[k][j]) < a[i][j]) a[i][j] = a[i][k] + a[k][j]; } 모든 쌍의 최단경로 AllLengths의 분석 전체 시간은 O(n3)

모든 쌍의 최단경로(3) 예제 6.7 모든 쌍의 최단 경로 문제의 예 A 1 2 A 1 2 1 4 11 4 11 1 6 2 1 -1 1 2 A 1 2 1 4 11 4 11 4 11 2 1 6 2 1 6 2 3 2 2 3 2 3 7 ( a) 방향그래프 ( b) A -1 ( c) A A 1 1 2 A 2 1 2 4 6 4 6 1 6 2 1 5 2 2 3 7 2 3 7 ( d) A 1 ( e) A 2 모든 쌍의 최단 경로 문제의 예

이행적 폐쇄(1) 이행적 폐쇄 행렬(A+) 반사 이행적 폐쇄 행렬(A*) i에서 j로의 경로 길이 0  A+[i][j] = 1 인 행렬 반사 이행적 폐쇄 행렬(A*) i에서 j로의 경로 길이 0  A*[i][j] = 1 인 행렬 1 2 3 4 ( a) 방향 그래프 G 0 1 2 3 4 b) 인접행렬 A c) A + d) A *

이행적 폐쇄(2) A+ A* : A+의 대각선에 있는 항을 모두 1로 설정 전체 시간은 O(n3) 간선 <i, j>  G  length[i][j] = 1, otherwise, length[i][j] = LARGE All Lengths 종료시 length[i][j]  +  A+[i][j]=1 A* : A+의 대각선에 있는 항을 모두 1로 설정 전체 시간은 O(n3)

작업 네트워크 AOV(activity on vertex) 네트워크 : 정점이 작업을, 간선이 작업간의 선행 관계를 나타내는 방향그래프 G C1 C2 C4 C5 C6 C3 C7 C8 C15 C9 C10 C12 C13 C11 C14 (a) 가상적인 대학에서 컴퓨터 과학 학위에 필요한 과목들 (b) 과목은 정점으로, 선수과목은 간선으로 포현한 AOV 네트워크 An activity-on-vertex(AOV) 네트워크

AOV 네트워크(1) 정의 정점 i로부터 정점 j로의 방향 경로 존재하면 정점 i를 정점 j의 선행자(predecessor) 간선 <i, j>가 존재하면 정점 i를 정점 j의 직속 선행자(immediate predecessor) i가 j의 선행자 → j는 i의 후속자(successor) i가 j의 직속 선행자 → j는 i의 직속 후속자(immediate successor) 모든 세 쌍 i, j, k에 대해 I  j 이고 j  k → I  k 가 성립하면 관계는 이행적(transitive) S에 속한 모든 원소 x에 대해 x  x가 성립하지 않으면 관계는 집합 S상에서 비반사적(irreflexive) 분분 순서(partial order) : 이행적, 비반사적인 선행 관계 위상순서(topological order) : 임의의 두 정점 i, j에 대해 네트워크에서 i가 j의 선행자이면 선형순서에서도 i가 j 앞에 있는 그래프 정점의 선형 순서

AOV 네트워크(2) (a) 초기 (b) 정점 0 삭제 (c) 정점 3 삭제 (d) 정점 2 삭제 (e) 정점 5 삭제 1 1 1 2 4 2 4 2 4 3 5 3 5 5 (a) 초기 (b) 정점 0 삭제 (c) 정점 3 삭제 1 1 4 4 4 5 (d) 정점 2 삭제 (e) 정점 5 삭제 (f) 정점 1 삭제 생성된 위상 순서 : 0, 3, 2, 5, 1, 4

AOV 네트워크(3) 위상 정렬 알고리즘에 의해 사용되는 내부 표현 count first data link [0] 1 1 2 [1] 4 1 [2] 1 4 1 5 [3] 1 5 1 4 [4] 3 [5] 2 위상 정렬 알고리즘에 의해 사용되는 내부 표현

AOV 네트워크(4) TopologicalOrder의 분석 점근적 계산 시간 O (e+n) 위상 순서 void LinkedDigraph::TopologicalOrder() { // 네트워크의 n개 정점이 위상 순서로 나열한다. int top = -1; for(int i=0; i<n; i++) // 선행자가 없는 정점들을 연결 스택으로 if(count[i]==0) {count[i] = top; top = i;} // 생성 for(i=0; i<n; i++) if(top==-1) throw “Network has a cycle." int j = top; top = count[top]; // 정점 하나를 스택에서 꺼냄 cout << j << endl; Chain<int>::ChainIterator ji = adjLists[j]. begin(); while (ji) { // j의 후속자 정점의 계수를 감소시킴 count[*ji]--; if(count[*ji]==0) { count[*ji] = top;top=*ji;} // *ji를 스택에 삽입 ji++; } 위상 순서

AOE 네트워크(1) AOE(activity on edge) 네트워크 방향 간선 : 프로젝트에서 수행되어야 할 작업 정점 : 사건(event) (사건은 어떤 작업의 완료를 알림) 정점에서 나오는 간선이 의미하는 작업은 그 정점에서의 사건이 발생할 때까지 시작될 수 없다.

AOE 네트워크(2) (a) 가상 프로젝트의 작업 네트워크 사 건 의 미 (b) 네트워크 (a)의 몇몇 사건의 의미 1 4 7 2 3 5 4 8 7 6 a = 6 start finish a = 1 a = 9 a = 2 10 a = 4 11 a = 7 a = 4 9 a = 2 a = 5 (a) 가상 프로젝트의 작업 네트워크 사 건 의 미 1 4 7 8 프로젝트의 시작 작업 a1의 종료 작업 a4와 a5의 종료 작업 a8와 a9의 종료 프로젝트의 종료 (b) 네트워크 (a)의 몇몇 사건의 의미

AOE 네트워크(3) 임계경로(critical path) 가장 이른 시간(earliest time) e(i) 시작 정점에서 종료 정점까지의 최장 경로(longest path) 가장 이른 시간(earliest time) e(i) 시작 정점 0에서 정점 i 까지의 최장 경로 길이 가장 늦은 시간(latest time) l(i) 프로젝트 기간을 지연시키지 않으면서 가장 늦게 작업을 시작할 수 있는 시간 임계작업(critical activity) : e(i) = l(i) 인 작업 임계경로 분석의 목적 임계작업들을 식별해내어 가용 자원을 집중시킴으로써 프로젝트 완료 시간을 단축

AOE 네트워크(4) 가장 이른 작업 시간과 가장 늦은 작업 시간 가장 이른 시간의 계산 e(i)= ee[k] (ee[k] : 가장 이른 사건 발생 시간) l(i) = le[l] - 작업 ai의 기간 (le[l] : 가장 늦은 사건 발생 시간) 가장 이른 시간의 계산 ee[j] = max { ee[i] + <i, j>의 시간 } (P(j)는 j의 직속 선행자의 집합) iP(j)

AOE 네트워크(5) (a) 인접리스트 (b) ee의 계산 1 2 6 4 3 5 9 7 8 [0] [1] [2] [3] [4] 1 2 6 4 3 5 9 7 8 [0] [1] [2] [3] [4] [5] [6] [7] [8] count first vertex dur link (a) 인접리스트 (b) ee의 계산

AOE 네트워크(6) 가장 늦은 시간의 계산 le[j] = min { le[i] - <j, i>의 기간 } (S(j)는 j의 직속 후속자들의 집합) iP(j) le[8]=ee[8]=18 le[6]=min{le[8]-2}=16 le[7]=min{le[8]-4}=14 le[4]=min{le[6]-9, le[7]-7}=7 le[1]=min{le[4]-1}=6 le[2]=min{le[4]-1}=6 le[5]=min{le[7]-4}=10 le[3]=min{le[5]-2}=8 le[0]=min{le[1]-6, le[2]-4, le[3]-5}=0 AOE 네트워크에 대한 le의 계산

AOE 네트워크(7) 작업 e 1 1 – e 1 – e = 0 a Yes a 2 2 No a 3 3 No a 6 6 Yes a 이른 시작 시간 가장 높은 시간 임계도 임계성 작업 e 1 1 – e 1 – e = 0 a Yes 1 a 2 2 No 2 a 3 3 No 3 a 6 6 Yes 4 a 4 6 2 No 5 a 5 8 3 No 6 a 7 7 Yes 7 a 7 7 Yes 8 a 7 10 3 No 9 a 16 16 Yes 10 a 14 14 Yes 11 이른, 늦은 임계도 값

AOE 네트워크(8) a1 a4 a10 a7 a8 a11 a5 a1 a7 a3 a6 a2 a4 start 4 8 finish a8 a11 7 모든 비임계 작업을 삭제한 후의 그래프 a5 1 4 5 a1 a7 a3 a6 3 a2 a4 2 도달 불가능한 작업을 가진 AOE 네트워크