Directed Acyclic Graph (1) 썸네일형 리스트형 122. Directed Acyclic Graph DAG(Directed Acyclic Graph)는 사이클이 존재하지 않는 유향 그래프를 의미한다. 정의는 이렇게 간단하지만 응용할 수 있는 분야는 상당히 넓은 편이며, 최근에는 블록체인에서도 많이 다루면서 점점 주목받고 있는 개념이기도 하다. 사회과학에서도 등장한다고 한다. 그래프 이론의 관점에서 DAG의 큰 특징은 다음과 같이 나타낼 수 있다. 진입 차수가 $0$인 정점이 하나 이상 존재한다. 진출 차수가 $0$인 정점이 하나 이상 존재한다. 어떤 정점 및 그 정점과 연결된 간선들을 그래프에서 제거할 경우 남는 정점과 간선들로 이루어진 그래프도 DAG이다. 모든 정점을 순서대로 나열했을 때 간선의 방향이 전부 동일하게(왼쪽 → 오른쪽 또는 오른쪽 → 왼쪽) 할 수 있다. 네 번째 특징에 나온 정점 나.. 이전 1 다음
