Transitiv lukking
Den transitive lukkingen er en operasjon matematikk kan brukes på binære relasjoner på et sett , med andre ord på rettet graf .
Binær forhold
Den transitive lukkingen , eller den transitive lukkingen R trans av et binært forhold R på et sett X er forholdet
Rtrpåikkes=⋃ikke≥1Rikke,{\ displaystyle R ^ {\ rm {trans}} = \ bigcup _ {n \ geq 1} R ^ {n},}
som også kan oversettes som følger:
Hvis vi navngir forholdet "eksisterer det en bane av størrelse n mellom a og b" Pikke(på,b): ⇔∃(vs.0,...,vs.ikke)∈Xikke+1vs.0=på,vs.ikke=b og vs.0Rvs.1,vs.1Rvs.2,...,vs.ikke-1Rvs.ikke{\ displaystyle P_ {n} (a, b): \ Leftrightarrow \ eksisterer (c_ {0}, \ ldots, c_ {n}) \ i 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}}
Vi definerer
påRtrpåikkesb: ⇔∃ikke∈IKKE∗Pikke(på,b).{\ displaystyle aR ^ {\ rm {trans}} b: \ Leftrightarrow \ eksisterer n \ i \ mathbb {N} ^ {*} \ quad P_ {n} (a, b).}
Dette er den minste transitive forhold på X inneholdende R .
Vi definerer på samme måte den transitive refleksive lukkingen R reflekterer-trans av R som forholdet
Rreflektere-trans=⋃ikke≥0Rikke=Rtrpåikkes∪ΔX{\ displaystyle R ^ {\ text {reflect-trans}} = \ bigcup _ {n \ geq 0} R ^ {n} = R ^ {\ rm {trans}} \ cup \ Delta _ {X}}(Hvor er
diagonalen til X)
ΔX{\ displaystyle \ Delta _ {X}}
som også kan oversettes som følger:
påRreflektere-transb: ⇔∃ikke∈IKKEPikke(på,b)⇔(påRtrpåikkesb eller på=b).{\ displaystyle aR ^ {\ text {reflect-trans}} b: \ Leftrightarrow \ eksisterer n \ i \ mathbb {N} \ quad P_ {n} (a, b) \ Leftrightarrow (aR ^ {\ rm {trans} } b {\ text {eller}} a = b).}
Det er derfor den refleksive lukkingen av R trans , men også den transitive lukkingen av R ref . Dette er den minste refleksive og transitive på X inneholdende R .
For eksempel på settet Z med relative heltall , er den transitive lukkingen av den strengt acykliske relasjonen R definert av x R y ⇔ y = x + 1 den vanlige strenge orden <, og den transitive refleksive lukkingen av R er rekkefølgen vanlig ≤.
Grafteori
En rettet graf G = ( V , A ) er en binær relasjon A på settet V for sine hjørner. Dens transitive lukking, eller transitive lukking, er grafen C ( G ) = ( V , A trans ). Enes buer C ( G ) er de par av topp-punktene mellom hvilke det finnes en bane i G . Dette uttrykkes også som følger:
∀(på,b)∈V2på→b i VS(G)⇔∃ikke∈IKKE∗ ∃(vs.0,...,vs.ikke)∈Vikke+1vs.0=på,vs.ikke=b og vs.0→vs.1→...→vs.ikke-1→vs.ikke i G.{\ displaystyle \ forall (a, b) \ i V ^ {2} \ quad a \ to b {\ text {in}} C (G) \ Leftrightarrow \ eksisterer n \ i \ mathbb {N} ^ {*} ~ \ eksisterer (c_ {0}, \ ldots, c_ {n}) \ i V ^ {n + 1} \ quad c_ {0} = a, c_ {n} = b {\ text {and}} c_ { 0} \ to c_ {1} \ to \ ldots \ to c_ {n-1} \ to c_ {n} {\ text {in}} G.}
Den transitive lukkingen kan beregnes ved hjelp av en binær matrise . Vi foretrekker ofte notasjonen B = {1, 0}. Når du programmerer algoritmer som bruker disse matrisene, kan betegnelsen {SANN, FALSK} eksistere samtidig med notasjonen {1, 0} fordi mange språk godtar denne polymorfismen.
Relaterte artikler
Referanser
-
Jean-Pierre Ramis , André Warusfel et al. , Alt-i-ett-matematikk for lisensen: Nivå L1 , Dunod ,2013, 2 nd ed. ( les online ) , s. 31.
-
Jiří Matoušek og Jaroslav Nešetřil , Introduksjon til diskret matematikk , Springer ,2004, 453 s. ( ISBN 978-2-287-20010-6 , leses online ) , s. 43.
-
(in) Eric W. Weisstein , " Transitive closure " på MathWorld .
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">