Solution to the transitive closure of a binary relation R on a set X is the smallest … - Sikademy
Author Image

Archangel Macsika

the transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive steps of Warshall’s Algorithm: Step 1: Execute W:=M_R, k:=0W:=M R ​ ,k:=0 Step 2: Execute k:=k+1k:=k+1 Step 3: For all i\ne ki  =k such that w_{ik}=1w ik ​ =1, and for all jj execute the operation w_{ij}:=w_{ij}\lor w_{kj}w ij ​ :=w ij ​ ∨w kj ​ Step 4: If k=nk=n, then stop: the solution is W=M_{R^*}W=M R ∗ ​ , else go to step 2. in our case: M_R=\begin{pmatrix} 1 &0&1 \\ 0 & 1&1\\ 1&0&0 \end{pmatrix}M R ​ = ⎝ ⎛ ​ 1 0 1 ​ 0 1 0 ​ 1 1 0 ​ ⎠ ⎞ ​ k = 1: w_{31}=1w 31 ​ =1 W_1=\begin{pmatrix} 1 &0&1 \\ 0 & 1&1\\ 1&0&1 \end{pmatrix}W 1 ​ = ⎝ ⎛ ​ 1 0 1 ​ 0 1 0 ​ 1 1 1 ​ ⎠ ⎞ ​ k =3: w_{13}=1w 13 ​ =1 W_2=\begin{pmatrix} 1 &0&1 \\ 0 & 1&1\\ 1&0&1 \end{pmatrix}W 2 ​ = ⎝ ⎛ ​ 1 0 1 ​ 0 1 0 ​ 1 1 1 ​ ⎠ ⎞ ​ w_{23}=1w 23 ​ =1 W_3=\begin{pmatrix} 1 &0&1 \\ 1 & 1&1\\ 1&0&1 \end{pmatrix}W 3 ​ = ⎝ ⎛ ​ 1 1 1 ​ 0 1 0 ​ 1 1 1 ​ ⎠ ⎞ ​ transitive closure: R^*=\{(1, 1) (1, 3), (2, 2), (2,3), (3,1),(2,1),(3,3)\}R ∗ ={(1,1)(1,3),(2,2),(2,3),(3,1),(2,1),(3,3)}

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

a.

g(n)=6n\le 6f(n)=6n(n-1)

𝒈(𝒏) = 𝑶(𝒇(𝒏))


b.

𝑓(𝑛) = 𝑛 + 2\sqrt𝑛\le 3n\le 3𝑔(𝑛) = 3𝑛^2

𝒇(𝒏) = 𝑶(𝒈(𝒏))


c.

𝑓(𝑛) = 𝑛 + log 𝑛\le 2n\le 2𝑔(𝑛) = 2𝑛\sqrt 𝑛

𝒇(𝒏) = 𝑶(𝒈(𝒏))


e.

𝑔(𝑛) = log 𝑛 + 1\le 2logn\le 2f(n)=2(log 𝑛)^2

𝒈(𝒏) = 𝑶(𝒇(𝒏))


d.

𝑓(𝑛) = 𝑛 log 𝑛\le n\sqrt n=2𝑔(𝑛)

𝒇(𝒏) = 𝑶(𝒈(𝒏))

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-511-qpid-397