slides33

  • 格式:pdf
  • 大小:1.51 MB
  • 文档页数:5

L3-3.2Copyright © Radhika Nagpal, 2002.Partial OrderTwo students are related to each otherif one is shorter and younger thanthe other(s1, a1) R(s2, a2)iff(s1≤s2) ∧(a1≤a2)–Reflexive–Antisymmetric–TransitiveL3-3.3Copyright © Radhika Nagpal, 2002.Partial OrderTransitive:Prove (s1, a1) R(s2, a2)and (s2, a2) R(s3, a3)implies (s1, a1) R(s3, a3) :(s1≤s2≤s3)and (a1≤a2≤a3)Therefore (s1≤s3)and (a1≤a3)If we line up the students in a chain in order ofIf we line up the students in an antichainorder ofOlderL3-3.7Copyright © Radhika Nagpal, 2002.Normal Person’s Graph xyy = f(x)L3-3.8Copyright © Radhika Nagpal, 2002. Computer Scientist’s Graphafecdbedge (e ,a )L3-3.9Copyright © Radhika Nagpal, 2002.DefinitionA Graph is a set of vertices V and a set E of edges, such thatSo E is simply a binary relationon the set V.VV E ×⊆L3-3.10Copyright © Radhika Nagpal, 2002.Relations and GraphsA = {a,b,c,d}R = {(a,b) (a,c) (c,b)}acbdProperties of RelationsReflexiveTransitiveSymmetricAntisymmetricNOTypes of RelationsTotal Order (<)132456Equivalence (mod 3)164352Partial Order(a |b)123546L3-3.13Copyright © Radhika Nagpal, 2002.A Relation on Buildingsa Rb ::= Building a is “physicallyadjacent” to Building bA B CA R B,B R A not A RC A R AL3-3.14Copyright © Radhika Nagpal, 2002.MIT Building ConnectionsR4131012268L3-3.15Copyright © Radhika Nagpal, 2002.Class Problem 1R4131012268L3-3.16Copyright © Radhika Nagpal, 2002.MIT Building Connections413101241310124131012R 2= {(a,b) | a,b areconnected by path of length 2}R 3= {(a,b) | a,b are connected by a path of length 3}Composition and Path Lengths R k is the set of all pairs (a,b ) suchthat a and b are connected by a path of length exactly k.Composition and Path LengthsIf R is not reflexiveIf R is reflexive and transitiveRR 2RR 2L3-3.19Copyright © Radhika Nagpal, 2002.The Same QuestionsQuestion 1:Can you drive from one state to another with at most 5state-boundary crossings ?C ×C =R 0∪R 1∪⋅⋅⋅∪R 5?Question 2:Can you fly on KLM from Boston toParamaribo with at most 3stopovers ?(BOS, PAR ) ∈R 0∪R 1 ∪⋅⋅⋅∪R 4 ?Quiz:Paramaribo is the capital of …?L3-3.20Copyright © Radhika Nagpal, 2002.ConnectivityIs it possible at all to get from bldg a to b ?Is there a path of some length k from a to b ?(a, b )∈? =R n-1Why n-1?R is reflexive and …0k k R ∞=∪L3-3.21Copyright © Radhika Nagpal, 2002. Connectivity…the greatest distance between any pair of nodes is n-1:If longer than n -1can remove cycleL3-3.22Copyright © Radhika Nagpal, 2002.Reflexive Transitive ClosureR *::=k k R ∞=∪= R 0 ∪R 1∪R 2 ∪⋅⋅⋅∪R k ∪⋅⋅⋅dI aka the Connectivity RelationBoolean Matrix RepresentationA = {a,b,c,d}R = {(a,b) (a,c) (c,b)}acbda b c da 0 11 0b 0 0 0 0c 0 1 0 0d 0 0 0 0Boolean Matrix Operationse.g R = A×A –R(all pairs not in R)a b c d a 0 1 10b 0 0 0 0c 0 1 0 0d 0 0 0 0a b c da 1 0 01b 1 1 1 1c 1 0 1 1d 1 1 1 1L3-3.25Copyright © Radhika Nagpal, 2002.Composition using Matrices1a 0 1 1 00 0 0 01 0 0 00 0 0 1R2a 3a 4a 1b 2b 3b 4b 1c 2c 3c 4c 1b 2b 3b 4b 00 0 010 0 000 1 000 0 1S=T ::= R )S10 1 00 0 0 00 0 0 00 0 0 11a 2a 3a 1c 2c 3c 4a 4c T (a 1,c 1) = [R (a 1,b 1)∧S (b 1,c 1)] ∨[R (a 1,b 2)∧S (b 2,c 1)] ∨[R (a 1,b 3)∧S(b 3,c 1)] ∨[R (a 1,b 4)∧S (b 4,c 1)]L3-3.26Copyright © Radhika Nagpal, 2002. Class ProblemsL3-3.27Copyright © Radhika Nagpal, 2002.MIT Building Connections812101326441310122688121013264CRC RL3-3.28Copyright © Radhika Nagpal, 2002.MIT Building Connections3R 2R 4131012268R41310122684131012268。