Přechodné uzavření

Transitivní uzávěr je operace matematiky lze aplikovat na binární relace na množině , jinými slovy na orientovaných grafů .

Binární relace

Transitivní uzávěr , nebo tranzitivní uzávěr R trans binární relace R na nastavenou X je vztah

{\ displaystyle R ^ {\ rm {trans}} = \ bigcup _ {n \ geq 1} R ^ {n},}

což lze také přeložit takto:

Pokud pojmenujeme vztah „existuje cesta velikosti n mezi a a b“ ${\ displaystyle P_ {n} (a, b): \ Leftrightarrow \ existuje (c_ {0}, \ ldots, c_ {n}) \ v X ^ {n + 1} \ quad c_ {0} = a, c_ {n} = b {\ text {et}} c_ {0} Rc_ {1}, c_ {1} Rc_ {2}, \ ldots, c_ {n-1} Rc_ {n}}$ Definujeme ${\ displaystyle aR ^ {\ rm {trans}} b: \ Leftrightarrow \ existuje n \ in \ mathbb {N} ^ {*} \ quad P_ {n} (a, b).}$

Jedná se o nejmenší přechodný vztah k X , obsahující R .

Definujeme stejným způsobem tranzitivním reflexivní uzávěr R odrážejí-trans z R jako vztah

{\ displaystyle R ^ {\ text {reflect-trans}} = \ bigcup _ {n \ geq 0} R ^ {n} = R ^ {\ rm {trans}} \ cup \ Delta _ {X}}

(Kde je úhlopříčka X)

{\ displaystyle \ Delta _ {X}}

což lze také přeložit takto: ${\ displaystyle aR ^ {\ text {reflect-trans}} b: \ Leftrightarrow \ existuje n \ in \ mathbb {N} \ quad P_ {n} (a, b) \ Leftrightarrow (aR ^ {\ rm {trans} } b {\ text {nebo}} a = b).}$ Proto je reflexivní uzávěr z R trans , ale také tranzitivním uzávěrem R ref . Jedná se o nejmenší reflexivní a tranzitivní na X , který obsahuje R .

Například na nastaveném Z z relativních celých čísel , tranzitivní uzávěr přísně acyklického vztahu R je definován xR y ⇔ y = x + 1 je obvyklé striktní pořadí <a tranzitivní reflexivní uzávěr R je pořadí obvykle ≤.

Teorie grafů

Směrovaný graf G = ( V , A ) je binární relace A na množině V jeho vrcholů. Jeho přechodné uzavření nebo přechodné uzavření je graf C ( G ) = ( V , A trans ). Oblouky C ( G ) jsou dvojice vrcholů, mezi nimiž je v G cesta . To je také vyjádřeno takto: $\ forall (a, b) \ ve V ^ 2 \ quad a \ to b \ text {in} C (G) \ Leftrightarrow \ existuje n \ v \ N ^ * ~ \ existuje (c_0, \ ldots, c_n) \ ve V ^ {n + 1} \ quad c_0 = a, c_n = b \ text {a} c_0 \ to c_1 \ to \ ldots \ to c_ {n-1} \ to c_n \ text {in} G.$

Tranzitivní uzávěr lze vypočítat pomocí binární matice . Často dáváme přednost označení B = {1, 0}. Při programování algoritmů pomocí těchto matic může notace {TRUE, FALSE} koexistovat s notací {1, 0}, protože mnoho jazyků tento polymorfismus přijímá.

Související články

Reference

Jean-Pierre Ramis , André Warusfel a kol. , All-in-one Mathematics for the License: Level L1 , Dunod ,2013, 2 nd ed. ( číst online ) , s. 31.
Jiří Matoušek a Jaroslav Nešetřil , Úvod do diskrétní matematiky , Springer ,2004, 453 s. ( ISBN 978-2-287-20010-6 , číst online ) , s. 43.
(in) Eric W. Weisstein , „ Přechodné uzavření “ na MathWorld .