展开查看详情
1.Digraphs and Relations 3/4/12 1
2.Walks in digraph G walk from u to v and from v to w implies walk from u to w u v w 3/4/12 2
3.Walks in digraph G walk from u to v and from v to w , implies walk from u to w : u G + v AND v G + w IMPLIES u G + w 3/4/12 3
4.Walks in digraph G transitive r elation R : u R v AND v R w IMPLIES u R w G + is transitive 3/4/12 4
5.Theorem: R is a transitive iff R = G + for some digraph G transitivity 3/4/12 5
6.G + is the transitive closure of the binary relation G Transitive Closure 3/4/12 6
7.reflexivity relation R on set A is reflexive iff a R a for all a ∈ A ≤ on numbers and ⊆ on sets are reflexive 3/4/12 7
8.reflexivity For any digraph G, G * is reflexive 3/4/12 8
9.G * is the reflexive transitive closure of the binary relation G Reflexive Transitive Closure 3/4/12 9
10.two-way walks If there is a walk from u to v and a walk back from v to u then u and v are s trongly connected . u G * v AND v G * u 3/4/12 10
11.symmetry relation R on set A is symmetric iff a R b IMPLIES b R a 3/4/12 11
12.Paths in DAG D path from u to v implies no path from v to u unless u = v u D * v and u≠v IMPLIES NOT ( v D * u ) 3/4/12 12
13.antisymmetric relation R : u R v IMPLIES NOT ( v R u ) for any u ≠ v If D is a DAG then D * is antisymmetric antisymmetry 3/4/12 13
14.(weak) partial orders Reflexive, Transitive, and A ntisymmetric examples: ⊆ is (weak) p.o . on sets ≤ is (weak) p.o . on 3/4/12 14
15.Theorem: R is a W PO iff R = D * for some DAG D weak partial orders 3/4/12 15
16.transitive, symmetric & reflexive equivalence relations 3/4/12 16
17.Theorem: R is an equiv rel iff R = the strongly connected relation of some digraph equivalence relations 3/4/12 17
18.examples: = (equality) same size sibling (same parents) equivalence relation 3/4/12 18
19.Equivalence Relation An equivalence relation decomposes the domain into subsets called equivalence classes where aRb iff a and b are in the same equivalence class I n the digraph of an equivalence relation, all the members of an equivalence class are reachable from each other but not from any other equivalence class 3/4/12 19
20.Graphical Properties of Relations Reflexive Transitive Symmetric 3/4/12 20 Equivalence Relation
