Transitiv lukning
Den transitive lukning er en operation, som matematik kan anvendes til binære relationer på et sæt , med andre ord på rettet graf .
Binært forhold
Den transitive lukning eller den transitive lukning R trans af et binært forhold R på et sæt X er forholdet
Rtrpåikkes=⋃ikke≥1Rikke,{\ displaystyle R ^ {\ rm {trans}} = \ bigcup _ {n \ geq 1} R ^ {n},}
som også kan oversættes som følger:
Hvis vi navngiver forholdet "er der en sti af størrelse n mellem 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 \ findes (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 \ findes n \ i \ mathbb {N} ^ {*} \ quad P_ {n} (a, b).}
Dette er den mindste transitive forhold på X indeholdende R .
Vi definerer på samme måde den transitive refleksive lukning R reflekterer-trans af 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}}![{\ displaystyle R ^ {\ text {reflect-trans}} = \ bigcup _ {n \ geq 0} R ^ {n} = R ^ {\ rm {trans}} \ cup \ Delta _ {X}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d37c188f5d03ada1967566925584e10ab22e066a)
(Hvor er
diagonalen af X)
Δx{\ displaystyle \ Delta _ {X}}
som også kan oversættes som følger:
påRreflektere-transb: ⇔∃ikke∈IKKEPikke(på,b)⇔(påRtrpåikkesb eller på=b).{\ displaystyle aR ^ {\ text {reflect-trans}} b: \ Leftrightarrow \ findes n \ i \ mathbb {N} \ quad P_ {n} (a, b) \ Leftrightarrow (aR ^ {\ rm {trans} } b {\ text {eller}} a = b).}
Det er derfor den refleksive lukning af R trans , men også den transitive lukning af R ref . Dette er den mindste refleksive og transitive på X indeholder R .
For eksempel på sættet Z med relative heltal er den transitive lukning af den strengt acykliske relation R defineret af x R y ⇔ y = x + 1 den sædvanlige strenge rækkefølge <, og den transitive refleksive lukning af R er den sædvanlige rækkefølge ≤.
Grafteori
En rettet graf G = ( V , A ) er en binær relation A på sæt V for dens hjørner. Dens transitive lukning eller transitive lukning er grafen C ( G ) = ( V , A trans ). Buer af C ( G ) er de par af knudepunkter mellem hvilke der er en sti i G . Dette udtrykkes 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 \ findes n \ i \ mathbb {N} ^ {*} ~ \ eksisterer (c_ {0}, \ ldots, c_ {n}) \ i V ^ {n + 1} \ quad c_ {0} = a, c_ {n} = b {\ text {og}} c_ { 0} \ to c_ {1} \ to \ ldots \ to c_ {n-1} \ to c_ {n} {\ text {in}} G.}
Den transitive lukning kan beregnes ved hjælp af en binær matrix . Vi foretrækker ofte notationen B = {1, 0}. Ved programmering af algoritmer, der bruger disse matricer, kan notationen {TRUE, FALSE} eksistere sammen med notationen {1, 0}, fordi mange sprog accepterer denne polymorfisme.
Relaterede artikler
Referencer
-
Jean-Pierre Ramis , André Warusfel et al. , All-in-one matematik til licensen: Niveau L1 , Dunod ,2013, 2 nd ed. ( læs online ) , s. 31.
-
Jiří Matoušek og Jaroslav Nešetřil , Introduktion til diskret matematik , Springer ,2004, 453 s. ( ISBN 978-2-287-20010-6 , læs 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;">