北京郵電大學計算機學院--離散數(shù)學--9.4-relations

1、9.4 Closures of Relations,2,2024/3/21,College of Computer Science & Technology, BUPT,Closures of Relations,DefinitionThe closure(閉包) of a relation R with respect to property P is the relation obtained by adding the

2、minimum number of ordered pairs to R to obtain property P.3 elements:R1 contains RR1 possesses the property PIf R2 contains R and possesses the property P, then R2 contains R1,3,2024/3/21,College of Computer Science

3、& Technology, BUPT,Closures of Relations,In terms of the digraph representation of RTo find the reflexive closure add loops.To find the symmetric closureadd arcs in the opposite direction.To find the transitive

4、closureif there is a path from a to b, add an arc from a to b.,4,2024/3/21,College of Computer Science & Technology, BUPT,Reflexive Closure,Theorem: Let R be a relation on A.The reflexive closure of R, denoted r(R

5、), is RÈD.Method:Add loops to all vertices on the digraph representation of R.Put 1’s on the diagonal of the connection matrix of R.,5,2024/3/21,College of Computer Science & Technology, BUPT,Symmetric closur

6、e,TheoremLet R be a relation on A. The symmetric closure of R, denoted s(R), is the relation RÈR-1.,6,2024/3/21,College of Computer Science & Technology, BUPT,Theorem,R is symmetric If and only ifR = R-1N

7、ote: in digraph of a symmetric relation, use undirected edges instead of arcs,7,2024/3/21,College of Computer Science & Technology, BUPT,Example,8,2024/3/21,College of Computer Science & Technology, BUPT,Paths,Su

8、ppose that R is a relation on a set 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 thata R x1, x1 R x2, ..., xn-1 R b,9,2024/3/21,Colle

9、ge of Computer Science & Technology, BUPT,Example,?1 : 1, 2, 5, 4, 3 is a path of length 4 from vertex l to vertex 3?2 : 1, 2, 5, 1 is a path of length 3 from vertex l to itself?3 : 2, 2 is a path of length l from

10、vertex 2 to itself,10,2024/3/21,College of Computer Science & Technology, BUPT,Some definitions,A path that begins and ends at the same vertex is called a cycle.Rn : x Rn y means that there is a path of length n fro

11、m x to y in R.Rn (x)R? : x R? y means that there is some path in R from x to y. R? (x)The relation R? is sometimes called the connectivity relation for R .,11,2024/3/21,College of Computer Science & Technology, B

12、UPT,Example,Let A = {1, 2, 3, 4, 5, 6}R is shown as in figureR2 = ?,12,2024/3/21,College of Computer Science & Technology, BUPT,Example,Let A = {a, b, c, d, e}R = {(a, a), (a, b), (b, c), (c, e), (c, d), (d, e)}.

13、Compute (a) R2 ; (b) R?,13,2024/3/21,College of Computer Science & Technology, BUPT,Solution,R = {(a, a), (a, b), (b, c), (c, e), (c, d), (d, e)}.,R R2 R?,14,2024/3/21,Coll

14、ege of Computer Science & Technology, BUPT,Theorem,If R is a relation on A = {a1, a2, …, an}, then,15,2024/3/21,College of Computer Science & Technology, BUPT,Proof,Let MR = [mij] and MR2 = [nij]. the i, jth e

15、lement of MR? MR is equal to l mik= 1 and mkj = l for some k, l ? k ? n. By definition of the matrix MRai R ak and ak R ajai R2 aj , and so nij = 1. Therefore position i, j of MR ? MR is equal to 1 nij = l. So MR

16、 ? MR = MR2QED,16,2024/3/21,College of Computer Science & Technology, BUPT,Example,Let A = {a, b, c, d, e}R = {(a, a), (a, b), (b, c), (c, e), (c, d), (d, e)}.Compute R2,17,2024/3/21,College of Computer Science &a

17、mp; Technology, BUPT,Example cont.,,18,2024/3/21,College of Computer Science & Technology, BUPT,Theorem,For n ? 2 and R a relation on a finite set A, we have,19,2024/3/21,College of Computer Science & Technology,

18、 BUPT,Proof by induction,Let P(n) be the assertion that the statement holds for an integer n ? 2.Basis Step: P(2) is true by Theorem 1.,20,2024/3/21,College of Computer Science & Technology, BUPT,Induction Step,Cons

