第四章关系和有向图10月23日周四讲稿..docVIP

第四章 关系和有向图Relations and Digraphs 4.4关系的性质Properties of Relations 自反和反自反关系Reflexive and Irreflexive Relations 自反关系Reflexive Relations 关系R?A?A, ?a?A,(a,a)?R IA,P是自反关系。 反自反关系 Irreflexive Relations 关系R?A?A, ?a?A,(a,a)?R Q是反自反关系。 对称Symmetric，不对称 asymmetric，反对称antisymmetric Relations关系 对称Symmetric， (a,b)∈R?(b,a)∈R 不对称 asymmetric， (a,b)∈R?(b,a)?R 反对称antisymmetric (a,b)∈R ∧ (b,a)∈R ? a=b 传递 Transitive (a,b)∈R ∧ (b,c)∈R ? (a,c)∈R. 大于等于，小于等于，恒等，整除关系都是传递关系。 定理1.关系R是传递的当且仅当Rn?R, 即如果a,b有长度大于1的边则有长度为1的边。 定理2. R是A上关系,则 R自反 则?a?A, a∈R(a). R对称 则 a∈R(b) iff b∈R(a) R传递 则 b∈R(a), c∈R(b) ? c∈R(a). 偏序关系Partial Order 1.自反 Reflexive ?a?A, (a,a)?R 2．反对称antisymmetric (a,b)∈R ∧ (b,a)∈R ? a=b 3．传递Transitive (a,b)∈R ∧ (b,c)∈R ? (a,c)∈R. 大于等于，小于等于，恒等，整除关系都是偏序关系。（A, ?）集合对于?是偏序。 树是偏序。 全序关系，线性序关系linear order 偏序1.2.3.＋ 4． ?a,b?A,(a,b)?R∨(b,a)∈R. 大于等于，小于等于是全序，整除，（A, ?）不是。 严格序strict order 1.反自反 irreflexive 2.传递 transitive 严格线性序strict linear order 严格序＋ 4’． ?a,b?A,(a,b)?R∨a=b∨(b,a)∈R. 大于，小于都是严格线性序。 Homework P127-128 10,12,14,20,26,30,32 4.5等价关系 Equivalence Relations 等价关系R是A上关系，满足： 1．自反 2．对称 3．传递 恒等IA是等价关系 三角形全等，三角形相似是等价关系 集合基数相等是等价关系 Z上同余关系是等价关系 n∈Z+, a,b∈Z, a≡b(n) iff n|(a-b), 或 a%n=b%n 等价关系与划分 定理1. 设P是集合A的一个划分，定义A上关系R: a R b 当且仅当a,b属于P的同一分块 则R是等价关系。 引理1 设R是A上等价关系，则 a R b当且仅当 R(a)=R(b) 证明 设R(a)=R(b)，则b∈R(a), 因此a R b 反之 ?c?A, 设c∈R(a)，则 a R c,由对称性，c R a. 由a R b，传递性有c R b. 因此c∈R(b).于是 R(a)?R(b). 同理有R(b)?R(a). 从而R(a)＝R(b)。 引理2 设R是A上等价关系，则 R(a)∩R(b)≠?当且仅当 R(a)=R(b) 证明 存在c∈R(a)∩R(b)，aRc,cRb. 由传递性aRb, 由引理1 R(a)=R(b)。 定理2 设R是A上等价关系， P＝{R(x)|x∈A}， 则P是A的一个划分。且划分P确定的等价关系是R. 证明. ?a?A, a∈R(a)，A=∪P=R(a), 由引理1，2，R(a)∩R(b)=? 或R(a)＝R(b)。 因此P是A的一个划分。 a,b属于P的同一分块，a,b∈R(x),则aRb. P确定的等价关系就是R. 称R(a)为a的等价类。 也用[a]表示。 划分P也记作A/R， Z关于n的同余关系的划分 记作Zn=Z/(n)={[0],[1],…，[n-1]}={0,1,2,……，n-1}. [a]+[b]=[a+b], [a]×[b]=[a×b]. Homework p132-133 12,20,16,24 4.6关系和图的计算机表示Computer Representation of Relations and Digraphs 4.7关系的运算Operations on Relations 设R和S