《離散數(shù)學(xué)》ch(7)

1、整理課件7.4 Closures of Relations (關(guān)系的閉包關(guān)系的閉包)Introduction (1) Example 0 (page 544) A computer network has data centers in Boston, Chicago, Denver, Detroit, New York and San Diego. There are direct, one-way telephone lines from Boston to Chicago, from Boston to Detroit, from Chicago to Detroit, from Det

2、roit to Denver, and from New York to San Diego.整理課件 Let R be the relation containing (a,b) if there is a telephone line from the data center a to that in b. How can we determine if there is some (possibly indirect) link composed one or more telephone lines from one center to another?Solution: We can

3、 find all pairs of data centers that have a link by constructing the smallest transitive relation that contains R. This relation is called the transitive closure (傳遞閉包傳遞閉包) of R整理課件 (2) The Closure of Relation R with Respect to Property P Let R be a relation on A. R may or may not have some property

4、 P, such as reflexive, symmetric, or transitivity. If there is a relation S with property P containing R such that S is a subset of every relation with property P containing R, then S is called the closure of R with respect to P. (可以可以page 555的第的第35題作業(yè)來加深理解題作業(yè)來加深理解) Why?整理課件 2. Closures (1) Introduc

5、tion 1 (reflexive closure) The relation R=(1,1), (1,2), (2,1), (3,2) on the set A=1,2,3 is not reflexive. How can we produce a reflexive relation containing R that is as small as possible? Solution: by adding (2,2), (3,3) to relation R. The new relation is called the reflexive closure of R. 整理課件 (2)

6、 Result 1 Let = (a,a) | aA. It is called the diagonal relation (對角線的關(guān)系對角線的關(guān)系). The reflexive closure of relation R on set A- R Example 1 (page 545) What is the reflexive closure of the relation R= (a,b) | ab on the set of positive integers? Solution: RR-1=.= (a,b) | ab 整理課件 (5) Introduction 3 (trans

7、itive closure) Consider the relation R= (1,3), (1,4), (2,1), (3,2) on the set 1,2,3,4. The relation is not transitive. Add (1,2), (2,3), (2,4), and (3,1). Still not transitive. Why? -(3,1) in -(1,4) in -(3,4) not in transitive closure-complicated整理課件 3. Paths in directed graphs (1) Definition 1 (pat

8、h) A path (路徑路徑)from a to b in the directed graph G is a sequence of edges (x0,x1), (x1,x2), (x2,x3),(xn-1,xn) in G, where n is a nonnegative integer, and x0=a, xn=b. This path is denoted by x0, x1, , xn and has length n. A path of length n1 that begins and ends at the same vertex is called a circui

9、t or cycle (回路回路).整理課件 (2) Example 3 (page 546) Which of the following are paths in the directed graph shown in Figure 1: a, b, e, d; a, e, c, d, b; b, a, c, b, a, a, b; d, c; c, b, a; e, b, a, b, a, b, e? What are the lengths of those that are paths? Which of the paths in this list are circuits? So

10、lution: See book.整理課件 (3) The term path also applies to relations There is a path from a to b in R if there is a sequence of elements a, x1, x2, , xn-1, b with (a,x1)R,(x1,x2)R, and (xn-1,b)R.整理課件 (4) Theorem 1 (page 547) Let R be a relation on a set A. There is a path of length n, where n is a posi

11、tive integer, from a to b if and only if (a,b)Rn. Proof: See book.整理課件4. Transitive closure (傳遞閉包傳遞閉包)Definition 2 (page 547) Let R be a relation on a set A. The connectivity relation (連通性關(guān)系連通性關(guān)系) R* consists of the pairs (a,b) such that there is a path of length at least one from a to b in R. In ot

12、her words, using theorem 1, R*= n=1 infinite Rn整理課件(2) Example 4 (page 547) Let R be the relation on the set of all people in the world that contains (a,b) if a has met b. What is Rn, where n is a positive integer greater than one? What is R*?Solution: (a) The relation R2 contains (a,b) if there is

13、a person c such that (a,c)R and (c,b)R, that is, if there is a person c such that a has met c and c has met b. 整理課件 (b) Similarly, Rn consists of those pairs (a,b) such that there are people x1, x2, , xn-1 such that a has met x1, x1 has met x2, , and xn-1 has met b. (c) The relation R* contains (a,b

14、) if there is a sequence of people, starting with a and ending with b, such that each person in the sequence has met the next person in the sequence.Example 5:Example 6: See the book.整理課件(3) Theorem 2 (page 548) The transitive closure of a relation R equals the connectivity relation R*.Proof: Please

15、 see blackboard and book.整理課件(4) Lemma 1 (page 548) Let A be a set with n elements, and R be a relation on A. If there is a path of length at least one in R from a to b, then there is a path with length not exceeding n. Moreover, when ab, if there is a path of at least one in R from a to b, then the

16、re is such a path with length not exceeding n-1.整理課件From Lemma 1, we see that the transitive closure of R is the union of R, R2, R3, , Rn. R*=R R2 R3 Rn整理課件(5) Theorem 3 (page 501) Let MR be the zero-one matrix of the relation R on a set with n elements. Then the zero-one matrix of the transitive cl

17、osure R* is MR*=MR / MR2 / MR3 / / MRn Reason: (a) R*=R R2 R3 Rn (b) MRn=MRn (c) MRS =MR / MS整理課件 (6) Example 7 (page 549) Find the zero-one matrix of the transitive closure of the relation where MR=? (page 502) Solution: See book.整理課件 (7) A Procedure for Computing the Transitive Closure Procedure transitive closure (MR:zero-one matrix) A:=MR B:=A for i:=2 to n begin A:=AMR B:=B / A end Here, stands for the Boolean product.整理課件 Analysis of this algorithm:Each Boolean product -n2(n+n-1) bit operations All these Boolean pr