Chap4RelationsandDigraphs.ppt

1、Chapter 4 Relations and Digraphs,Weiqi Luo (骆伟祺) School of Software Sun Yat-Sen University Email： Office：A309,4.1 Product Sets and Partitions 4.2 Relations and Digraphs 4.3 Paths in Relations and Digraphs 4.4 Properties of Relations 4.5 Equivalence Relations 4.6 Data structures for Relations and Dig

2、raphs 4.7 Operations on Relations 4.8 Transitive Closure and Warshalls Algorithm,2,Chapter Four: Relations and Digraphs,Ordered pair An order pair (a, b) is a listing of objects a and b in a prescribed order, which a appearing first and b appearing second (a,b) = (c,d) a=c and b=d Product set If A a

3、nd B are two nonempty sets, we define the product set or Cartesian product A B as the set of all ordered pairs (a, b) with a A and b B. Thus A B = (a, b) | a A and b B,4.1. Product Sets and Partitions,3,Example 1 if x in A2 . y R(A2). In either cases, y R(A1) U R(A2) , therefore R(A1 U A2 ) R(A1) U

4、R(A2) (2) R(A1) U R(A2) R(A1 U A2 ) A1 A1 U A2 , then R(A1) R(A1 U A2 ) A2 A1 U A2 , then R(A2) R(A1 U A2 ) Thus R(A1) U R(A2) R(A1 U A2 ) Therefore, we obtain R(A1 U A2 ) = R(A1) U R(A2),4.2 Relations and Digraphs,26,(c) R (A1 A2) R(A1) R(A2) Proof: If y R (A1 A2 ) , then x R y for some x in A1 A2,

5、 since x is in both A1 and A2 , it follows that y is in both R(A1) and R(A2) ; that is, y R(A1 ) R(A2). Therefore R (A1 A2) R(A1) R(A2) Note: R(A1) R(A2) R (A1 A2),4.2 Relations and Digraphs,27,Example 15 Let A=Z, R be “” A1=0,1,2 and A2=9,13. Then R(A1) consists of all integers n such that 0 n, or

6、1 n, or 2 n, thus R(A1) =0, 1, 2,. Similarly R(A2)=9, 10, 11, so R(A1) R(A2)= R(A2)=9,10,11, On the other hand, A1 A2 = , therefore, R (A1 A2 ) = This shows that R(A1 ) R(A2) R (A1 A2 ),4.2 Relations and Digraphs,28,Theorem 2 Let R and S be relations from A to B, If R(a) =S(a) for all a in A, then R

7、=S Proof: If a R b, then b R(a). Therefore, b S(a) and a S b. A completely similar argument shows that, if a S b, then a R b. Thus R=S.,4.2 Relations and Digraphs,29,The matrix of a Relation If A=a1,a2, am and B=b1,b2,bn are finite sets containing m and n elements, respectively, and R is a relation

8、from A to B, we represent R by the mn matrix MR =mij, which is defined by mij = 1 if (ai bj) R = 0 otherwise The matrix MR is called the matrix of R.,4.2 Relations and Digraphs,30,Example 17 Let A =1, 2, 3 and B=r, s. Then we define R=(1, r), (2, s), (3, r) is a relation from A to B. Then the matrix

9、 of R is,4.2 Relations and Digraphs,31,Consider the matrix Since M is 34, we let A=a1,a2,a3 and B=b1,b2,b3,b4 Then (ai,bj) in R if and only if mij=1, thus R=(a1,b1),(a1,b4),(a2,b2),(a2,b3),(a3,b1),(a3,b3,4.2 Relations and Digraphs,32,The Digraph of a Relation If A is a finite set, R is a relation on

10、 A (from A to A) 1) Draw a small circle for each element of A and label the circle with the corresponding element of A (Vertices) 2) Draw an arrow from vertex ai to vertex aj if and only if ai R aj (Edge) The resulting pictorial representation of R is called a directed graph or digraphy of R.,4.2 Re

11、lations and Digraphs,33,Example 19 Let A=1, 2, 3, 4 R=(1,1), (1,2), (2,1), (2,2), (2,3), (2,4), (3,4), (4,1),4.2 Relations and Digraphs,34,Example 20 Find the relation determined by the following Figure. R= (1,1), (1,3), (2,3), (3,3), (3,2), (4,3) ,4.2 Relations and Digraphs,35,In-/Out- Degree If R

