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
editovatV 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í
editovatTranzitivní 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ů
editovatJelikož 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
editovatPro 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]
Odkazy
editovatReference
editovat- ↑ 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)