
Digraphs and DAGs
Erik Demaine continues MIT's 6.1200J Mathematics for Computer Science with a lecture on directed graphs. He covers walks, cycles, and connectivity in digraphs before turning to Directed Acyclic Graphs, digraphs that contain no cycles. The session builds on earlier graph theory material in the course, formalizing definitions and working through the structural properties that distinguish DAGs from general digraphs, groundwork for later topics like topological sorting and scheduling problems. Demaine develops the ideas on the board in the standard MIT OCW lecture format, moving through definitions, examples, and proofs at a pace suited to students already familiar with basic graph terminology. Filmed as part of the Spring 2024 offering of 6.1200J, a core discrete mathematics course for MIT computer science students, the lecture runs just over an hour and is one installment in a full semester sequence available through MIT OpenCourseWare.