Tranzitivní uzávěr

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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'=\cap_M[(R \subseteq M) \and ( \forall a,b,c)(([a,b] \isin M \and [b,c] \isin M) \Rightarrow ([a,c] \isin M))]

Příklad[editovat | editovat zdroj]

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

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). 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)\}