1
$\begingroup$

I have graphs represented by matrices. For example,

$\begin{matrix} 0&0&0\\1&0&0\\1&1&0\end{matrix}$

Produces this graph:

enter image description here

The graphs are supposed to be transitive, i.e. the edge from A to C is redundant and should be removed.

From the Wikipedia Transitive Reduction page, the transitive reduction of a graph can be computed as follows:

$R^- = R - (R \circ R^+)$

Where $R^-$ is the transitive reduction, $R^+$ is the transitive closure of the matrix and $\circ$ denotes relation composition.

I have written algorithms to compute subtraction and the transitive closure of a matrix, but I'm having trouble understanding relation composition. My knowledge of set theory is pretty minimal and the notation on the Wikipedia page is beyond me.

All of the examples I've found seem to deal with sets of ordered pairs, and I'm wondering if anyone could recommend resources or give a brief outline of how to compute relation composition of two matrices.

  • 0
    @Henning Makholm Ah yes, the issue was that my matrices have 1s across the diagonal. Thanks for your help. If you submit it as an answer I'll accept it.2012-02-25

1 Answers 1

1

To not leave this question unanswered, I repeat the correct solution given by Henning Makholm in the commentary:

If $A$ and $B$ are relation matrices, the matrix of the composed relation can be computed by matrix multiplication $A\cdot B$ and then setting all non-zero entries of the product to $1$.