1L4-2.1September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Mathematics for Computer ScienceMIT 6.042J/18.062JDAGs,Partial Orders,SchedulingL4-2.2September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Normal Person’s Graphxyy = f(x)L4-2.3September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Computer Scientist’s GraphafecdbL4-2.4September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Relations and Graphsset of vertices Vset of edges E, E ⊆ V × V(Formally the same asa binary relation on V.)acbdV={a,b,c,d} E = {(a,b), (a,c), (c,b)}L4-2.5September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Graphical Properties of RelationsReflexiveTransitiveSymmetricNOAntisymmetricL4-2.6September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.ARPaths2L4-2.7September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.AR= paths of length 1 R2from A to AR2= paths of length 2R≤2= paths of length≤2 L4-2.8September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Path Relationsa1and a2 are connected by path of length exactly k in the graph of Ra1Rka2iffa1R≤ka2iffa1and a2 are connected by path of length at most k in the graph of RL4-2.9September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Reflexive Transitive Closurea1R*a2iffa1and a2 are connected by pathL4-2.10September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Prerequisite Relation on Classesclass c is a prerequisite for class dc→dL4-2.11September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Some Course 6 Prerequisites• 18.01 → 6.042• 18.01 → 18.02• 18.01 → 18.03• 8.01 → 8.02• 6.001 → 6.034• 6.042 → 6.046• 18.03, 8.02 → 6.002• 6.001, 6.002 → 6.004 • 6.001, 6.002 → 6.003• 6.004 → 6.033• 6.033 → 6.857• 6.046 → 6.840L4-2.12September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Indirect Prerequisites18.01 is indirect prereq. of 6.84018.01 → 6.042 → 6.046 → 6.8403L4-2.13September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Classes with no prereqs"Freshman classes"18.01 6.0018.01d is a Freshman class iffnothing → dL4-2.14September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.d is minimal for →there is no c s.t. c→dMinimal elementsL4-2.15September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Prerequisite graph18.0218.016.0466.84018.036.0016.0346.0038.018.026.0026.0046.0336.8576.042L4-2.16September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.minimum means "smallest"-- a prereq. for every classno minimum in this exampleminimal not minimumL4-2.17September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Team ProblemProblem 1,2L4-2.18September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.What if there is a cycle in this graph?-- a path from class c to class d andback to class c?No one can graduate!Comm. on Curricula & Registrar aresupposed to prevent cycles.Prerequisite graph4L4-2.19September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Directed Acyclic Graph (DAG)18.0218.016.0466.84018.036.0016.0346.0038.018.026.0026.0046.0336.8576.042L4-2.20September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.DAG's = Partial OrdersTheorem:• The path relation of a DAG is a partial order.• The graph of a partial order is a DAG.L4-2.21September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.• 18.01 → 6.042• 18.01 → 18.02• 18.01 → 18.03• 8.01 → 8.02• 6.001 → 6.034• 6.042 → 6.046Constructing the DAG• 18.03, 8.02 → 6.002• 6.001, 6.002 → 6.004 • 6.001, 6.002 → 6.003• 6.004 → 6.033• 6.033 → 6.857• 6.046 → 6.840Identify Minimal ElementsL4-2.22September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Directed Acyclic Graph (DAG)18.01 6.0018.01L4-2.23September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.• 18.01 → 6.042• 18.01 → 18.02• 18.01 → 18.03• 8.01 → 8.02• 6.001 → 6.034• 6.042 → 6.046Constructing the DAG• 18.03, 8.02 → 6.002• 6.001, 6.002 → 6.004 • 6.001, 6.002 → 6.003• 6.004 → 6.033• 6.033 → 6.857• 6.046 → 6.840Remove minimal elementsL4-2.24September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.• 6.042• 18.02• 18.03• 8.02• 6.034• 6.042 → 6.046Constructing the DAG• 18.03, 8.02 → 6.002• 6.002 → 6.004 • 6.002 → 6.003• 6.004 → 6.033• 6.033 → 6.857• 6.046 → 6.840Remove minimal elements5L4-2.25September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.• 6.042• 18.02• 18.03• 8.02• 6.034• 6.042 → 6.046Constructing the DAG• 18.03, 8.02 → 6.002• 6.002 → 6.004 • 6.002 → 6.003• 6.004 → 6.033• 6.033 → 6.857• 6.046 → 6.840Identify new minimal elementsL4-2.26September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Directed Acyclic Graph (DAG)18.0218.0118.036.0016.0348.018.026.042continue in this way…L4-2.27September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Directed Acyclic Graph (DAG)18.0218.016.04618.036.0016.0348.018.026.0026.042L4-2.28September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Prerequisite graph18.0218.016.0466.84018.036.0016.0346.0038.018.026.0026.0046.0336.8576.042L4-2.29September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.Topological sort• Is there a way of graduating? (in any number of semesters?)• Yes - take a minimal remaining course each semesterL4-2.30September 28, 2005Copyright ©Albert R. Meyer and Ronitt Rubinfeld 2005. All rights reserved.How many terms to
View Full Document
Unlocking...