Tranzitivní uzávěr

Tranzitivní uzávěr binární relace R je definován jako nejmenší (z hlediska množinové inkluze) tranzitivní nadmnožina R.

Matematicky vyjádřeno, pro tranzitivní uzávěr R' binární relace R platí:

R ′ = ∩ M [ ( R ⊆ M ) ∧ ( ∀ a , b , c ) ( ( [ a , b ] ∈ M ∧ [ b , c ] ∈ M ) ⇒ ( [ a , c ] ∈ M ) ) ] {\displaystyle R'=\cap _{M}[(R\subseteq M)\land (\forall a,b,c)(([a,b]\in M\land [b,c]\in M)\Rightarrow ([a,c]\in M))]}

Příklad

Máme určit tranzitivní uzávěr relace R:

R = { ( 1 , 2 ) , ( 2 , 3 ) } {\displaystyle R=\{(1,2),(2,3)\}}

Relace R řiká, že existuje vztah mezi 1 a 2 a mezi 2 a 3. Abychom vytvořili tranzitivní relaci R', která zachová všechny prvky relace R, je třeba ji rozšířit o vztah mezi 1 a 3, tedy prvek ( 1 , 3 ) {\displaystyle (1,3)} . Jelikož chceme co nejmenší takovou relaci R', nebudeme ji rozšiřovat o další prvky. Tranzitivní uzávěr tak bude:

R ′ = { ( 1 , 2 ) , ( 2 , 3 ) , ( 1 , 3 ) } {\displaystyle R'=\{(1,2),(2,3),(1,3)\}}


Pahýl
Pahýl
 Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.