8.4 Closures of Relations Intro Consider the following

8.4 Closures of Relations Intro Consider the following

8.4 Closures of Relations Intro Consider the following example (telephone line, bus route,) a b c d Is R, defined above on the set A={a, b, c, d}, transitive? If not, is there a (possibly indirect) link between each of the cities?

To answer, we want to find the Transitive Closure Closures, in general Def: Let R be a relation on a set A that may or may not have some property P. (Ex: Reflexive, ) 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.

Note: the closure may or may not exist Reflexive Closures- Idea, Example Reflexive Closure of Rthe smallest reflexive relation that contains R Consider R={(1,2),(2,3),(3,2)} on A={1,2,3} 1 2 3 Using both ordered pairs and digraphs, find the reflexive

closure. Reflexive Closures Reflexive Closure of Rthe smallest reflexive relation that contains R Reflexive Closure = R Where on A.

={(a,a)| a A} is the diagonal relation More examples Find the reflexive closures for: R={(a,b)|a

Symmetric Example Find the symmetric closure of R={(1,1), (1,2),(2,2),(2,3),(3,1),(3,2)} on A={1,2,3} 1 2 3 Symmetric Closures Symmetric Closure of R = R R-1 Where R-1= {(b,a) | (a,b) R}

Example: R={(a,b)|a>b} on the integers Z Symmetric closure: Transitive Theory- example 1 2 4 3 Add all (a,c) such that (a,b), (b,c) R.

Keep going. (Why?) Transitive Closure Theory, and Def of Path Def: A path from a to b in a directed graph G is a sequence of edges (x0,x1), (x1,x2) (xn-1, xn) in G where x0=a and xn=b. It is denoted x1, x2,xn and has length n. When a=b, the path is called a circuit or cycle.

Find Transitive Closure- see worksheet Do Worksheet 12 43 Find the transitive closure Find circuits and paths of length 2, 3, 4

Example- in matrices Using the idea that R n+1 = RnR and MSR = MR MS , Find the matrices for R R2 R3

R4 The find paths of length 2, 3, 4 Example = Next step

In order to come up with a theory for the transitive closure, we will first study paths. Theorem 1 Theorem 1: Let R be a relation on a set A. There is a path of length n from a to b iff (a,b)Rn Proof method?

Proof of Thm. 1 By induction: N=1: true by definition (path from a to b of l=1 iff (a,b) R). Induction step: Assume: There exists a path of length __ from ___iff ______ Show: There exists a path of length __ from ___iff ______ Assuming the IH (Inductive Hypothesis), There is a path of length __ from ___

Iff There exists an element c with a path from a to c in R and a path of length n from c to b in ___ Iff There exists an element c with (a,c) ___ and (c,b) ___ Iff (a,b) ____ = _______ Def 2: Connectivity relation Def. 2: Let R be a relation on set A. The connectivity relation R* consists of the pairs (a,b) such that there is a path between a and b

in R. R* = Examples R={(a,b)| a has met b} 6 degrees Erdos number R* include (you,__)

R={(a,b)| it is possible to travel from stop a to b directly} on set A of all subway stops R*= R={(a,b)|state a and b have a common border on the set A of states. R*= Thm. 2: Transitive closure is the connectivity

relation Theorem 2: The transitive closure of a relation R equals the connectivity relation R* = Elements of the Proof: Note that R R* To show R* is the transitive closure of R, show: 1) R* is ________

2) Whenever S is a transitive relation that contains R, then R* ______ Proof of Thm 2 1) Assume (a,b) R* and (b,c) R* So (a,b) ___ and (b,c) ___ By Thm. 1, there exists paths 2 paths: In conclusion ________

Thm 2 proof 2) Suppose S is a transitive relation containing R It can be shown by induction that Sn is transitive. By a previous theorem in sec. 8.1, S n ___ S. Since S* = S k and S k __ S , the S* ___ S. Since R ___S, the R* ____ S*. Therefore R* ___ S* ___ S.

Recently Viewed Presentations

  • Presentazione standard di PowerPoint

    Presentazione standard di PowerPoint

    How . Idoneità EF tutorato. Unit 4 - Mrs. Loi. A. Pronunciation - page 29 ex. 3. How do wepronounce the letter O. in the word 'mother'? How manydifferent ways of pronuncing the letter O
  • The Whippet - ccsdk12.org

    The Whippet - ccsdk12.org

    The Whippet Needs to be brushed occasionally to remove dead hair Give the dog a chew toy to avoid tartar build up. 17.25 - 20 inches; 25-45 pounds fur is firm and dense; assortment of colors the most common color...
  • In search of equity, efficiency and impact in

    In search of equity, efficiency and impact in

    To evaluate COPD case detection strategies (in different at-risk subgroups) in terms of epidemiological consequences, cost-effectiveness, and budget impact. General objective. To create the first Canadian outcomes model of COPD to support policy, practice, and research.
  • Welcome to Our Worship Services - TheLordsWay

    Welcome to Our Worship Services - TheLordsWay

    A DRIED EYED CHURCH IN A HELL BENT WORLD. INTRODUCTION: 1. The Christian life is to be full of overflowing abundant joy. A. Someone has said that joy is the flag that flies from the heart when the King is...
  • Etienne Aug Deputy Scientific Director Particle Physics and

    Etienne Aug Deputy Scientific Director Particle Physics and

    Etienne Augé Deputy Scientific Director Particle Physics and Computing CFMA: what for ? Overview of the cooperation activities at CNRS/IN2P3
  • Who's to blame?

    Who's to blame?

    "I married them, and their stol'n marriage day / Was tybalt's doomsday, whose untimely death/ banish'd the new-made bridegroom from this city"(5.3.223-225). He admits that from the day he married them everything was doomed.
  • Middle School Course Selection Information 2020

    Middle School Course Selection Information 2020

    Elective Subject Choices. After the CORE subjects, students have the opportunity to fill the rest of their timetable with subjects from any of the Key Learning Areas we just looked at.
  • Ecosystems - Groby Bio Page

    Ecosystems - Groby Bio Page

    Simple Food Chain. Producer. First Consumer. Second Consumer. The arrows in a food chain show the transfer of food energy from organism to organism. Food chains always begin with a PRODUCER. This is a green plant which is able to...