Re: Transitive Closure

"x" <x-false_at_yahoo.com> wrote in message news:<40a8abfa$1_at_post.usenet.com>...
> **** Post for FREE via your newsreader at post.usenet.com ****
>
>
> "Mikito Harakiri" <mikharakiri_at_iahu.com> wrote in message
> news:cl7pc.22$7Q3.233_at_news.oracle.com...
> >
> > "x" <x-false_at_yahoo.com> wrote in message
> news:40a4f84f$1_at_post.usenet.com...
> > > > > Wikipedia says: "...the transitive closure of a binary relation R on
> a
> > > > > set X is the smallest transitive relation on X that contains R."
> > > >
> > > > I have better definition. Assume that graph adjacency matrix is A.
> Then,
> > > > transitive closure is
> > > >
> > > > (1-A)^(-1) = I + A + A^2 + A^3 + ...
> > > >
> > > > On the other hand
> > > >
> > > > exp(A) = I + A +A^2/2 + A^3/6 + ...
> > > >
> > > > Which one is correct TC definition?
> > >
> > > What type have the elements of A ?
> >
> > Elements of A have values 0 and 1. (Although, the adjacency matrix
> > definition easily extends to graphs with weighted edges). Elements of
> TC(A),
> > on the other hand, should be allowed at least Real. TC(A) is interpreted
> > back to graph the following way: if matrix component value is non 0 then
> > nodes are adjacent.
>
> I asked what type. {0,1} is not a type.
> 0 , 1, +, ^, / as symbols for what ?

Oh, they are arithmetics operators, of course! For instance, ^ is power. Let me give you an example:

Edges:

tail head
---- ----
1 2
2 3

Adjacency Matrix:

mapple> G:=Matrix(3,3,[[0,0,0],[1,0,0],[0,1,0]]);

Transitive Closure:

mapple> (1-G)^(-1);

MATRIX([[1, 0, 0], [1, 1, 0], [1, 1, 1]]) mapple> exponential(G);

MATRIX([[1/2, 0, 0], [1, 1, 0], [1, 1, 1]]) Received on Tue May 18 2004 - 01:36:53 CEST