Re: transitive closure again

Mikito Harakiri wrote:
> paul c wrote:
> > If we have a relation that is the closure (including trivial
> > relationships if necessary), can we obtain what Mikito (if I recall),
> > calls the adjacency list, using the RM algebra but without recursion?
>
> Seems easy: for all pairs of nodes making an edge (x,y ) in the TC
> graph, select only those that aren't represented as (x,z) & (z,y).

Here is a slightly different (and amusing) perspective. Transitive closure T of graph G is a formal power series

T = 1 + G + G^2 + G^3 + ...

This equation has standard interpretation where each T and G is an adjacency matrix for a graph. Is this equation useful at all? Let's extract factor G on the left side

T = 1 + G (1 + G + G^2 + ...)

which gives the recurrence equation

T = 1 + G T

which is essentialy the same as

T = (1 - G)^(-1)

(This is a valid trick for acyclic graphs only. Why?)

If nothing else, the last equation allows calculating transitive closure via formal matrix operations.

In the context of Paul's question, starting from this equation perhaps, we can deduce a another formula that represents G in terms of T? Well, without any clever idea by just rearranging terms I've got

G = 1 - T^(-1)

which seems lead nowhere. The trick is another recurrence formula

T = G + T^2

which you can verify by expanding the T and expanding T^2 into a series.This is the exact answer:

G = T - T^2

"the original graph edges are those in transitive closure graph except those that are compositions of nodes (x,z) (z,y)" Received on Sat Nov 05 2005 - 01:16:46 CET