Transitive Order of a Relation
- From: DGoncz@xxxxxxxxxxxx
- Date: 6 May 2007 05:33:11 -0700
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
.
- Follow-Ups:
- Re: Transitive Order of a Relation
- From: DGoncz
- Re: Transitive Order of a Relation
- From: DGoncz
- Re: Transitive Order of a Relation
- Prev by Date: Re: Non-touching hex-triangles
- Next by Date: excellent money making program
- Previous by thread: Homeomorphic images of a line in R^2
- Next by thread: Re: Transitive Order of a Relation
- Index(es):
Relevant Pages
|
