1、Yang JCollege of Computer Science & TechnologyBeijing University of Posts & Telecommunications9.4 Closures of Relations 2* College of Computer Science & Technology, BUPT Closures of Relationsn Definitionn The closure(闭包 ) of a relation R with respect to property P is the relation obtained by adding
2、the minimum number of ordered pairs to R to obtain property P.n 3 elements:n R1 contains Rn R1 possesses the property Pn If R2 contains R and possesses the property P, then R2 contains R13* College of Computer Science & Technology, BUPT Closures of Relationsn In terms of the digraph representation o
3、f Rn To find the reflexive closure n add loops.n To find the symmetric closuren add arcs in the opposite direction.n To find the transitive closuren if there is a path from a to b, add an arc from a to b.4* College of Computer Science & Technology, BUPT Reflexive Closuren Theorem: n Let R be a relat
4、ion on A.n The reflexive closure of R, denoted r(R), is RD.n Method:n Add loops to all vertices on the digraph representation of R.n Put 1s on the diagonal of the connection matrix of R.5* College of Computer Science & Technology, BUPT Symmetric closuren Theoremn Let R be a relation on A. n The symm
5、etric closure of R, denoted s(R), is the relation RR-1.6* College of Computer Science & Technology, BUPT Theoremn R is symmetric n If and only ifn R = R-1n Note: in digraph of a symmetric relation, use undirected edges instead of arcs7* College of Computer Science & Technology, BUPT Example8* Colleg
6、e of Computer Science & Technology, BUPT Pathsn Suppose 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 thatn a R x1, x1 R x2, ., xn-1 R b9* College of Computer Science & Technology, BUPT Exa
7、mplen 1 : 1, 2, 5, 4, 3 is a path of length 4 from vertex l to vertex 3n 2 : 1, 2, 5, 1 is a path of length 3 from vertex l to itselfn 3 : 2, 2 is a path of length l from vertex 2 to itself2451310* College of Computer Science & Technology, BUPT Some definitionsn A path that begins and ends at the same vertex is called a cycle.n Rn : x Rn y means that there is a path of length n from x to y in R.n Rn (x)n R : x R y means that there is some path in R from x to y. n R (x)n The relation R is sometimes called the connectivity relation for R .
