第四章關(guān)系和有向圖4.1-4.4

1、第四章 關(guān)系和有向圖Relations and Digraphs4.1乘積集合和劃分Product sets and Partions乘積集合Product sets A´B =(a,b) | aÎA, bÎB| A´B|=|A|´|B|A1´A2´´An = (a1, a2,an)| aiÎAi,i=1,2,n定理1.乘積集合對，滿足分配律A×(BC)=A×BA×CA×(BC)=A×BA×C(BC)×A=B×AC×

2、A(BC)×A=B×AC×A(AB)×(CD)A×CB×D劃分Partion or Quotient set of AA= A1A2An, Ai¹Æ , AiAj=Æ, i=1,2,n .Homework P105-106 17,264.2關(guān)系和有向圖Relations and Digraphs關(guān)系RÍA´B R稱為A到B上的關(guān)系, a Relation from A to B. RÍA´A R稱為A上的關(guān)系, a relation on A.(a,b) Î

3、;R, 也記作 aRb.例1 IA =(a,a)| aÎA 等于關(guān)系。例2 A=1,2,3,4, Q=(1,2), (1,3),(1,4),(2,3),(2,4),(3,4) Q是A上小于關(guān)系。例3 P= IA(1,2), (1,3), (1,4), (2,4), P是A上整除關(guān)系。由關(guān)系派生的集合Sets Arising from Relations定義域Dom(R) domain of R關(guān)系RÍA´BDom(R)=x| $yÎB, (x,y) ÎRDom(IA)=A, Dom(Q)=A-4, Dom(P)=A。值域Ran(R) range

4、 of RRan(R)= yÎB|$xÎA, (x,y) ÎR.Ran(IA)=A, Ran(A)=2,3,4, Ran(P)=1,2,3,4。A1的像集R(A1) ，x的像集R(x)關(guān)系RÍA´B, A1ÍA.R(A1)=yÎB| $xÎ A1, (x,y) ÎR, A1的像集，the R-relative set of A1.R(x)=yÎB| (x,y) ÎR, x的像集。定理1. 關(guān)系RÍA´B,A1ÍA, A2ÍA, (a) If A1

5、ÍA2, then R(A1)ÍR(A2).(b) R(A1A2) ÍR(A1)R(A2).(c) R(A1A2) Í R(A1)R(A2).定理2. 關(guān)系RÍA´B, SÍA´B. 如果"aÎA,R(a)=S(a), 則R=S.關(guān)系矩陣MR The Matrix of a Relation關(guān)系RÍA´B, 關(guān)系R的矩陣MR=mij， 關(guān)系圖The Digraph of a Relation關(guān)系RÍA´A, G=(V,E),定點集合V=A,邊集合E=R。1

6、11423A=1,2,3,4R=(1,1),(1,2),(2,1),(2,2),(2,3),(2,4), (3,4),(4,1)由關(guān)系確定矩陣和圖由矩陣確定關(guān)系由圖確定關(guān)系Homework P114-115 18,22,24,284.3關(guān)系和圖的路徑Paths in Relations and Digraphs長度為n的路徑a path of length n從a到b有長度為n的路徑：aRx1, x1Rx2, xn-1Rb，記做：a,x1,x2,xn-1,b.Rn 具有長度為n的路徑的關(guān)系關(guān)聯(lián)關(guān)系 R connectivity relation for RMR2= MRÄMR MRn

7、= MRÄ MRÄMRÄÄ MRMR¥= MRÅ MR2ÅMR3Å可達矩陣MR*= InÅMRÅ MR2ÅMR3Å兩條路徑的連接1：a1,a2,an,2：b1,b2,bm,b1=an12：a1,a2,an,b2,bm,Homework P120-1216,8,18,24,25,264.4關(guān)系的性質(zhì)Properties of Relations自反和反自反關(guān)系Reflexive and Irreflexive Relations自反關(guān)系Reflexive Relations關(guān)系

8、RÍA´A, "aÎA,(a,a)ÎRIA,P是自反關(guān)系。反自反關(guān)系 Irreflexive Relations關(guān)系RÍA´A, "aÎA,(a,a)ÏRQ是反自反關(guān)系。對稱Symmetric，不對稱 asymmetric，反對稱antisymmetric Relations關(guān)系對稱Symmetric，(a,b)RÞ(b,a)R不對稱 asymmetric，(a,b)RÞ(b,a)ÏR反對稱antisymmetric (a,b)R (b,a)R Þ a=b

9、傳遞 Transitive (a,b)R (b,c)R Þ (a,c)R.大于等于，小于等于，恒等，整除關(guān)系都是傳遞關(guān)系。定理1.關(guān)系R是傳遞的當(dāng)且僅當(dāng)RnÍR, 即如果a,b有長度大于1的邊則有長度為1的邊。定理2. R是A上關(guān)系,則(a) R自反 則"aÎA, aR(a).(b) R對稱 則 aR(b) iff bR(a)(c) R傳遞 則 bR(a), cR(b) Þ cR(a).偏序關(guān)系Partial Order1.自反 Reflexive "aÎA, (a,a)ÎR2反對稱antisymmetric(a,b)R (b,a)R Þ a=b3傳遞Transitive(a,b)R (b,c)R Þ (a,c)R.大于等于，小于等于，恒等，整除關(guān)系都是偏序關(guān)系。（A, Í）集合對于Í是偏序。樹是偏序。全序關(guān)系，線性序關(guān)系linear order偏序1.2.3.4 "a,bÎA,(a,b)ÎR(b,a)R.大于等于，小于等于是全序，整除，（A, Í）不是。嚴(yán)格序strict or