방향 그래프(Directed Graph)는 정점(Vertex)을 연결하는 간선(Edge)에 지금까지와는 달리 방향성을 부여한 것입니다. 그래서 간선을 화살표로 표시합니다. 이것의 의미는 정점 A에서 B로 갈 수는 있어도, B에서 A로는 갈 수 없는 상황을 모델링하는데 유용합니다. 도로를 모델링할 경우 일방통행로가 해당될 것이고, 공정을 모델링할 경우 비가역적(Irreversible) 변이가 이에 해당될 것입니다.
방향 그래프는 그래서 어떤 두 정점간에 연결될 수 있는가(Connectivity)를 알아보는 것이 주요 이슈입니다. 도달 가능성(Reachability)은 한 정점에서 연결되는 모든 정점을 찾아보는 문제로, Warshall 알고리즘을 통해 이행적 폐쇄(Transitive Closure)를 찾는 방법으로 해결해 봅니다.
그외에 강한 결합 요소를 찾는 문제, 위상 정렬 문제, AOE 네트워크 문제, 임계 작업 찾기 등의 복잡하지만 현실에서 많이 제기되는 문제들을 해결하는 방법을 알아 봅니다.
강의 자료
강의 동영상
22.0 방향 그래프 - 시작 : 이 장에서는 방향 그래프의 개념과 표현, 그리고 도달 가능성, 이행적 폐쇄, 강한 결합 요소 찾기, 위상 정렬 등의 다양한 주제를 다루어 봅니다.
22.1 방향 그래프 - 개요 : 방향 그래프는 간선에 방향성이 있는 그래프입니다. 다른 그래프와 마찬가지로 인접 행렬과 리스트로 표현할 수 있습니다.
22.2 도달 가능성 (Reachability) : 방향 그래프의 간선은 한 방향만 가리키기 때문에 그래프의 모든 정점간에 연결 통로가 존재하지 않을 수도 있습니다. 어떤 정점에서 출발하여 도달할 수 있는 모든 정점들을 찾아내는 도달 가능성 문제를 풀어 봅니다. 깊이 우선 탐색과 Warshall 알고리즘을 이용합니다.
22.3 강한 결합 요소 : 강한 결합 요소는 두 정점이 양방향으로 연결되어 있는 요소를 의미합니다. 그런데 직접 연결되지 않고 간접적으로 연결되는 것도 포함합니다. 재귀적인 방법으로 강한 결합 요소를 찾아 봅니다.
22.4 위상 정렬 (Topological Sort) : 위상 정렬은 비순환 방향 그래프(DAG, Directed Acyclic Graph)를 다룹니다. DAG는 강한 결합 요소가 없는 그래프를 의미하며, 한 방향으로만 진행할 수 있어 비가역적인 공정(Process)을 묘사하는데 유용합니다. 위상정렬은 DAG의 정점을 연결 상태를 고려하여 일렬로 세우는 것을 의미합니다. 혼자서 작업하는 경우의 작업 순서를 뜻합니다.
22.5 AOE 네트워크 (AOE Network) : AOE는 Activity On Edge의 약자로 간선을 공정, 정점을 공정이 완료된 상태로 모델링합니다. 그래서 공정에 가중치를 부여할 수 있습니다. 가중치는 공정의 비용(기간, 인원 등)을 배정합니다.
22.6 임계 작업 (Critical Activity) : AOE 네트워크를 이용하여 복잡한 공정의 임계 작업을 구할 수 있습니다. 임계 작업은 전체 공정의 비용을 결정하는 일련의 작업들을 의미합니다. 임계 작업의 비용을 줄이면 전체 공정의 비용을 줄일 수 있기 때문에, 공정의 생산성 향상에 매우 중요합니다.
22.9 방향 그래프 - 결론 : 방향 그래프는 주로 도달 가능성과 공정의 모델링에 많이 사용됩니다. 이번 장에서 배운 방향 그래프의 내용을 정리해 봅니다.
관련글 |
- C++로 배우는 알고리즘
- 21장 : 가중 그래프 (Weighted Graph)
- 23장 : 다항식 (Polynomial)
댓글 없음:
댓글 쓰기