그래프 정리

DAG 공정 모델링( 공정 흐름 - 순서적인 걸 따질때 )

Reachabilitiy : 도달 가능성(방향 그래프에서 어느정점에서 어느 정점까지 도달 할 수 있는 지를 보는 것)

Transitive Closure : 우회적으로 어느 정점에서 어느 정점까지 도달 할 수 있는 것을 보느 것

결국 두개는 모든 정점에 대해서 해본다

강한결합( Strongly Connected Components) 방향성 있는 순환 노드 = 사이클을 찾을때, 특징 강한결합으로 이루어진 노드중 하나를 하나 제거해도

ex A,B,C 가 강한 결합인데 A 를 제거해도 B 와 C 는 연결 된다

위상 정렬(Topological sort) -AOV Network( 비선형 구조를 선형 구조로 탐색 하는 방법 )=흐름에 따른 여러 공정 모델링을 한사람이 처리 하는 정렬방법

(A처리 된다음 B 가 처리 되고 B 처리 된다음 C,D 가 동시에 처리 될 수 있고 C 다음 F 가 처리 되고 의 흐름을 선형적으로 한사람이 처리 하는 과정으로

정렬 하는 방법)

역위상 정렬(Reverse Topological sort)

위상정렬의 반대로 처리 하는 것 A->B->C, D 의 순이 위상이라면 C,D -> B ->A 순으로 처리 하는 것

위상정렬에서 AOE Network 이 나오는데 AOE Network 으로 간선에 작업을 놓고 간선에 비용을 쓰는 걸 이용해서 작업이 처리되는 소요 비용 , 시간

등을 알 수 있고 , 임계영역(=임계경로Critical Activity) 를 구할 수 있다 = 작업이 모두 끝나는 시간(= 가장 오래 걸리는 경로)

임계영역을 찾음으로써 임계영역의 처리 시간들을 줄이게 되면 공정의 작업 시간을 줄일 수 있다