Transitive Closure and Reflexive-Transitive Closure R+,R∗
Closure (Mathematics)
Closure is a property said to be satisfied by a set under a given operation if and
only if performing the operation on members of the set always produces a
member of the same set. (Wikipedia)
binary relation: 2-ary relation (R⊆S×S)
P closure operator: cl(R) is the strongest or the smallest relation (cl(R)⊆S×S) that contains R (R⊆cl(R)) and the property P holds (P(Q)=true).
a binary relation R is transitive: ∀x,y,z:S∙(((x,y)∈R∧(y,z)∈R)⟹(x,z)∈R)
for example, >,=,≥,≤ are transitive, but "is parent of" is not.
a binary relation R is reflexive: ∀x:S∙((x,x)∈R)
for example, =,≥,≤ are reflexive, but > is not reflexive
For example,
reflexive closure: clref(R) is the smallest relation that contains R and is reflexive.
transitive closure: cltrn(R), or R+ is the smallest relation that contains R and is transitive.
reflexive–transitive closure: R∗ is the smallest relation that contains R and is both transitive and reflexive.
Definitions
Rr=R∪idS - reflexive closure
Rs=R∪R∼ - symmetric closure
R∗=R+∪idS
Alternative Definitions in terms of iterations (Z notation)
iteration of relation: Rk=R;R;...;R=R;Rk−1=Rk−1;R
R0=idS
R+=⋃{k:N1∙Rk}
R+=⋃{k:N∙Rk}
Applications
transitive closure of a directed graph likes cities connection by railways or airplanes: means all possible routes from one city to another city, then can be used to calculate the shortest path from one place to another place
R={(A,B),(B,C),(B,D),(C,A)} - direct routes between two cities
R2=R;R={(A,C),(A,D),(B,A),(C,B)} - one stop routes between two cities
R3=R2;R={(A,C),(A,D),(B,A),(C,B)};{(A,B),(B,C),(B,D),(C,A)}={(A,A),(B,B),(C,C),(C,D)} - two stop routes between two cities
R4=R3;R={(A,A),(B,B),(C,C),(C,D)};{(A,B),(B,C),(B,D),(C,A)}={(A,B),(B,C),(B,D),(C,A)} - equal to R
No comments :
Post a Comment