Mathematics for Computer Science

9.5. Directed Acyclic Graphs & Scheduling 333 The time it takes to schedule tasks, even with an unlimited number of processo ...

Chapter 9 Directed graphs & Partial Orders334 Theorem 9.5.8.A minimum time schedule for a finite DAGDconsists of the sets A ...

9.6. Partial Orders 335 Corollary 9.5.13.Every DAG withnvertices has a chain of size greater than p n or an antichain of size at ...

Chapter 9 Directed graphs & Partial Orders336 So we have Lemma 9.6.2.For any digraph,G, the walk relationsGCandGare transit ...

9.6. Partial Orders 337  ifx < yandy < zthenx < z, so less-than is transitive, and  NOT.x < x/, so less-than is ir ...

Chapter 9 Directed graphs & Partial Orders338 Definition 9.6.12. A binary relation,R, on a setA, isantisymmetriciff, for all ...

9.7. Representing Partial Orders by Set Containment 339 9.7 Representing Partial Orders by Set Containment Axioms can be a great ...

Chapter 9 Directed graphs & Partial Orders340 We leave the proof to Problem 9.29. Essentially the same construction shows th ...

9.10. Equivalence Relations 341 Definition 9.9.1.The product,R 1 R 2 , of relationsR 1 andR 2 is defined to be the relation wit ...

Chapter 9 Directed graphs & Partial Orders342  It is symmetric becausexy .modn/impliesyx .modn/.  It is transitive becau ...

9.11. Summary of Relational Properties 343 Theorem 9.10.4. The equivalence classes of an equivalence relation on a setA are the ...

Chapter 9 Directed graphs & Partial Orders344 AsymmetryRisasymmetricwhen 8 x;y 2 A: x R yIMPLIES NOT.y R x/: There is at mos ...

9.11. Summary of Relational Properties 345 Problems for Section 9.1 Exam Problems Problem 9.1. The proof of the Handshaking Lemm ...

Chapter 9 Directed graphs & Partial Orders346 (a)Prove the “iff” statement from left to right. (b)Prove the “iff” from right ...

9.11. Summary of Relational Properties 347 +0 +1 +0 +0 +1 +1 +1 00 11 10 01 +0 Figure 9.10 The 2-bit graph. mines your 3-good st ...

Chapter 9 Directed graphs & Partial Orders348 (b)Give an example of a digraph in which a vertexvis on an odd-length closed w ...

9.11. Summary of Relational Properties 349 Explain why there must be an edge not on the trail that starts or ends at a vertex on ...

Chapter 9 Directed graphs & Partial Orders350 Problem 9.10. There is a simple and useful way to extend composition of functi ...

9.11. Summary of Relational Properties 351 in Figure 9.11, three of the four chickens are kings. Chickencis not a king in this e ...

Chapter 9 Directed graphs & Partial Orders352 Problem 9.13. LetfA;:::;Hgbe a set of tasks that we must complete. The followi ...