12、is a relation on a set A, and a in A, then The in-degree of a relative to the relation R is the number of b in A such that (b,a) in R. The out-degree of a is the number of b in A such that (a,b) in R,4.2 Relations and Digraphs,36,Example 22 Let A=a, b, c, d, and R be the relation on A that has the m

13、atrix Construct the digraph of R, and list the in-degrees and out-degrees of all vertices,4.2 Relations and Digraphs,37,In-degree,Out-degree,If R is a relation on a set A, and B is a subset of A, the restriction of R to B is R (BB) Example 24 Let A=a,b,c,d,e,f, R=(a,a), (a,c), (b,c), (a,e), (b,e), (

14、c,e). Let B=a,b,c, then BB=(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c) and the restriction of R to B is (a, a), (a, c), (b, c),4.2 Relations and Digraphs,38,Homework Ex. 2, Ex. 8, Ex.12, Ex.20 Ex.24, Ex. 28, Ex. 32,4.2 Relations and Digraphs,39,Suppose that R is a relation on a set

15、 A. A path of length n in R from a to b is a finite sequence : a, x1, x2, , xn-1, b beginning with a and ending with b, such that a R x1, x1 R x2, ,xn-1 R b Note: A path of length n involves n+1 elements of A, although they are not necessarily distinct.,4.3 Paths in Relations and Digraphs,40,Example

16、 1 Consider the digraph in the following figure. Then 1: 1, 2, 5, 4, 3 is a path of length 4 from vertex 1 to 3 2: 1, 2, 5, 1 is a path of length 3 from vertex 1 to itself 3: 2, 2 is a path of length 1 from vertex 2 to itself Cycle: a path that begins and ends at the same vertex (2 3 ),4.3 Paths in

17、Relations and Digraphs,41,If n is a fixed positive integer, we define a relation Rn on A as follows: x Rn y means that there is a path of length n from x to y in R Define a relation R on A, by letting x R y mean that there is some path in R from x to y. The length of such a path will depend on x and

18、 y. The relation R is sometimes called the connectivity relation for R. Rn(x) consists of all verities that can be reached form x by means of a path in R of length n. The set R (x) consists of all vertices that can be reached from x by some path in R,4.3 Paths in Relations and Digraphs,42,Example 2

19、Let A be the set of all living human beings R be the relation of mutual acquaintance a R b means that a and b know one another a R2 b means that a and b have an acquaintance in common a Rn b if a knows someone x1, who knows x2, , who knows xn-1, who knows b. a R b means that some chain of acquaintan

20、ces exists that begins at a and ends at b. Q: It is interesting (and unknown) whether every two Americans, say, are related by R,4.3 Paths in Relations and Digraphs,43,Example 3 Let A be a set of cities x R y if there is a direct flight from x to y on at least one airline. x Rn y if one can book a f

21、light from x to y having exactly n-1 intermediate stops x R y if one can get from x to y by plane,4.3 Paths in Relations and Digraphs,44,Example 5 Let A=a,b,c,d,e and R=(a,a), (a,b), (b,c), (c,e), (c,d), (d,e) Compute (a) R2 (b) R ,4.3 Paths in Relations and Digraphs,45,R,Compute R2 a R2 a since a R

22、 a and a R a a R2 b since a R a and a R b a R2 c since a R b and b R c b R2 e since b R c and c R e b R2 d since b R c and c R d c R2 e since c R d and d R e Hence R2 =(a,a), (a,b), (a,c), (b,e), (b,d), (c,e),4.3 Paths in Relations and Digraphs,46,Compute R To compute R , we need all ordered pairs o

23、f vertices for which there is a path of any length from the first vertex to the second. We can see that from the figure,4.3 Paths in Relations and Digraphs,47,R,R = (a,a), (a,b), (a,c), (a,d), (a,e), (b,c),(b,d), (b,e), (c,d), (c,e), (d,e) .,Note: If |R| is large, it can be tedious and perhaps diffi

24、cult to compute R ,Boolean Matrix (p.37) A Boolean Matrix is an mn matrix whose entries are either 0 or 1. Let A=aij and B=bij be mn matrix Boolean matrix. The Join of A and B : A V B = C = cij cij=1 if aij=1 or bij=1 cij=0 otherwise The meet of A and B: A B = D = dij dij=1 if aij and bij are both 1

