离散数学_.ppt

Chapter 8 Relations §8.1 Relations and their properties (1) 8.1.1 The concept of relation §8.1 Relations and their properties (2) §8.1 Relations and their properties (3) §8.1 Relations and their properties (4) §8.1 Relations and their properties (5) §8.1 Relations and their properties (6) §8.1 Relations and their properties (7) §8.1 Relations and their properties (9) §8.2 N-ary Relations and  Their Applications (1) §8.2 N-ary Relations and  Their Applications (2) §8.2 N-ary Relations and  Their Applications (3) §8.2 N-ary Relations and  Their Applications (4) §8.2 N-ary Relations and  Their Applications (5) §8.3 Representing relations (1) §8.3 Representing relations (1) §8.3 Representing relations (2) §8.4 Closures of Relations (11) 8.4.3 Warshall’s algorithm Computing Wk from Wk-1: Step1:First transfer to Wk all 1’s in Wk-1. Step2:List the location p1,p2,…,in column k of Wk-1,where the entry is 1,and the locations q1,q2,…,in row of Wk-1,where the entry is 1. Step3:Put 1’s in all the positions pi,qj of Wk. §8.4 Closures of Relations (12) 8.4.3 Warshall’s algorithm W:=MR; For i=1 to n Begin For j=1 to n If W[j,i]=1 Then for k=1 to n W[j,k]:=W[j,k]+W[i,k]; End Print W; §8.5 Equivalence relations (1) 8.5.1 The concept of equivalence relations Definition： A relation on a set A is called equivalence relation if it is reflexive,symmetric,and transitive. §8.5 Equivalence relations (2) 8.5.1 The concept of equivalence relations Example：A={1,2,3,…,10} R3={(a,b)|(a-b)/3?整数} §8.5 Equivalence relations (3) 8.5.2 Equivalence classes Definition： Let R be an equivalence relation on a set A.The set of all elements that are related to an element a of A is called the equivalence class of a.The equivalence class of a with respect to R is denoted by [a]R.