Tranzitivní uzávěr

Pojem Tranzitivní uzávěr má několik významů v rámci různých oblastí matematiky.

V teorii množin

V kontextu axiomatické teorie množin, např. ZF, se množina nazývá tranzitivní, pokud obsahuje všechny prvky svých prvků. Například množina $a=\{\mathrm{\varnothing },\left\{\left\{\mathrm{\varnothing }\right\}\right\}\}$ není tranzitivní, protože neobsahuje množinu $\left\{\mathrm{\varnothing }\right\}$, ač tato je prvkem množiny $\left\{\left\{\mathrm{\varnothing }\right\}\right\}$, která je prvkem $a$.

Tranzitivní uzávěr množiny $a$ je pak nejmenší tranzitivní nadmnožina množiny $a$; použité slovo „nejmenší“ odkazuje na to, že třída všech množin je částečně uspořádána relací množinové inkluze. Tranzitivní uzávěr $a$ je tedy taková tranzitivní $b\supseteq a$, že pro každou tranzitivní $c\supseteq a$ platí $c\supseteq b$. Jinými slovy $b$ je tranzitivní nadmnožina $a$, která neobsahuje „nic navíc“, než co je nutné pro tranzitivitu, a proto každá další tranzitivní nadmnožina $a$ je i nadmnožinou $b$.

Každá množina má tranzitivní uzávěr, který lze zkonstruovat po krocích: množina $a_1$ obsahuje prvky $a$ a prvky jejích prvků, množina $a_2$ prvky $a_1$ a prvky jejích prvků atd. Tranzitivním uzávěrem množiny $a$ je množina právě těch množin $x$, které leží v $a_n$ pro nějaké přirozené číslo $n$.

V kontextu relací

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^{\prime }={\cap }_M[(R\subseteq M)\wedge (\mathrm{\forall }a,b,c)(([a,b]\in M\wedge [b,c]\in M)\Rightarrow ([a,c]\in M))]$

Například na celých číslech tranzitivní uzávěr relace „$x=y-1$“ je relace „$x>y$“. Tranzitivní uzávěr relace „$|x-y|=2$“ je „$y\text{ je sudé}$“.

V kontextu grafů

Tranzitivní uzávěr grafu

Jelikož každý orientovaný graf je binární relace na množině uzlů, tranzitivní uzávěr grafu vznikne doplněním hran z $a$ do $c$, existuje-li hrana (šipka) z $a$ do $b$ i z $b$ do $c$. Tuto operaci může být potřeba provést opakovaně, protože přidání hran může způsobit nutnost dalšího přidání.

Například graf se čtyřmi uzly a hranami spojujícími postupně první, druhý, třetí a čtvrtý uzel, má uzávěr s celkem šesti hranami (viz obrázek). Pokud by byla v původním grafu i hrana spojující čtvrtý uzel s prvním je uzávěrem úplný graf.

Obdobně se dá tranzitivní uzávěr definovat i pro neorientovaný graf. V tom případě jde vždy o graf úplný nebo tvořený disjunktní množinou úplných podgrafů.

Algoritmická složitost

Pro orientované grafy existuje efektivní algoritmus pro nalezení tranzitivního uzávěru. Je složitost je $O(m+\mu n)$, kde $m$ je počet hran, $n$ počet vrcholů a $\mu$ je počet hran spojujících jeho silně souvislýlmi komponentami.

Odkazy

Externí odkazy

• Šablona:Citace elektronického periodika