25、 dij=0 otherwise,4.3 Paths in Relations and Digraphs,48,Boolean Product (p.38) A = aij is an mp Boolean matrix and B = bij is a pn Boolean matrix. The Boolean product of A and B, denoted AB, is the m n Boolean matrix C=cij defined by,4.3 Paths in Relations and Digraphs,49,Example Let then,4.3 Paths

26、in Relations and Digraphs,50,Theorem 5 (p. 39) 1. (a) A V B= B V A (b) A B = B A 2. (a) (A V B) V C = A V (B V C) (b) (A B) C = A (B C) 3. (a) A ( B V C) = (A B) V (A C) (b) A V (B C) = (A V B) (A V C) 4. (A B) C = A (B C),4.3 Paths in Relations and Digraphs,51,Theorem 1 If R is a relation on A=a1,a

27、2,an, then Proof: Let MR=mij and MR2 =nij. By definition, the i, j-th element of MR MR is equal to 1 if only if row i of MR and column j of MR has a 1 in the same relative position, say position k. This means that mik=1 and mkj=1 for some k, 1 k n. By definition of matrix MR, the preceding condition

28、s mean that ai R ak, and ak R aj. Thus ai R2 aj, and so nij=1. Therefore, position i, j of MR MR is 1 if and only if nij=1.,4.3 Paths in Relations and Digraphs,52,Example 6 Let A and R be as in Example 5. Then,4.3 Paths in Relations and Digraphs,53,Theorem 2 For n 2 and R is a relation on a finite s

29、et A, we have Proof by Mathematical Induction (refer to p.138-139 for more details),4.3 Paths in Relations and Digraphs,54,4.3 Paths in Relations and Digraphs,55,If R and S are relations on A. the relation R U S is defined by x (R U S) y if and only if x R y or x R y. It is easy to verify that MRUS

30、=MR V MS,The Reachability relation R* of a relation on a set A that has n elements is defined as follows: x R* y means that x=y or x R y,4.3 Paths in Relations and Digraphs,56,Composition Let 1 = a, x1, x2, , xn-1,b be a path in relation R of length n form a to b, and 2 = b, y1, y2, , ym-1,c be a pa

31、th in relation R of length m form b to c, then the composition of 1 and 2 is the path a, x1, x2, , xn-1,b y1, y2, , ym-1,c of length n+m denoted by 2 O 1,4.3 Paths in Relations and Digraphs,57,Consider the relation whose digraph is given in the following figure and the paths 1 = 1, 2, 3 and 2 = 3, 5

32、, 6, 2, 4 Then the composition of 1 and 2 is the path 2 O 1 : 1, 2, 3, 5, 6, 2, 4 from 1 to 4 of length 6,4.3 Paths in Relations and Digraphs,58,Homework Ex. 2, Ex. 6, Ex. 12, Ex. 18, Ex. 20, Ex. 26,4.3 Paths in Relations and Digraphs,59,Reflexive therefore, b in R(a), so a R b,4.5 Equivalence Relat

33、ions,91,Conversely, suppose that a R b, then (1) b in R(a) by definition. Therefore, since R is symmetric (2) a in R(b) by theorem 2 (b) of Section 4.4. To prove R(a)=R(b) First, we choose x in R(b), since R is transitive, the fact x in R(b) with b in R(a) (1) , implies by Theorem 2(c) of Section 4.

34、4 that x in R(a). Thus, R(b) R(a) Second, support y in R(a). This fact and a in R(b) (2) imply. As before, that y in R(b). Thus R(a) R(b) Therefore, we have R(a) = R(b) The Lemma proved.,4.5 Equivalence Relations,92,Theorem 2 Let R be an equivalence relation on A, and let P be the collection of all

35、distinct relative sets R(a) for a in A. Then P is a partition of A, and R is the equivalence relation determined by P. Proof: According to the definition of a partition, we should show the two following properties (a) Every element of A belongs to some relative set (b) If R(a) and R(b) are not ident

36、ical, then R(a) R(b) = ,4.5 Equivalence Relations,93,Property (a) is true, since a R(a) (reflexivity) Property (b) is equivalent to the following statement If R(a) R(b) , then R(a) = R(b) (p59 Theorem 2 b) Assume c R(a) R(b), then a R c, b R c. then we have c R b (symmetric) a R c, c R b a R b (tran

37、sitivity) Therefore, R(a) = R(b) (by lemma 1),4.5 Equivalence Relations,94,Equivalence classes If R is an equivalence relation on A, then the sets R(a) (or a) are traditionally called equivalence classes of R. The partition P constructed in Theorem 2 consists of all equivalence classes of R, and thi

38、s partition will be denoted by A/R. (the quotients set of A),4.5 Equivalence Relations,95,Example 7 Let A=1,2,3,4 and let R=(1,1),(1,2), (2,1), (2,2), (3,4), (4,3), (3,3), (4,4) Determine A/R Solution: R(1) = 1, 2 = R(2) , R(3) = 3, 4 = R(4) Hence A/R = 1,2 , 3,4,4.5 Equivalence Relations,96,Example

39、 8 Let A=Z and let R= (a, b) AA | a and b yield the same remainder when divided by 2. Solution: First R(0)=,-4,-2,0,+2,+4, the set of even integers, since the remainder is zero when each of these numbers is divided by 2. R(1) = , -3,-1,0,+1,+3, , the set of odd integers, since the remainder is 1 whe

40、n divided by 2. Hence, A/R consists of the even integers and the set of odd integers.,4.5 Equivalence Relations,97,The procedure of determining A/R is as follows: Support A=a1,a2, (finite or countable) Step 1: i=0; j=0; Step 2: i=i+1; Step 3: if ai A, then j=j+1; bj=ai and compute the equivalence cl

41、ass R(bj ), A= A- R(bj) Step 4: if A become an empty set, then we obtain the equivalence classes R(b1), R(b2), R(bj) (Note: j may be finite or infinite) otherwise repeat step 2 4,4.5 Equivalence Relations,98,Homework Ex. 4, Ex. 12, Ex. 14, Ex. 20, Ex. 23, Ex. 28,4.5 Equivalence Relations,99,Let R an

42、d S be relations from a set A to a set B R and S are subsets of AB. We can use set operations on the relations R and S Relations: (three representations) 1. the set of ordered pairs (finite or infinite) 2. digraph (finite) 3. matrix (finite),4.7 Operations on Relations,100,Complementary relation if

43、and only if a R b The intersection R S a (R S) b means that a R b and a S b The union R U S a (R U S) b means that a R b or a S b,4.7 Operations on Relations,101,Inverse Let R be a relation from A to B, the relation R-1 is a relation from B to A (reverse order from R) denoted by b R-1 a if and only

44、if a R b Note: (R-1) -1=R Dom(R-1) = Ran (R) Ran(R-1) = Dom(R),4.7 Operations on Relations,102,Example 1 Let A=1,2,3,4 and B= a,b,c. We Let R=(1,a), (1,b), (2,b),(2,c),(3,b),(4,a) and S= (1,b),(2,c),(3,b),(4,b) Compute: (a) (b) R S (c) R U S (d) R-1 Solution: AB = (1,a), (1,b), (1,c), (2,a), (2,b),

45、(2,c), (3,a), (3,b), (3,c), (4,a), (4,b), (4,c) ,4.7 Operations on Relations,103,Example 1 RS = (1,b), (3,b), (2,c) RS = (1,a), (1,b), (2,b), (2,c), (3,b), (4,a), (4,b) R-1= (a,1), (b,1), (b,2), (c,2), (b,3), (a,4) ,4.7 Operations on Relations,104,Example 2 Let A=R. Let R be the relation on A and le

46、t S be Then the complement of R is the relation , since a b means ab Similarly, the complement of S is the relation . On the other hand, R-1=S, since for any number a and b a R-1 b if and only if b R a if and only if b a if and only if a b if and only if a S b R S : “=” R U S : AA,4.7 Operations on

47、Relations,105,Example 3 R= (a,a), (b,b), (a,c), (b,a), (c,b), (c,d), (c,e), (c,a), (b,d), (d,a), (d,e), (e,b), (e,a), (e,d), (e,c) R-1= (b,a), (e,b), (c,c), (c,d), (d,d), (d,b), (c,b), (d,a), (e,e), (e,a) RS = (a b), (b e) (c c) ,4.7 Operations on Relations,106,Example 4,4.7 Operations on Relations,

