Consider a (binary) relationRon a non-empty setSconsisting of points in a plane. Letaandbbe...

Question

Consider a (binary) relationRon a non-empty setSconsisting of points in a plane. Letaandbbe two
elements ofS, i.e.,a,b?S, and defineRsuch thata R biff there is a directed path fromatob.

Consider the setS={a,b,c}with(a,b),(b,c),(c,d)?R1. IsR1transitive? Show this.

Consider the setS={a,b,c}with(a,b),(b,c),(c,b),(c,d),(a,c),(b,d)?R2. IsR2transitive? Show

this.

Define the transitive closure ofRtofR.

Construct the transitive closure ofR1.

Provide a concise description of the method (algorithm) you used to construct the transitive closure
ofR1.

Givennpoints in the plane, what is the maximum number of distinct directed paths that can connect
these points. (This problem requires you to carefully define the structure of the points in the plane).

David · Accepted Answer

Consider a (binary) relation R on a non-empty set S consisting of points in a plane. Let 
a and b be two elements of S, i.e., a, b? S, and define R such that aRb iff there is a 
directed path from a to b. 
1. Consider the set S = {a, b, c, d} with (a, b), (b, c), (c, d)? R1. Is R1 transitive? Show this. 
Sol: 
The above given relation R1 is not transitive. 
Proof: 
R1 is the set of elements {(a, b), (b, c), (c, d)}.

Consider a (binary) relationRon a non-empty setSconsisting of points in a plane. Letaandbbe two elements ofS, i.e.,a,b?S, and defineRsuch thata R biff there is a directed path fromatob. Consider the...

Solution

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment