Lesson 1

An important subclass of directed graphs is the class of graphs without cycles. They are called directed acyclic graphs and are commonly abbreviated as DAGs (or even dags). For example, the graph on the left is a DAG, whereas the right one is not (as it contains a cycle \(1 \to 5 \to 4 \to 3 \to 1\)).