# The definition of a graph's transitive reduction

I want to determine the transitive reduction of this graph:

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.

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

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