有向图及其关系

本文主要介绍了 有向图及其关系。通过例子来说明,例如有向图G中的走势。从u到v,从v到w,意味着从U走到W。 本文还介绍了等价关系,并举例说明。
展开查看详情

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

21.Finis 3/4/12 21