transitive closure

You are here: irt.org | FOLDOC | transitive closure

The transitive closure R* of a relation R is defined by

	x R y => x R* y
	x R y  and  y R* z => x R* z

I.e. elements are related by R* if they are related by R directly or through some sequence of intermediate related elements.

E.g. in graph theory, if R is the relation on nodes "has an edge leading to" then the transitive closure of R is the relation "has a path of zero or more edges to". See also Reflexive transitive closure.

Nearby terms: TRANSIT « transition ad « transitive « transitive closure » transit network » Translation Look-aside Buffer » Transmission Control Protocol

FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL