DAG là viết tắt của Directed Acyclic Graph, dịch sang tiếng Việt là Đồ thị có định hướng không tuần hoàn. Nó là một mô hình hoặc khái niệm thường được sử dụng trong ngành tiền điện tử và công nghệ. DAG có thể được hiểu như một tập hợp các đỉnh (nodes/vertex) và các cạnh (edges) nối chúng với nhau. Mỗi cạnh có một hướng xác định và không có chu trình (không được lặp lại).
Một số ví dụ về DAG trong cuộc sống có thể kể đến như:
– Lịch sử phiên bản của Git: Mỗi commit là một đỉnh và mỗi cạnh là một thay đổi. Không có hai commit nào có thể trỏ về cùng một commit trước đó.
– Phụ thuộc giữa các công việc trong một dự án: Mỗi công việc là một đỉnh và mỗi cạnh là một ràng buộc. Không có hai công việc nào có thể phụ thuộc lẫn nhau.
– Cây gia phả: Mỗi người là một đỉnh và mỗi cạnh là một quan hệ cha-con. Không có hai người nào có thể là cha-con của nhau.