제 6 장 그래프

Size: px

Start display at page:

Download "제 6 장 그래프"

민종 피
4 years ago
Views:

1 제 장 그래프 Copyright DBLAB, Seoul National University

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

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

4 그래프추상데이타타입 () 예제그래프 G G G V(G )={,,,} E(G )={(,),(,),(,),(,),(,),(,)} V(G )={,,,,,,) E(G )={(,),(,),(,),(,),(,),(,)} V(G )={,,} E(G )={<,>,<,>,<,>} Copyright DBLAB, Seoul National University

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

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

7 그래프추상데이타타입 () G (i) (ii) (iii) (iv) G 의서브그래프 G (i) (ii) (iii) (iv) G 의서브그래프 Copyright DBLAB, Seoul National University

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

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

10 그래프표현법 () 인접행렬 (Adjacency Matrix) G=(V,E) 는정점의수가 n(n ) 인그래프 인접행렬 : n n 의 차원배열 간선 (v i, v j ) E(G) a[i][j]= 간선 (v i, v j ) E(G) a[i][j]= 필요공간 : n 비트 G 의인접행렬 G 의인접행렬 G 의인접행렬 n- 무방향그래프 : 어떤정점 i의차수는그행의합 : a[i][j] J= 방향그래프 : 행의합은진출차수, 열의합은진입차수 인접행렬의수행시간 : 최소한 O (n ) 희소그래프 (sparse graph) : O (e+n) Copyright DBLAB, Seoul National University

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

12 인접리스트 () [] [] [] [] adjlists data link [] [] [] adjlists G 인접리스트 G 인접리스트 [] [] [] [] [] [] [] [] adjlists G 인접리스트 Copyright DBLAB, Seoul National University (

13 인접리스트 () int nodes[n + *e +]; 그래프 G 의순차표현 [] [] [] G 의역인접리스트 Copyright DBLAB, Seoul National University

14 인접리스트 () 헤더노드 그래프 G 에대한직교리스트표현 Copyright DBLAB, Seoul National University

15 인접다중리스트 (Adjacency Multilists) 간선 (u,v) 는두개의엔트리로표현 : u 를위한리스트, v 를위한리스트에나타남 새로운노드구조 m vertex vertex list list [] [] [] [] adjnodes The lists are N N N edge (,) N N N edge (,) N N edge (,) N N N edge (,) N N edge (,) N edge (,) vertex : N -> N -> N vertex : N -> N -> N vertex : N -> N -> N vertex : N -> N -> N Copyright DBLAB, Seoul National University G 에대한인접다중리스트

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

17 C++ 그래프클래스 Graph Matrix WDigraph LinkedWDigraph LinkedDigraph MatrixWGraph MatrixDigraph LinkedWGraph LinkedGraph MatrixGraph 그래프클래스에대해파생가능계층 Copyright DBLAB, Seoul National University

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

19 깊이우선탐색 () 예제.,,,,,,, 순으로방문 그래프 G 와그인접리스트 [] [] [] [] [] [] [] [] adjlists (a) (b) Copyright DBLAB, Seoul National University 9

20 깊이우선탐색 () DFS 의분석 탐색을끝내는시간 O (e) v에인접한모든정점들을찾는데 O (n) 의시간 총시간은 O(n ) Copyright DBLAB, Seoul National University

21 너비우선탐색 () 너비우선탐색 (BFS; Breadth-First Search) 시작정점 v 를방문 v 에인접한모든정점들을방문 새롭게방문한정점들에인접하면서아직방문하지못한정점들을방문 예제.,,,,,,, 순으로방문 Copyright DBLAB, Seoul National University

22 너비우선탐색 () 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(n ) 인접리스트표현 : 전체비용 O(e) Copyright DBLAB, Seoul National University

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

24 신장트리 () 신장트리 (spanning tree) : G 의간선들로만구성되고 G 의모든정점들이포함된트리 깊이 - 우선신장트리 (depth-first spanning tree) 너비 - 우선신장트리 (breadth-first spanning tree) 완전그래프와이그래프의세신장트리 (a) DFS() 신장트리 (b) BFS() 신장트리 Copyright DBLAB, Seoul National University

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

26 이중결합요소 () 단절점 (articulation point) 그래프의정점들중이정점과이정점에부속한모든간선들삭제시, 최소한두개의연결요소를만들게하는정점 이중결합그래프 (biconnected graph) 절점이없는연결그래프 이중결합요소 (biconnected component) 최대이중결합부분그래프 (maximal biconnected subgraph) 연결그래프 이중결합요소 Copyright DBLAB, Seoul National University

27 이중결합요소 () 연결무방향그래프의이중결합요소 깊이 - 우선신장트리를이용 연결그래프 루트를 으로하는깊이 - 우선신장트리 Copyright DBLAB, Seoul National University

28 이중결합요소 () 백간선 (back edge) 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 8 9 dfn 8 9 low 9 신장트리에대한 dfn 값과 low 값 Copyright DBLAB, Seoul National University 8

최소비용신장트리 최소비용신장트리 (minimum-cost spanning tree) 최저의비용을갖는신장트리 Kruskal, Prim, Sollin 알고리즘 갈망법 (greedy method) 최적의해를단계별로구한다 각단계에서는몇개의판단기준에따라최상의결정을내린다

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

30 Kruskal 알고리즘 () 알고리즘 한번에하나씩 T 에간선을추가해가면서최소비용신장트리 T 를구축 T 에포함될간선을비용의크기순으로선택 이미 T 에포함된간선들과사이클을형성하지않는간선만을 T 에추가 - G 는연결되어있고 n> 개의정점을가지므로정확하게 n- 개의간선만이 T 에포함됨. Copyright DBLAB, Seoul National University

31 Kruskal 알고리즘 () 예제. 8 8 (a) (b) (c) (d) (e) (f) (g) (h) Kruskal 알고리즘의각단계 Copyright DBLAB, Seoul National University

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

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

34 Prim 알고리즘 () (a) (b) (c) (d) (e) (f) Prim 알고리즘의진행단계 Copyright DBLAB, Seoul National University

35 Sollin 알고리즘 알고리즘 각단계에서여러개의간선을선택 각단계에서는포리스트에있는각트리에대해하나의간선을선택 이간선은오직하나의정점만그트리에속한최소비용간선 선택된간선은구축중인신장트리에추가 오직하나의트리만이존재 or 더이상선택할간선이없을 때종료 Copyright DBLAB, Seoul National University (a) (b) Sollin 알고리즘의단계들

36 최단경로와이행적폐쇄 단일시발점 / 모든종점 : 음이아닌간선비용 문제 : 시발정점 v 에서부터 G 의모든다른정점까지의최단경로를구하는것 (a) 그래프 경로 길이 ), ),, ),,, ), (b) 에서부터의최단경로 그래프와정점 에서모든종점까지의최단경로 Copyright DBLAB, Seoul National University

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

