Tranzitivní uzávěr

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

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 ${\displaystyle a=\left\{\emptyset ,\left\{\left\{\emptyset \right\}\right\}\right\}}$ není tranzitivní, protože neobsahuje množinu ${\displaystyle \left\{\emptyset \right\}}$, ač tato je prvkem množiny ${\displaystyle \left\{\left\{\emptyset \right\}\right\}}$, která je prvkem ${\displaystyle a}$.

Tranzitivní uzávěr množiny ${\displaystyle a}$ je pak nejmenší tranzitivní nadmnožina množiny ${\displaystyle 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 ${\displaystyle a}$ je tedy taková tranzitivní ${\displaystyle b\supseteq a}$, že pro každou tranzitivní ${\displaystyle c\supseteq a}$ platí ${\displaystyle c\supseteq b}$. Jinými slovy ${\displaystyle b}$ je tranzitivní nadmnožina ${\displaystyle a}$, která neobsahuje „nic navíc“, než co je nutné pro tranzitivitu, a proto každá další tranzitivní nadmnožina ${\displaystyle a}$ je i nadmnožinou ${\displaystyle b}$.

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

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

Matematicky vyjádřeno, pro tranzitivní uzávěr ${\displaystyle R}$ binární relace ${\displaystyle R}$ platí:

${\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))]}$

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

Jelikož každý orientovaný graf je binární relace na množině uzlů, tranzitivní uzávěr grafu vznikne doplněním hran z ${\displaystyle a}$ do ${\displaystyle c}$, existuje-li hrana (šipka) z ${\displaystyle a}$ do ${\displaystyle b}$ i z ${\displaystyle b}$ do ${\displaystyle 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ů.

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

• Transitive closure of a directed graph - Algowiki. algowiki-project.org [online]. [cit. 2024-12-04]. Dostupné online. (anglicky)