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

editovat

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   není tranzitivní, protože neobsahuje množinu  , ač tato je prvkem množiny  , která je prvkem  .

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

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

V kontextu relací

editovat

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

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

 

Například na celých číslech tranzitivní uzávěr relace „ “ je relace „ “. Tranzitivní uzávěr relace „ “ je „ “.

V kontextu grafů

editovat
 
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   do  , existuje-li hrana (šipka) z   do   i z   do  . 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

editovat

Pro orientované grafy existuje efektivní algoritmus pro nalezení tranzitivního uzávěru. Je složitost je  , kde   je počet hran,   počet vrcholů a   je počet hran spojujících jeho silně souvislýlmi komponentami.[1]

Reference

editovat
  1. PURDOM, Paul W. A Transitive Closure Algorithm. [s.l.]: [s.n.] Dostupné online. (anglicky) 

Externí odkazy

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