Re: Transitive Order of a Relation

On May 6, 8:33 am, DGo...@xxxxxxxxxxxx wrote:
Given a relation R, which is a subset of the power set P of the
Cartesian product SxS of a set S with itself, R is either transitive
or it is not. The transitive closure of R is well defined and is
conventionally noted R^t, where t is not an integer, but indicates
"transitive".

Matrix multiplication may be used to find the transitive closure of a
graph. The mth power of an ajacency matrix is the number of paths of
length m between the relevant vertices. Each time the adjacency matrix
A of a graph G of a relation R is squared, new paths of length two may
appear. For large graphs this is easier using computer methods than
looking for potential closures in the graph by inspection. When none
appear, we are done; we have found the transitive closure of the
relation.

By defining 0/0 = 0, we may normalize any power of an adjacency matrix
simply to directly represent the transitive closure of a graph. We may
write (piecewise) (R / |R|) to normalize a matrix if 0/0 = 0. Then,
the transitive order of a relation R is

the minimial power n such the normalized adjacency matrices

(piecewise)
( (R^(2^n)) / | R^(2^n)) | ) = ( (R^(2^(n+1))) / | R^(2^(n+1)))
| ).

The transitive order of a transitive relation is 1.

The transitive closure of a relation with transitive order n is
therefore

( (R^(2^n)) / | R^(2^n)) | ).

Is this known?

Doug Goncz
Replikon Research
Seven Corners, VA 22044-0394

Hello? Is anybody listening?

Doug

.

Relevant Pages

  • Re: Transitive Order of a Relation
    ... The transitive closure of R is well defined and is ... A of a graph G of a relation R is squared, new paths of length two may ... Please define the term "relation of transitive order n" ... Is it a standard terminology? ...
    (sci.math)
  • Re: Can this be done in SQL? Find the transitive relation
    ... I am strugling get the following done in SQL. ... http://www.bookpool.com/sm/0977671542, section on transitive closure ... There are several key graph concepts that would guide your intuition ... Figure 6.5: Reachability as an equivalence relation: graph from fig. ...
    (comp.databases.oracle.server)
  • Re: Help needed: Is Quick-Union-Find the right solution to this problem ?
    ... That's a solved problem (checking for cycles in a directed graph using ... > What you want is a "transitive closure" of the graph. ... I did a bit of research and studied two approaches to Warshall ... which is pretty easy to accomplish or I might have an array of strings ...
    (comp.programming)
  • Transitive Order of a Relation
    ... which is a subset of the power set P of the ... The transitive closure of R is well defined and is ... A of a graph G of a relation R is squared, new paths of length two may ... we may normalize any power of an adjacency matrix ...
    (sci.math)
  • Re: Transitive Order of a Relation
    ... The transitive closure of R is well defined and is ... The mth power of an ajacency matrix is the number of paths of ... A of a graph G of a relation R is squared, new paths of length two may ... Please define the term "relation of transitive order n" ...
    (sci.math)