다음 그래프는 AOE(Activity on Edge) 네트워크를 보여 … | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 24년 1회차
다음 그래프는 AOE(Activity on Edge) 네트워크를 보여 준다. 정점의 숫자는 공정을 나타내고, 간선 위에 있는 는 작업을, 괄호 안의 숫자는 그 작업을 수행하는 데 필요한 최소한의 시간을 나타낼 때, 임계 경로의 길이는?
1
10
2
11
3
12
4
13
해설
임계 경로의 길이는 12이며, 경로는 0 → 3 → 6 → 8(a2, a7, a10)이다.
각 정점의 가장 이른 발생 시각은 들어오는 간선 중 최댓값으로 구한다.
1: 5, 2: 3, 3: 4, 4: 3+1=4
5: max(5+2, 4+3)=7, 6: max(4+3, 4+5)=9, 7: 4+2=68: max(7+4, 9+3, 6+5)=max(11, 12, 11)=12
- 10: 0 → 2 → 4 → 6 → 8(3+1+3+3)의 길이로, 가장 긴 경로가 아니다.
- 11: 0 → 1 → 5 → 8이나 0 → 3 → 7 → 8의 길이로, 가장 긴 경로가 아니다.
- 13: 13이 되는 경로는 존재하지 않는다.
오류나 개정된 내용이 보이면 알려주세요