展开查看详情
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
热门城市