48、107,Operations on Boolean Matrix,4.7 Operations on Relations,108,Theorem 1 Suppose that R and S are relations from A to B (a) If R S, then R-1 S-1. (b) If R S, then S R (c) (RS) -1 =R -1 S -1 and (R U S) -1 = R -1 U S -1 (d) (RS) = R U S and R U S = R S,4.7 Operations on Relations,109,Theorem 2 Let

49、R and S be relations on a set A (a) If R is reflexive, so is R-1 (b) If R and S are reflexive, then so are RS and R U S (c) R is reflexive if and only if R is irrflexive,4.7 Operations on Relations,110,Example 5 Let A=1,2,3 and consider the two reflexive relations R = (1,1), (1,2), (1,3), (2,2), (3,

50、3) S = (1,1), (1,2), (2,2), (3,2), (3,3) then R-1 = (1,1), (2,1), (3,1), (2,2), (3,3) . R and R-1 are both reflexive. R= (2,1), (2,3), (3,1), (3,2) is irreflexive while R is reflexive. RS = (1,1), (1,2), (2,2), (3,3) (reflexive) RS = (1,1), (1,2), (1,3), (2,2), (3,2), (3,3) (reflexive),4.7 Operation

51、s on Relations,111,Theorem 3 (Homework Ex. 37) Let R be a relation on a set A. Then (a) R is symmetric if and only if R=R-1 (b) R is antisymmetric if and only if R R -1 (c) R is asymmetric if and only if R R -1 = ,4.7 Operations on Relations,112,Theorem 4 Let R and S be relations on A (a) If R is sy

52、mmetric, so are R-1 and R (b) If R and S are symmetric, So R S and R U S,4.7 Operations on Relations,113,Example 6 Let A=1,2,3 and consider the symmetric relations R = (1,1), (1,2), (2,1), (1,3), (3,1) S = (1,1), (1,2), (2,1), (2,2), (3,3) then (a) R-1 = (1,1), (2,1), (1,2), (3,1), (1,3) (symmetric)

53、 R = (2,2), (2,3), (3,2), (3,3) (symmetric) (b) RS = (1,1), (1,2), (2,1) (symmetric) RS = (1,1), (1,2), (1,3), (2,1), (2,2), (3,1), (3,3) (symmetric),4.7 Operations on Relations,114,Theorem 5 Let R and S be relations on A (a) (R S )2 R2 S2 (b) If R and S are transitive, so is R S (c) If R and S are

54、equivalence relations, so is R S,4.7 Operations on Relations,115,Closure If R is a relation on a set A, and R lacks some relational properties (e.g. reflexivity, symmetry and transitivity) . We try to add as few new pairs as possible to R, so that the resulting relation R1 has the property we desire

55、d. If R1 exists, we call it the closure of R with the respect to the property in question.,4.7 Operations on Relations,116,Example 8 Support that R is a relation on A, and R is not reflexive. R1=R is the smallest reflexive relation on A containing R. The reflexive closure of R is R. Example 9 Suppor

56、t that R is a relation on A, and R is not symmetric. R1 =RR-1 is the smallest symmetric relation containing R. (Note: (RR-1)-1 = R-1R ),4.7 Operations on Relations,117,The symmetric closure of R R= (a,b), (b,c), (a,c), (c,d) RR-1= (a,b), (b,a) ,(b,c), (c,b), (a,c), (c,a), (c,d), (d,c),4.7 Operations

57、 on Relations,118,Composition Support A, B and C are sets, R is a relation from A to B, and S is a relation from B to C, the composition of R and S, written SoR is a relation from A to C If a is in A and c is in C, then a SoR c if and only if for some b in B, we have a R b, and b S c.,4.7 Operations

58、 on Relations,119,R,S,SoR,Example 10 Let A= 1,2,3,4 and R=(1,2), (1,1), (1,3), (2,4),(3,2) and S=(1,4), (1,3), (2,3),(3,1), (4,1). Since (1,2) in R, (2,3) in S, we must have (1,3) in SoR Similarly, we have SoR = (1,4), (1,3), (1,1),(2,1), (3,3),4.7 Operations on Relations,120,Theorem 6 Let R be a relation from A to B and let S be a relation from B to C. Then if A1 is any subset of A, we have (SoR)(A1)= S(R(A1) ) Proof: by the definition of composition and relative