38 단일시발점 / 모든종점 : 음이아닌간선비용 () 예제. Chicago San Francisco 8 Denver Los Angeles 9 New Orleans Boston New York (a) 방향그래프 Miami 8 9 (b) 길이 - 인접행렬 Copyright DBLAB, Seoul National University 8

39 단일시발점 / 모든종점 : 음이아닌간선비용 () 반복 선택된정점 거리 LA SF DEN CHI BOST NY MIA NO [] [] [] [] [] [] [] [] 초기 ---- 방향그래프에대한 ShortestPath 의작동 Copyright DBLAB, Seoul National University 9

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

41 Copyright DBLAB, Seoul National University 단일시발점 / 모든종점 : 일반적가중치 () 예제 (a) 방향그래프 - Dist k [] k (b) dist k 음의길이간선을가진최단경로

42 단일시발점 / 모든종점 : 일반적가중치 () Bellman 과 Ford 알고리즘 void MatrixWDigraph::BellmanFord(const int n, const int v) {// 음의길이간선을가지는단일시발점모든종점최단경로 for(int i=; i<n; i++) dist[i] = length[v][i]; // dist 초기화 } for(int k=; k<=n-; 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(n ), 인접리스트 O(ne) Copyright DBLAB, Seoul National University

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

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

45 Copyright DBLAB, Seoul National University 모든쌍의최단경로 () 예제. A - A (b) A - (c) A A (d) A A (e) A (a) 방향그래프모든쌍의최단경로문제의예

46 Copyright DBLAB, Seoul National University 이행적폐쇄 () 이행적폐쇄행렬 (A + ) i 에서 j 로의경로길이 A + [i][j] = 인행렬 반사이행적폐쇄행렬 (A * ) i 에서 j 로의경로길이 A * [i][j] = 인행렬 (a) 방향그래프 G (b) 인접행렬 A (c) A + (d) A *

47 이행적폐쇄 () A + 간선 <i, j> G length[i][j] =, otherwise, length[i][j] = LARGE All Lengths 종료시 length[i][j] + A + [i][j]= A * : A + 의대각선에있는항을모두 로설정전체시간은 O(n ) Copyright DBLAB, Seoul National University

48 작업네트워크 AOV(activity on vertex) 네트워크 : 정점이작업을, 간선이작업간의선행관계를나타내는방향그래프 G 과목번호 과목명 선수과목 C C C C C C C C8 C9 C C C C C C 프로그래밍 I 이산수학자료구조수학 I 수학 II 선형대수알고리즘분석어셈블리어운영체제프로그래밍언어론컴파일러설계인공지능계산이론병렬알고리즘수치해석 없음없음 C, C 없음 C C C, C C C, C8 C C C C C C C C C C C C C8 C C C9 C C C C C (a) 가상적인대학에서컴퓨터과학학위에필요한과목들 (b) 과목은정점으로, 선수과목은간선으로포현한 AOV 네트워크 An activity-on-vertex(aov) 네트워크 Copyright DBLAB, Seoul National University 8

49 AOV 네트워크 () 정의 정점 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 앞에있는그래프정점의선형순서 Copyright DBLAB, Seoul National University 9

50 AOV 네트워크 () (a) 초기 (b) 정점 삭제 (c) 정점 삭제 (d) 정점 삭제 (e) 정점 삭제 (f) 정점 삭제 생성된위상순서 :,,,,, Copyright DBLAB, Seoul National University

51 AOV 네트워크 () count first data link [] [] [] [] [] [] 위상정렬알고리즘에의해사용되는내부표현 Copyright DBLAB, Seoul National University

52 AOV 네트워크 () TopologicalOrder 의분석 점근적계산시간 O (e+n) void LinkedDigraph::TopologicalOrder() { // 네트워크의 n 개정점이위상순서로나열한다. int top = -; for(int i=; i<n; i++) // 선행자가없는정점들을연결스택으로 if(count[i]==) {count[i] = top; top = i;} // 생성 } for(i=; i<n; i++) if(top==-) 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]==) { count[*ji] = top;top=*ji;} // *ji 를스택에삽입 ji++; } 위상순서 Copyright DBLAB, Seoul National University

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

54 AOE 네트워크 () start a = a = a = a = a = a = 9 8 a = 8 a = finish a = a = 9 a = (a) 가상프로젝트의작업네트워크 사건 8 의미프로젝트의시작작업 a의종료작업 a와 a의종료작업 a8와 a9의종료프로젝트의종료 (b) 네트워크 (a) 의몇몇사건의의미 Copyright DBLAB, Seoul National University

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

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

57 AOE 네트워크 () [] [] count first vertex dur link [] (a) 인접리스트 [] [] [] 9 [] 8 [] 8 [8] (b) ee 의계산 ee [] [] [] [] [] [] [] [] [8] Stack Initial Output Output Output Output Output Output Output Output Output [] [,, ] [,, ] [, ] [] [] [, ] [] [8] Copyright DBLAB, Seoul National University

58 AOE 네트워크 () 가장늦은시간의계산 le[j] = min { le[i] - <j, i> 의기간 } i P(j) (S(j) 는 j 의직속후속자들의집합 ) le[8]=ee[8]=8 le[]=min{le[8]-}= le[]=min{le[8]-}= le[]=min{le[]-9, le[]-}= le[]=min{le[]-}= le[]=min{le[]-}= le[]=min{le[]-}= le[]=min{le[]-}=8 le[]=min{le[]-, le[]-, le[]-}= AOE 네트워크에대한 le 의계산 Copyright DBLAB, Seoul National University 8

59 AOE 네트워크 () 이른시작시간 가장높은시간임계도임계성 작업 e e e = a Yes a No a No a Yes a No a 8 No a Yes a 8 Yes a 9 No a Yes a Yes 이른, 늦은임계도값 Copyright DBLAB, Seoul National University 9

60 AOE 네트워크 (8) a a a a start 8 finish a 8 a 모든비임계작업을삭제한후의그래프 a a a a a a a 도달불가능한작업을가진 AOE 네트워크 Copyright DBLAB, Seoul National University

Chap 6: Graphs

Chap 6: Graphs 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page ) 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v]