Træ (matematik)

I matematik er et træ dataene for et sæt E og en symmetrisk relation R på E, således at to forskellige punkter x og y af E er forbundet med en enkelt endelig injektionsvej, dvs. n + 1 point z 0 , .. ., z n af tydelig E, der bekræfter x = z 0 , z i Rz i + 1 for i <n, z n = y.

Træet ( E , R ) siges at være endeligt eller uendeligt afhængigt af om E er. For eksempel hvis E er foreningen af kanten af en disk og dens centrum c, og hvis xRy er forholdet x = c eller y = c , så er ( E , R ) et uendeligt træ; dog er de fleste af de uendelige træer, vi møder, tællelige. For finite træer, vores definition svarer til den af grafteori , terminologien af , som vi vil bruge.

For k > 1, de gitre N k og Z k har nogen naturlig træstruktur.

Forankret træ og ordenforhold

Du kan vælge ethvert toppunkt på et træ og orientere kanterne fra det; dette valgte toppunkt kaldes derefter roden . Vi får derefter et rodfæstet træ . Et rodfæstet træ gør det muligt at definere en ordrerelation på alle dets hjørner. Hvis xRy ser vi på den unikke injektionsvej, der forbinder roden med x , hvis denne sti går gennem y, orienterer vi y → x ( y er forgængeren til x ), ellers x → y . Man definerer således en orientering på træets kanter. Den transitive lukning af forholdet → definerer en ordrerelation:

{\ displaystyle x <y \ Longrightarrow \ eksisterer n> 0, \ findes (z_ {0}, \ cdots, z_ {n}) \ i E ^ {n + 1}, z_ {0} = x, z_ {n } = y, \ forall i, z_ {i} \ til z_ {i + 1}}

x < y betyder, at x er en af hjørnerne på stien, der forbinder roden med y .

Sættet med x, således at x < y er her endeligt. Men vi kan udvide forestillingen om træ som følger. Et ordnet sæt (E, <) er et træ, hvis det har et minimum (dets rod), og hvis sættet { x , x < y } for alle y af E er ordnet . Dette sæt er derefter i forbindelse med en ordinær .

Eksempler på uendelige træer

Stern-Brocot træ

The Stern-Brocot træ er en repræsentation af alle strengt positive rationals , i form af irreducible fraktioner .

Hver knude er af grad 3 undtagen de tre knuder 0/1 = 0, 1/1 = 1 og 1/0 = $\infty$ . Overvej at 1 er træets rod. Træet er defineret af iteration: to noder og har for far ; hvor og er strengt positive heltal. $\ scriptstyle {\ frac {m} {n}}$ $\ scriptstyle {\ frac {m '} {n'}}$ $\ scriptstyle {\ frac {m + m '} {n + n'}}$ $\ scriptstyle m, \, m ', \, n$ $\ scriptstyle n '$

Den Calkin-Wilf træ er et alternativ til at repræsentere strengt positive rationals i form af en uendelig træ, i form af irreduktible fraktioner: noden svarer til det rationelle har til venstre barn og for højre barn , roden har kun barn . Hver rationel er således kun repræsenteret en gang i træet. $\ scriptstyle {\ frac {a} {b}}$ $\ scriptstyle {\ frac {a} {a + b}}$ $\ scriptstyle {\ frac {a + b} {b}}$ $\ scriptstyle {\ frac {0} {1}} = 0$ $\ scriptstyle {\ frac {1} {1}} = 1$

Homogent træ af grad n

Et homogent træ af grad n er et træ, hvor hvert knudepunkt er af grad n , det vil sige at det er forbundet med n andre hjørner. Dette træ er så uendeligt .

Træ på et alfabet

Lad A være et alfabet, der ikke nødvendigvis er endeligt, og A * sæt af (endelige) ord skrevet fra A (tomt ord ε inkluderet), hvilket er en monoid til sammenkædning . Lad os definere relationer P (til forgængeren ) og S (til efterfølger ) mellem ord ved xSy , eller YPX , IFF x fås fra y ved at tilføje et brev til den til højre; derefter (A *, T) , hvor T er symmetrizeringen af P eller S , er et træ. Vi kalder træ over A ethvert træ (E, R), hvor E er en del af A * stabil ved at tage en forgænger (egenskab tæt på et transitivt sæt ), og hvor R tydeligvis er begrænsningen af T ; et sådant træ har en naturlig rod, ordet tomt. Dette eksempel, når A er lig med N eller N x N , vil blive udviklet nedenfor i sætteori.

Vi finder et bestemt tilfælde med sandsynligheder anvendt til populationsdynamik, mere præcist under undersøgelsen af Galton-Watson-processer , under navnet Neveu-notation . Træer forbundet med Galton-Watson-processer kaldes derefter Galton-Watson-træer .

Cantor's Tree

Cantorsættet er en bemærkelsesværdig delmængde af den rigtige linje iterativt konstrueret fra segment $[0, 1]$ ved at fjerne den centrale tredjedel; derefter gentages operationen på de to resterende segmenter og så videre. Vi kan se de første seks iterationer af processen på følgende diagram:

Vi betegner af operatøren "fjern den centrale tredjedel": ${\ mathcal {T}}$

{\ mathcal {T}}: [a, b] \ mapsto \ left [a, a + {\ frac {ba} {3}} \ right] \ cup \ left [b - {\ frac {ba} {3 }}, b \ højre].

Vi kan derefter repræsentere hvert interval ved noderne i et binært træ. Intervallet $[0, 1]$ er roden og de to intervaller og er de to børn i intervallet $[$ $a$ $,$ $b$ $]$ . Hvert interval, der således opnås efter n iterationer, kan mærkes med et ord med n bogstaver på alfabetet A = {0,1}, idets bogstav i ordet angiver, om vi under den i-iteration har valgt venstre eller højre interval. Sættet af intervaller danner et uendeligt træ i tilknytning til sættet A * af alle endelige ord på alfabetet A. Lad os udfylde dette træ ved at tilføje det kantorrum , dannet af ord, der består af en uendelig række på 0 eller 1 Lad os definere på dette sæt forholdet x < y hvis og kun hvis x er et præfiks for y . Derefter får vi Cantor-træet, hvis sæt af blade er nøjagtigt det sæt af uendelige ord, i forbindelse med Cantor-sættet. Nedenfor er en gengivelse af de seks generationer af dette træ. Knudepunkterne (eller sætene) er repræsenteret af vandrette linjer og træets kanter med lodrette linjer. $\ scriptstyle \ left [a, a + {\ frac {ba} {3}} \ right]$ $\ scriptstyle \ left [b - {\ frac {ba} {3}}, b \ right]$

I sætteori

Velbegrundet træ

Vi siger, at (E, <) er et velbegrundet træ, hvis der ikke er nogen uendelig rækkefølge . Cantors træ er ikke velbegrundet. ${\ displaystyle x_ {0} <x_ {1} <\ cdots <x_ {n} <\ cdots}$

Se også

Semester