6.042J/18.062J 11. Directed Graphs

1 Albert R Meyer, March 1, 2010 Mathematics for Computer Science MIT 6.042J/18.062J Directed Graphs lec 5M.1 Albert R Meyer, March 1, 2010 lec 5M.2 Digraphs • a set, V, of vertices • a set, E ⊆ V×V of directed edges (v,w) ∈ E v w notation: v→w Albert R Meyer, March 1, 2010 Relations and Graphs a c b d V= {a,b,c,d} E = {(a,b), (a,c), (c,b)} lec 5M.3 Albert R Meyer, March 1, 2010 Formally, a digraph with vertices V is the same as a binary relation on V. lec 5M.4 Digraphs 2 Albert R Meyer, March 1, 2010 Graphical Properties of Relations Reflexive Transitive Symmetric Asymmetric NO lec 5M.6 Albert R Meyer, March 1, 2010 Graph of Strict Partial Order a b c e d f lec 5M.15 Albert R Meyer, March 1, 2010 how to check? • no self-loops i→i ∉ E (irreflexive) • if edges i→j and j→k then shortcut edge i→k is there too (transitive) Graph of Strict Partial Order lec 5M.16 Albert R Meyer, March 1, 2010 Cycles A cycle is a positive length directed path that starts and ends at the same vertex. simple cycle: each vertex only once, except start = end lec 5M.17 3 Albert R Meyer, March 1, 2010 Directed Cycle … v0 v1 v2 vn-1 v0 v0 vi vi+1 lec 5M.18 Albert R Meyer, March 1, 2010 by asymmetry: if there is a path from a to b, graph has no cycle Graph of Strict Partial Order a directed acyclic graph DAG then there is none from b to a lec 5M.19 Albert R Meyer, March 1, 2010 Graph of Strict Partial Order strict p.o. implies DAG, but not every DAG is strict p.o. not transitive also need these edges lec 5M.20 Albert R Meyer, March 1, 2010 Strict P.O. from a DAG but from any DAG, get a strict p.o. by adding “transitive” edges: if there is a path in the DAG, add an edge from start to end: b a d c lec 5M.21 4 Albert R Meyer, March 1, 2010 Positive Path Relation aR+b iff there is a nonzero directed path from a to b relation R on a set V aRv1Rv2RRb lec 5M.22 Albert R Meyer, March 1, 2010 DAG's & Partial Orders Theorem: • The graph of a strict partial order is a DAG. • The positive path relation of a DAG is a strict partial order. lec 5M.23 Albert R Meyer, March 1, 2010 Graph of Strict Partial Order a b c e d f what is smallest DAG whose paths define this partial order? lec 5M.24 Albert R Meyer, March 1, 2010 Covering Edges a b c e d f lec 5M.25 unneeded edges covering edges e.g. any path from c to d must traverse c→d 5 Albert R Meyer, March 1, 2010 Problems 1 -3 lec 5M.26 MIT OpenCourseWare http://ocw.mit.edu 6.042J /18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.