gen-define-a-directed-acyclic-graph-and-give-one-short-worked-ex-412d

Define a directed acyclic graph and give one short worked example.

# Directed Acyclic Graph (DAG) ## Definition A **directed acyclic graph** is a graph consisting of vertices connected by directed edges, with no cycles. More formally: - **Directed**: Each edge has a direction (goes from one vertex to another) - **Acyclic**: There is no path that starts and ends at the same vertex by following the directed edges ## Worked Example Consider a simple course prerequisite system: ``` CS101 → CS201 → CS301 ↓ ↓ CS150 → CS250 ``` **Vertices**: CS101, CS150, CS201, CS250, CS301 **Directed edges** (prerequisites): - CS101 → CS201 (must take CS101 before CS201) - CS101 → CS150 - CS201 → CS301 - CS201 → CS250 - CS150 → CS250 **Why it's a DAG**: - All edges have direction (showing prerequisite order) - No cycles exist (you can't have a situation where course A requires B, B requires C, and C requires A) - Valid orderings exist, such as: CS101 → CS150 → CS201 → CS250 → CS301 This is a DAG because students can complete courses in a valid order without circular dependencies.