0
$\begingroup$

I want to determine the transitive reduction of this graph:

1

as of now, I only found the first step of doing this: represent the transitive closure of the graph as an adjacency relation, so this is what I did:

 (a,b)
 (a,c)
 (a,d)
 (a,e)
 (b,d)
 (c,d)
 (c,e)
 (d,e)

I'm not sure that this is the correct transitive closure of the graph, and I don't know how to move forward in determining its transitive reduction.

$\endgroup$
1
  • $\begingroup$ You are missing $(b,e)$. $\endgroup$ – plop Jul 17 '20 at 7:21
1
$\begingroup$

If we order the vertices alphabetically, then the adjacency matrix is

$$A=\begin{pmatrix} 0&1&1&1&0\\ 0&0&0&1&0\\ 0&0&0&1&1\\ 0&0&0&0&1\\ 0&0&0&0&0 \end{pmatrix}$$

The adjacency matrix of the transitive closure would be

$$B=\begin{pmatrix} 0&1&1&1&1\\ 0&0&0&1&1\\ 0&0&0&1&1\\ 0&0&0&0&1\\ 0&0&0&0&0 \end{pmatrix}$$

To get the this one you get each row by navigate the graph starting at the node corresponding to that row and mark with a $1$ the columns of the nodes that you manage to visit and with $0$ the rest.

Now,

$$AB=\begin{pmatrix} 0&0&0&2&3\\ 0&0&0&0&1\\ 0&0&0&0&1\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{pmatrix}$$

To build the adjacency matrix $C$ of the transitive reduction put a $1$ in position $(i,j)$ if the $(i,j)$ entry of $A$ is non-zero and the $(i,j)$ entry of $AB$ is zero.

So, the adjacency matrix of the transitive reduction should be

$$C=\begin{pmatrix} 0&1&1&0&0\\ 0&0&0&1&0\\ 0&0&0&1&0\\ 0&0&0&0&1\\ 0&0&0&0&0 \end{pmatrix}$$

So, the transitive reduction looks like this

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.