19、ider the matrix MRk+1. Let MRk+1 = [xij], MRk = [yij], and MR = [mij] If xij = 1, we must have a path of length k + 1 from ai to aj. If we let asbe the vertex that this path reaches just before the last vertex aj, then

20、 there is a path of length k from ai to as and a path of length l from as to aj. Thus yis = 1 and msj = 1, so has a 1 in position i, j. similarly, if has a 1 in position i, j, then xij

21、 = 1.So,21,2024/3/21,College of Computer Science & Technology, BUPT,Induction Step,is true. Thus by the principle of mathematical induction, P(n) is true for all nQED,22,2024/3/21,College of Computer Science &

22、 Technology, BUPT,The reachability relation,The reachability relation R* of a relation R on a set A that has n elements:x R* yif and only if x = y or x R? y,23,2024/3/21,College of Computer Science & Technology, B

23、UPT,Composition of paths,Let?1: a, x1 , x2 , … , xn-1, b ?2: b, y1 , y2 , … , ym-1, c The composition of ?1 and ?2 is the path?2 ? ?1: a, x1 , x2 , … , xn-1, b, y1 , y2 , … , ym-1, cNote the order of composition!,2

24、4,2024/3/21,College of Computer Science & Technology, BUPT,Example,Consider the relation whose digraph is given in Figure and the paths?1: 1, 2, 3?2: 3, 5, 6, 2, 4 ?2 ? ?1,25,2024/3/21,College of Computer Science

25、& Technology, BUPT,Transitive closure,The transitive closure of a relation R is the smallest transitive relation containing R.,26,2024/3/21,College of Computer Science & Technology, BUPT,Transitive Closure,Also r

26、ecall R is transitive iff Rn is contained in R for all nHence, if there is a path from x to y then there must be an arc from x to y, or (x, y) is in R.,27,2024/3/21,College of Computer Science & Technology, BUPT,Use

27、ful Results for Transitive Closure,Theorem:If A ? B and C ? B, then A È C ? B.Theorem:If R ? S and T ? U then R?T ? S?U.Corollary:If R ? S then Rn ? Sn,28,2024/3/21,College of Computer Science & Technolo

28、gy, BUPT,Useful Results for Transitive Closure,Theorem:If R is transitive then so is RnTrick proof: Show (Rn)2 = (R2)n Ì RnTheorem: If Rk = Rj for some j > k, then Rj+m = Rn for some n ? j.We don’t get any

29、new relations beyond Rj.,29,2024/3/21,College of Computer Science & Technology, BUPT,Theorem,Let R be a relation on a set A. then R? is the transitive closure of R.Proof: we must show that R?1) is a transitive rel

30、ation2) contains R3) is the smallest transitive relation which contains R,30,2024/3/21,College of Computer Science & Technology, BUPT,Proof of Part 1),Suppose (x, y) and (y, z) are in R?. Show (x, z) is in R?.By d

31、efinition of R?, (x, y) is in Rm for some m and (y, z) is in Rn for some n.Then (x, z) is in Rn?Rm = Rm+n which is contained in R?.Hence, R? must be transitive.,31,2024/3/21,College of Computer Science & Technology

32、, BUPT,Proof of Part 2),Easy from the definition of R?,32,2024/3/21,College of Computer Science & Technology, BUPT,Proof of Part 3),Now suppose S is any transitive relation that contains R, show S contains R? (that i

33、s R? is the smallest such relation).R ? S so R2 ? S2 ? S since S is transitiveTherefore Rn ? Sn ? S for all n. (why?)Hence S must contain R? since it must also contain the union of all the powers of R.Q. E. D.In fac

34、t, we need only consider paths of length n or less.,33,2024/3/21,College of Computer Science & Technology, BUPT,Example,LetA={1, 2, 3, 4}R={(1, 2), (2, 3), (3, 4), (2, 1)}Find the transitive closure of R.,,,,,,,,,

35、2,4,3,1,34,2024/3/21,College of Computer Science & Technology, BUPT,Example,35,2024/3/21,College of Computer Science & Technology, BUPT,Theorem,Let A be a set with |A|=n, and let R be a relation on A. Then,36,202

36、4/3/21,College of Computer Science & Technology, BUPT,Proof,The equality will hold, if, for k?n<m, we haveRm ? Rk(a, b) ? Rm ? (a, b) ? Rk,37,2024/3/21,College of Computer Science & Technology, BUPT,Proof,Le

37、t a and b be A and suppose that a, x1, x2, …, xm-1, b is a path of length m from a to b in R (a, x1) ?R(x1, x2) ?R…(xm-1, b) ?R,38,2024/3/21,College of Computer Science & Technology, BUPT,Proof,There are m+1 elem

38、ents in the path, but we have only n distinct elements in A.So, there must be some same vertex in the path, say xi = xj = c, i<j(a, x1) ?R(x1, x2) ?R…(xi-1, xi) ?R(xi, xi+!) ?R…(xj-1, xj) ?R(xj, xj+1) ?R…(x

39、m-1, b) ?RThe red edges form a cycle in the path, we get a new path by deleting the cycle,39,2024/3/21,College of Computer Science & Technology, BUPT,Proof,A new path from a to b by deleting the cycle(a, x1) ?R(x

40、1, x2) ?R…(xi-1, xi) ?R(xj, xj+1) ?R…(xm-1, b) ?R,40,2024/3/21,College of Computer Science & Technology, BUPT,Proof,A path from a to b (xi = xj = c)a, x1, x2,…, xi-1, c, xj+1,…, xm-1, bThe length is k = m - j

41、+ i.The process can continue until k?n, so we haveRm ? Rk?m (m>n ?(a, b) ? Rm ? ?k (k?n ?(a, b) ? Rk ))ThereforeQED,41,2024/3/21,College of Computer Science & Technology, BUPT,Some definitions,LetA = {a1,

42、 a2,…, an}R be a relation on AInterior verticesa, x1, x2,…, xi, b,42,2024/3/21,College of Computer Science & Technology, BUPT,Some definitions,Wk: a Boolean matrix, for 1?k?nWk has a 1 in position i, jIf and onl

43、y ifthere is a path from ai to aj in R whose interior vertices, if any, come from the set {a1, a2,…, ak}What about W0 Wn ?Let W0 = WRWn = WR?W0, W1 , W2 , … , Wn,43,2024/3/21,College of Computer Science & Techno

44、logy, BUPT,Warshall’s Algorithm,Procedurebegin with the matrix of R, and compute each matrix Wk from the previous matrix Wk-1, and, reach WR? in n steps,,44,2024/3/21,College of Computer Science & Technology, BUP

45、T,Warshall’s Algorithm,SupposeWk = [tij]Wk-1 = [sij]If tij = 1, then there must be a path from ai to aj whose interior vertices come from the set {a1, a2,…, ak}.Whether ak is an interior vertex ?Two cases,45,2024/3/

46、21,College of Computer Science & Technology, BUPT,Warshall’s Algorithm,ak is not an interior vertexthen all interior vertices must actually come from the set {a1, a2,…, ak-1}so sij = 1.ak is an interior vertexAss

47、ume ak appears only once (why?)Two subpathsai to ak and ak to ajsik = 1 and skj = 1,46,2024/3/21,College of Computer Science & Technology, BUPT,Warshall’s Algorithm,The basis for Warshall’s Algorithmtij = 1If an

48、d only ifeithersij = 1sik = 1 and skj = 1,47,2024/3/21,College of Computer Science & Technology, BUPT,Warshall’s Algorithm,Step1: First transfer to Wk all 1’s in Wk-1.Step2: List the locations p1, p2, …, in col

49、umn k of Wk-1, where the entry is 1 List the locations q1, q2, …, in row k of Wk-1, where the entry is 1Step3: Put 1’s in all the positions pi, qj of Wk (if they are not already there),48,2024/3/21,College of Computer

50、 Science & Technology, BUPT,Example (1),LetA={1, 2, 3, 4}R={(1, 2), (2, 3), (3, 4), (2, 1)}Find the transitive closure of R.,,,,,,,,,2,4,3,1,49,2024/3/21,College of Computer Science & Technology, BUPT,Example,

51、50,2024/3/21,College of Computer Science & Technology, BUPT,Warshall’s Algorithm,Algorithm WarshallCLOSURE?MATFor k = 1 thru N For i = 1 thru NFor j = 1 thru N CLOSURE[i,j]?CLOSURE[i,j]?(CLOSURE[i,k

52、]?CLOSURE[k,j])End of Algorithm Warshall,51,2024/3/21,College of Computer Science & Technology, BUPT,Analysis,Complexity of AlgorithmWarshalln3MR?n4,52,2024/3/21,College of Computer Science & Technology, BUP