离散数学离散数学 (10).pdf

Computer Science&Technology0解：R1 R2=(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)R1 R2=(1,1)R1 R2=(2,2),(3,3)R2 R1=(1,2),(1,3),(1,4)R1 R2=(2,2),(3,3),(1,2),(1,3),(1,4)Computer Science&Technology1Computer Science&Technology2例：设集合 A=a,b,c，B=1,2,3,4,5，R 是集合 A上的关系，S 是A 到B上的关系R=,，S=,求解：R S，(R S)-1，R1，S1，S1 R1Computer Science&Technology3R-1=,S-1=,R S=,(R S)-1=,S1 R1=,(R S)-1=S1 R1Computer Science&Technology4111()R SSR证明：c,a(R S)-1 a,c R S bB,a,bR,b,cS bB,b,aR-1,c,bS-1 bB,c,bS-1,b,aR-1 c,a S-1 R-1Computer Science&Technology5Computer Science&Technology6Computer Science&Technology7Computer Science&Technology8Computer Science&Technology9自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R-1R1R2R1R2R1-R2R1R2若 R,R1,R2 是集合A的自反、对称、传递关系。证明每一个“”，为每个“”找个例证。Computer Science&Technology10自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性空关系空关系全关系全关系EA恒等关系恒等关系IA相似关系相似关系某些特殊关系所具有的性质。证明每一个“”，为每个“”找个例证。Computer Science&Technology11关系特性关系矩阵特征关系图特征自反性对角线元素全为1每个结点均有自回路反自反性对角线元素全为0每个结点均无自回路对称性矩阵对称两个不同的结点间若有边，则成对出现反对称性若1i，jn且ij，则aijaji=0两个不同的结点之间，至多有一条边，但允许是没有边传递性若有正整数kn使aikakj=1，则aij=1(从关系矩阵较难看出)若结点xi到xj有路，则xi到xj必有直达边AIR2RR1RRAIAIR 1RR证明是充要条件Computer Science&Technology12Computer Science&Technology13