유향 비순환 그래프

유향 비순환 그래프(有向非循環 graph, directed acyclic graph, DAG) 및 방향 비순환 그래프(方向非循環 graph)는 수학, 컴퓨터 과학 분야의 용어의 하나로서 방향 순환이 없는 무한 유향 그래프이다. 즉, 무한히 수많은 꼭짓점과 간선으로 구성되며 각 간선은 하나의 꼭짓점에서 다른 꼭짓점으로 방향을 잇는데 이처럼 어떠한 꼭짓점 $v$ 에서 시작하여 끝내 다시 $v$ 로 돌아가 순환 반복되는 일정한 방향의 일련한 간선을 따라가는 방법이 없다. 다시 말해 DAG는 위상정렬이 있는 유향 그래프이다.

DAG는 각기 다른 종류의 수많은 정보를 모델링할 수 있다. 스프레드시트는 DAG로 모델링이 가능한데, 각 셀에 대해서는 꼭짓점으로, 간선의 경우 하나의 셀의 공식이 다른 셀의 값을 사용하는 곳에 쓸 수 있다. 즉, DAG의 위상정렬을 사용하면 스프레드시트가 변경될 때 모든 셀의 값을 업데이트할 수 있다.

외부 링크

위키미디어 공용에 관련된
미디어 분류가 있습니다.

유향 비순환 그래프

Weisstein, Eric Wolfgang. “Acyclic Digraph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
DAGitty – an online tool for creating DAGs