Re: Transitive Closure

From: x <x-false_at_yahoo.com>
Date: Tue, 18 May 2004 09:50:06 +0300
Message-ID: <40a9b150_at_post.usenet.com>

• Post for FREE via your newsreader at post.usenet.com ****

"Mikito Harakiri" <mikharakiri_nospaum_at_yahoo.com> wrote in message news:8a529bb.0405171536.3b063d3f_at_posting.google.com... > "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:

It is not "Of course" because {0,1} could be easily interpreted as boolean values :-)
You asked "Which one is correct TC definition?"

> 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]])

>>> 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.

Interpreted back to graph, I see that the results are the same. :-) So what do you mean by correct ?

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

• Usenet.com - The #1 Usenet Newsgroup Service on The Planet! *** http://www.usenet.com Unlimited Download - 19 Seperate Servers - 90,000 groups - Uncensored -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Received on Tue May 18 2004 - 08:50:06 CEST