Talk:Transitive closure

From Wikipedia, the free encyclopedia

Contents

[edit] Minimal inverse

Is there an algorithm, that, given a transitive relation T, will return the smallest relation R such that the transitive closure of R is T? Is there such a smallest relation? I'm looking for such an algorithm, and this seems the most logical place to find a link to it. Luqui 10:55, July 19, 2005 (UTC)

Yes, and it's called transitive reduction, a concept that Wikipedia is not yet familiar with. Luqui 10:56, July 19, 2005 (UTC)
I dispute this. For finite sets, there are minimal such R, but they are not necessarily unique. If the relation T is, in addition, antisymmetric or asymmetric, then R is unique. However, there are minimal reductions of the full relation T on three elements (so that T has 9 pairs) with 3 and with 4 pairs. In addition, the order relation (<) on the rationals clearly cannot have any minimal reduction. Arthur Rubin 23:23, 15 August 2005 (UTC)
There is indeed a smallest one. To see that, consider that (1) the relation whereby every pair of members of the domain is related, is a transitive relation that is weaker than (i.e. that includes) T, and (2) the set of all such relations is closed under intersection, so the intersection of all such relations is another such relation; that intersection is therefore the smallest one. Michael Hardy 22:44, 19 July 2005 (UTC)
I dispute statement (2) here. Arthur Rubin 23:23, 15 August 2005 (UTC)
Sorry -- I read the question wrong. I thought it was asking whether, given R, there is a smallest T. Michael Hardy 01:40, 16 August 2005 (UTC)
The graphviz [1] tool tred computes a transitive reduction of a graph given as input. Directed graphs with no cycles (such as partial orders) have a unique transitive reduction. I have found this tool to be helpful for drawing Hasse diagrams. 69.180.211.147 23:23, 17 January 2006 (UTC)
The transitive reduction is not unique for cyclic graphs, but the differences between minimal transitive reductions are essentially unimportant: each strongly connected component is represented by a cycle, and if we contract each of these cycles to a vertex we will always get the same graph. We can attain a canonical form by numbering the vertices, promising that all edges not in the cycle go in and out from the lowest-numbered vertex, and choose the cycle to pass through the vertices in increasing number order (and back around from the largest to the smallest). Deco 23:43, 17 January 2006 (UTC)
So it's clear that there should be an article on transitive reduction. Should we move this bit of discussion there? 69.180.211.147 01:10, 18 January 2006 (UTC)
OK, i made my first article: transitive reduction Lyonsam 02:03, 18 January 2006 (UTC)
Good job! I'll add a bunch of stuff to it. Deco 03:12, 18 January 2006 (UTC)

[edit] *blink*

Would be really nice if this page could have a slightly less technical explanation too. The term "transitive closure" is sometimes used in less formal contexts, it would be nice to know what it meant! —The preceding unsigned comment was added by 80.111.233.163 (talk • contribs) 18:35, 04 September 2005 (UTC)

What do you have in mind? The first sentence seems to be a good non-technical summary. Arthur Rubin 18:35, 7 September 2005 (UTC)

This article is yet another good example that you can't learn something new by reading wikipedia articles unless you already know most of it already. You may want to consider giving a real example and to have linked articles for all the mathematical symbols you used —The preceding unsigned comment was added by 64.156.212.30 (talk • contribs) 05:53, 07 April 2006 (UTC)

Right. I came here after my textbook did a lousy job at explaining it, and this is even worse. Maybe it could do with some explanations that don't involve so many symbols. --BennyD 19:06, 16 December 2006 (UTC)

Putting the examples into the lead section might help to better convey the idea behind this first, before proceeding to the more formal stuff. — Matt Crypto 20:21, 10 January 2007 (UTC)

[edit] Transitive closure VS Transitive and reflexive closure

In this page, the Transitive Closure seems include a reflexive closure. In my mind we have to dissociate :

Transitive Closure: R^+ = \bigcup_{i\in\mathbb{N}_1} R^i
Transitive and Reflexive Closure: R^* = \bigcup_{i\in\mathbb{N}} R^i

where \mathbb{N}_1 is the set of naturals without 0 (\mathbb{N}_1=\mathbb{N}-\{0\})

What do you think about it ?

—The preceding unsigned comment was added by Nico S99 (talk • contribs) 09:29, December 27, 2006 (UTC)

[edit] nonmathematical

What set theory allows, for example, humans and airports to be members of sets? What a silly thing to say. —Preceding unsigned comment added by 24.61.183.197 (talk • contribs) 02:02, April 19, 2007