I grafteori er et tre et diagram som er syklisk og koblet sammen . Dens form fremkaller faktisk forgreningen av grenene på et tre . I motsetning til enkle trær, binære trær eller generelle algoritmeanalyse- eller analytiske kombinatoriske trær, som er spesielle innebygginger av trær (grafer) i flyet, kalles trær (grafer) noen ganger trær av Cayley , fordi de telles av Cayleys formel .
En samling trær kalles skog .
En graf representerer et sett med punkter, kalt hjørner eller noder , koblet eller ikke til hverandre ved hjelp av linjer, kalt kanter .
Det er derfor et veldig enkelt konsept og et veldig generelt modelleringsverktøy, nyttig på mange områder.
Vær oppmerksom på at arrangementet av toppunktene (plassering i rommet) ikke betyr noe, og ikke engang formen på kantene som muligens forbinder disse toppunktene (rett linje, kurve osv.). Det eneste som betyr noe er forholdet mellom toppunktene.
Et tre er en graf som tilfredsstiller følgende egenskaper:
En graf er et par slik at
Et tre er en graf slik at
Når det gjelder endelige trær, det vil si når settet med hjørner er endelig, er det en alternativ definisjon. Det er faktisk mulig å definere settet med endelige trær med toppunktene som tilhører et gitt ikke-fritt sett E (endelig eller uendelig) ved induksjon :
Med andre ord er tresettet hvis hjørner tilhører E det minste settet med grafer som tilfredsstiller de to første reglene ovenfor.
Det er flere veldig nyttige konsepter knyttet til trær, hvorav noen er gitt i tabellen nedenfor. Begrepene gitt her er faktisk alle gyldige i det generelle rammeverket for grafer. I tabellen fikser vi et tre ( S, A ).
Forestilling | Intuitiv definisjon | Formell definisjon |
---|---|---|
Tilstøtende hjørner | To hjørner x og y er tilstøtende hvis de er forbundet med en kant. | |
Tilstøtende kanter | To kanter en 1 og en 2 er tilstøtende hvis de deler den ene enden til felles. | |
Graden av et toppunkt x | Antall hjørner ved siden av x . | |
Blad | Vertex x hvis grad er 1. | |
Internt toppmøte | Vertex x hvis grad er strengt større enn 1. | |
Road kanter | Sti som består av flere tilstøtende kanter plassert ende til ende. | |
Avstand mellom to hjørner x og y | Størrelse på den korteste stien som forbinder x og y . | Hvis x og y er forskjellige, er avstanden d ( x, y )
og ellers er avstanden 0. |
Det er flere typer trær som kan være spesielle tilfeller av trær eller trær som strukturen er lagt til.
Et endelig tre er et tre slik at settet med toppunktene er endelig. Formelt sett er et tre ( S, A ) endelig hvis S er av endelig kardinalitet.
Vi kan legge merke til følgende egenskaper:
I det spesielle tilfellet hvor S er settet med heltall mellom 1 og n, så sier vi at treet ( S, A ) er et Cayley-tre (med n vertices).
Et lokalt endelig tre er et tre slik at graden av hvert toppunkt er endelig. Formelt sett er et tre ( S, A ) lokalt endelig hvis for et toppunkt x av S, er deg ( x ) endelig.
Et begrenset tre er alltid lokalt begrenset, men det omvendte er ikke sant. Antall hjørner av et lokalt endelig tre er endelig eller tellbar.
DemonstrasjonLa være et lokalt endelig tre. La oss fikse ethvert element . For inkluderer alle eksterne topper nøyaktig av . Ved sammenheng kan vi se at alle hjørnene tilhører en av . Med andre ord
På den annen side kan vi vise ved induksjon, ved hjelp av det faktum at det er endelig lokalt, at for alt er endelig. Så er en tellbar forening av endelige sett derfor er endelig eller tellbar.
Et rotfestet tre er ganske enkelt et tre hvis toppunkt har den spesielle statusen til roten . Formelt er et rotfestet tredobbelt ( S , A , r ) hvor ( S, A ) er et tre og r er et element av S som kalles rot.
Denne enkle forestillingen om rot gjør det mulig å gi en forfader / etterkommere type rekkefølge mellom treets hjørner. Forankrede trær er nyttige for modellering av slektsforskningen til en befolkning.
Forestilling | Intuitiv definisjon | Formell definisjon |
---|---|---|
Høyde av et topp-punkt x | Avstand mellom x og roten r . | |
Barn (eller sønn ) av toppunkt x | Vertice ved siden av x hvis høyde er lik x plus 1. | |
Forelder til et toppunkt x | Vertex slik at x er dets barn. | |
Nedstigning fra toppunkt x | Vertex som følger fra en foreldre / barnestam fra x . |
|
Forfedre til et toppunkt x | Vertex slik at x er en etterkommer. |
|
Kant som oppstår fra et toppunkt x | Edge som kobler x til et av disse barna. |
Et merket tre er et tre hvis hjørner (eller kanter) har en etikett , det vil si et element i et ikke-tomt sett (ofte er etiketter heltall eller reelle tall ).
Et tre har alltid kanonisk toppunktmerking: hvert toppunkt mottar seg selv som et merke. Dermed kan et Cayley-tre med n- toppunktene sees på som et tre merket injeksivt med heltallene fra 1 til n. Med denne kanoniske merkingen har toppunktene forskjellige etiketter. Fordelen med merkekonseptet er at det er mulig å gi identiske etiketter til flere forskjellige hjørner.
Et orientert tre er et tre der kantene er orientert, det vil si at de har en retning (de starter fra et toppunkt for å komme til et annet). Formelt et orientert tre er et par slik at
Et rotfestet tre har to kanoniske retninger:
Et rettet tre er alltid forbundet per definisjon (vi sier også svakt forbundet ), men er ikke nødvendigvis sterkt forbundet . Faktisk er det eneste sterkt koblede orienterte treet det trivielle treet som bare har ett toppunkt.
Et ordnet tre er et rotfestet tre slik at for hvert toppunkt er det spesifisert en total orden for settet med barn i dette toppunktet.
Vi kan vise at det er n n - 2 nummererte trær med n hjørner. Oppdagelsen av denne formelen har blitt tilskrevet Arthur Cayley for en tid . Av denne grunn kalles trær som grafer noen ganger Cayley-trær . Blant mange bevis, la oss sitere en som bruker Joyal Bijeksjon : å telle deler av settet av Cayley trær med n noder, Joyal etablerer en Bijeksjon mellom og settet av kart i , vanligvis bemerket . Det har vi altså
Hvis vi velger et toppunkt r i et tre, er det mulig å rote treet ved r , dvs. orientere alle kantene slik at det er en sti fra r til alle de andre noder. Vi får da et rotfestet tre .
Et tre er en plan graf : en graf som kan tegnes i planet uten at kantene berører, bortsett fra i endene. En slik tegning kalles noen ganger innbygging av en graf. De fleste plane grafer har flere ikke- homeomorfe embeddings , i den forstand at det for minst to av disse embeddingene ikke er noen homeomorfisme av hele planet mot seg selv som sender den ene innebyggingen til den andre embedding: klassene homeomorfismene til disse embeddings kalles plane kart . Homeomorfismeklasser av treinnbydelser (grafer) kalles også trær (plan, generell, katalansk). For oppregning er det praktisk å gi dem en rot, nemlig en orientert kant: vi snakker da om rotfestede plantrær . Følgelig bestemmes altså antallet plane trær forankret med n er kantene den n- te catalantall :
Eksempel: trær med 3 kanter (og 4 hjørner)Planertrær er umerket, mens Cayley-trær er ( n- toppunktene er merket fra 1 til n ). For eksempel er det to umoterte og umerkede trær med 3 kanter, den som har et toppunkt på grad 3 og 3 blader (stjerne med 3 grener) og den som har 2 hjørner av grad 2 og to blader (rad).
Treet kan vises med opprinnelsen til rotkanten nederst eller øverst (innen informatikk vises roten ofte øverst), og rotkanten enten helt til høyre eller helt til venstre (i figuren over rotkanten starter ved det røde punktet og slutter ved det blå punktet).
NevønotasjonEt rotfestet plantre kan beskrives entydig ved listen over toppunktene, hver betegnet av en endelig serie med heltall, som er posisjonene i deres søsken, til forfedrene til toppunktet: dette er nevøen . Den familietre brukes her som en metafor for planar treet: toppunktet 2 | 4 | 3 betegner 3 rd sønn av 4 th sønn av 2 nd sønnen til stamfar (stamfar selv blir utpekt av tomt suite, bemerket ). Etter konvensjon er forfedren den første toppunktet til rotkanten, og den endelige toppunktet til rotkanten er den eldste sønnen til forfedren: som sådan bemerkes det 1. Lengden på den tilknyttede sekvensen i et toppunkt er høyden (eller dybde ) i toppunktet, dvs. avstanden mellom dette toppunktet og begynnelsen av roten, som representerer forfedren: ved å følge metaforen representerer et toppunkt på høyden n et individ som tilhører n- generasjonen av den grunnlagt befolkningen av forfedren.
De 5 trærne med 3 kanter er således beskrevet av de 5 settene med ord
Ruten til toppunktene i leksikografisk rekkefølge er da den prefikserte dybderuten (eller prefiksruten) til et tre sett på som en datastruktur i informatikk. Videre oppfatter vi gjennom Neveu-notasjonen hvordan et plantre beleilig koder for en realisering av Galton-Watson-prosessen med utryddelse: det tilfeldige treet som oppnås ved å kode en realisering av Galton-Watson-prosessen, kalles noen ganger Galton-treet-Watson . Ingenting er imot å definere et uendelig plantre ved hjelp av Neveu-notasjonen, som tillater koding av realiseringene av Galton-Watson-prosesser der befolkningen ikke slukker .
På grunn av de interessante egenskapene til trær, spesielt innen teoretisk informatikk , er det noen ganger nyttig å bryte ned generelle grafer i trær. Således, for eksempel, de tre bredde er definert ved å lage grupper av noder er organisert i et tre, og arboricity ved fordeling kantene inn i skogene.