Chiusura transitiva
La chiusura transitiva è un'operazione che la matematica può essere applicata a relazioni binarie su un insieme , in altre parole su grafi diretti .
Relazione binaria
La chiusura transitiva , o chiusura transitiva R trans di una relazione binaria R su un insieme X è la relazione
RtranonS=⋃non≥1Rnon,{\ displaystyle R ^ {\ rm {trans}} = \ bigcup _ {n \ geq 1} R ^ {n},}
che può anche essere tradotto come segue:
Se chiamiamo la relazione "esiste un percorso di dimensione n tra a e b" Pnon(a,b): ⇔∃(vs0,...,vsnon)∈Xnon+1vs0=a,vsnon=b e vs0Rvs1,vs1Rvs2,...,vsnon-1Rvsnon{\ displaystyle P_ {n} (a, b): \ Leftrightarrow \ esiste (c_ {0}, \ ldots, c_ {n}) \ in 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}}
Definiamo
aRtranonSb: ⇔∃non∈NON∗Pnon(a,b).{\ displaystyle aR ^ {\ rm {trans}} b: \ Leftrightarrow \ esiste n \ in \ mathbb {N} ^ {*} \ quad P_ {n} (a, b).}
Questa è la più piccola relazione transitiva su X contenente R .
Definiamo allo stesso modo la chiusura riflessiva transitiva R riflessione-trans di R come relazione
Rriflettere-trans=⋃non≥0Rnon=RtranonS∪ΔX{\ displaystyle R ^ {\ text {riflettere-trans}} = \ bigcup _ {n \ geq 0} R ^ {n} = R ^ {\ rm {trans}} \ cup \ Delta _ {X}}(Dov'è la
diagonale di X)
ΔX{\ displaystyle \ Delta _ {X}}
che può anche essere tradotto come segue:
aRriflettere-transb: ⇔∃non∈NONPnon(a,b)⇔(aRtranonSb o a=b).{\ displaystyle aR ^ {\ text {riflettere-trans}} b: \ Leftrightarrow \ esiste n \ in \ mathbb {N} \ quad P_ {n} (a, b) \ Leftrightarrow (aR ^ {\ rm {trans} } b {\ text {o}} a = b).}
È quindi la chiusura riflessiva di R trans , ma anche la chiusura transitiva di R rif . Questo è il più piccolo riflessiva e transitiva su X contenente R .
Ad esempio sull'insieme Z di interi relativi , la chiusura transitiva della relazione strettamente aciclica R definita da x R y ⇔ y = x + 1 è il solito ordine rigoroso <, e la chiusura riflessiva transitiva di R è l' ordine usuale ≤.
Teoria dei grafi
Un grafo orientato G = ( V , A ) è una relazione binaria A sull'insieme V dei suoi vertici. La sua chiusura transitiva, o chiusura transitiva, è il grafo C ( G ) = ( V , A trans ). Gli archi di C ( G ) sono le coppie di vertici tra i quali v'è un percorso in G . Questo è anche espresso come segue:
∀(a,b)∈V2a→b nel VS(G)⇔∃non∈NON∗ ∃(vs0,...,vsnon)∈Vnon+1vs0=a,vsnon=b e vs0→vs1→...→vsnon-1→vsnon nel G.{\ displaystyle \ forall (a, b) \ in V ^ {2} \ quad a \ to b {\ text {in}} C (G) \ Leftrightarrow \ esiste n \ in \ mathbb {N} ^ {*} ~ \ esiste (c_ {0}, \ ldots, c_ {n}) \ in V ^ {n + 1} \ quad c_ {0} = a, c_ {n} = b {\ text {e}} c_ { 0} \ to c_ {1} \ to \ ldots \ to c_ {n-1} \ to c_ {n} {\ text {in}} G.}
La chiusura transitiva può essere calcolata utilizzando una matrice binaria . Spesso preferiamo la notazione B = {1, 0}. Quando si programmano algoritmi utilizzando queste matrici, la notazione {TRUE, FALSE} può coesistere con la notazione {1, 0} perché molti linguaggi accettano questo polimorfismo.
Articoli Correlati
Riferimenti
-
Jean-Pierre Ramis , André Warusfel et al. , Matematica all-in-one per la licenza: Livello L1 , Dunod ,2013, 2 ° ed. ( leggi in linea ) , p. 31.
-
Jiří Matoušek e Jaroslav Nešetřil , Introduzione alla matematica discreta , Springer ,2004, 453 p. ( ISBN 978-2-287-20010-6 , leggi online ) , p. 43.
-
(a) Eric W. Weisstein , " chiusura transitiva " su MathWorld .
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">