Puu (graafiteoria)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 16.6.2020 tarkistetusta versiosta . tarkastukset vaativat 6 muokkausta .

Puu on yhdistetty asyklinen graafi . [1] Yhteydellä tarkoitetaan reitin olemassaoloa minkä tahansa kärkiparin välillä, asyklisyys tarkoittaa syklien puuttumista. Tästä seuraa erityisesti, että puun reunojen määrä on yksi vähemmän kuin kärkien lukumäärä, ja minkä tahansa pisteparin välillä on yksi ja vain yksi polku.

Metsässä on paljon puita.

Suunnattu (suunnattu) puu on asyklinen digraafi ( suunnattu graafi , joka ei sisällä syklejä), jossa vain yhden kärjen sisääntuloaste on nolla (sisään ei ole kaaria) ja kaikilla muilla kärjillä on sisääntuloaste 1 (täsmälleen yksi kaari johtaa niihin). Huippupisteitä, joiden sisääntuloaste on nolla, kutsutaan puun juureksi , ja pisteitä, joiden lopputulos on nolla (josta ei tule kaaria), kutsutaan terminaaleiksi tai lehtiksi . [2]

Aiheeseen liittyvät määritelmät

Huippupisteen aste on siihen osuvien reunojen lukumäärä.

Päätesolmu ( lehti , päätepiste ) on solmu, jonka aste on 1 (eli solmu, johon vain yksi reuna johtaa; suunnatun puun tapauksessa solmu, johon johtaa vain yksi kaari eikä kaaria mene ulos) .

Haarasolmu on ei-päätesolmu.

Puuta, jolla on merkitty kärki, kutsutaan juurtuneeksi puuksi .
- $m$ Puun kolmas taso on joukko puun solmuja, jotka ovat puun juuren tasolla. $T$ $m$
- osittaisjärjestys pisteillä: jos kärjet ja ovat erilaisia ja kärki sijaitsee (ainutlaatuisessa!) alkeisketjussa, joka yhdistää juuren kärkeen . $u\prev$ $u$ $v$ $u$ $v$
- juurialipuu juurtunut osagraafina . $v$ $\{v\}\cup \{w\mid v<w\}$
- Kontekstissa, jossa puulla oletetaan olevan juuri, puun, jolla ei ole erottuvaa juurta, sanotaan olevan vapaa .

Solmun taso - polun pituus juuresta solmuun. Voidaan määritellä rekursiivisesti:

puun juuritaso on 0; $T$
minkä tahansa muun solmun taso on yhtä suurempi kuin kyseisen solmun sisältävän puun lähimmän alipuun juuren taso . $T$

Virittävä puu ( runko ) on tietyn graafin osagraafi, joka sisältää kaikki sen kärjet ja on puu. Kuvaajan reunoja, jotka eivät sisälly runkoon, kutsutaan graafin sointuiksi suhteessa luurankoon.

Puuta kutsutaan redusoitumattomaksi, jos sillä ei ole 2 asteen huippuja.

Metsä on joukko (yleensä järjestetty), joka ei sisällä yhtä ei-leikkautuvaa puuta tai sisältää useita ei-leikkaavia puita.
Centroid - kärki, jonka poistamisen jälkeen tuloksena olevien yhdistettyjen komponenttien mitat eivät ylitä (puolet alkuperäisen puun koosta) ${\dfrac {n}{2))$

Binääripuu

Termillä binääripuu (käytetään myös termiä binääripuu) on useita merkityksiä:

Suuntaamaton puu, jonka kärkiasteet ovat enintään 3.
Suunnattu puu, jossa lähtevien kärkien asteet (lähtevien reunojen määrä) ei ylitä kahta.
Abstrakti tietorakenne, jota käytetään ohjelmoinnissa . Tietorakenteet, kuten binäärihakupuu , binäärikeko , puna-musta puu , AVL-puu , Fibonacci-keko jne. perustuvat binääripuuhun.

N-aariset puut

N-arvoiset puut määritellään analogisesti binääripuun kanssa. Niissä on myös suunnattuja ja ohjaamattomia tapauksia sekä vastaavia abstrakteja tietorakenteita.

N-aarinen puu (suuntaamaton) on puu (tavallinen, suuntaamaton), jonka kärkien asteet eivät ylitä N + 1.
N-aarinen puu (suunnattu) on suunnattu puu, jonka kärkien lähtevät asteet (lähtevien reunojen määrä) eivät ylitä N:a.

Ominaisuudet

Puulla ei ole useita reunoja tai silmukoita .
Mikä tahansa puu, jolla on kärjet, sisältää reunan. Lisäksi äärellinen yhdistetty graafi on puu silloin ja vain jos , missä on pisteiden lukumäärä ja on graafin reunojen lukumäärä. $n$ $n-1$ $BP = 1$ $B$ $P$
Graafi on puu, jos ja vain jos mitkä tahansa kaksi sen erillistä kärkeä voidaan yhdistää yhdellä yksinkertaisella ketjulla .
Mikä tahansa puu määräytyy yksiselitteisesti sen päätepisteiden (aste 1) välisten etäisyyksien (pienimmän ketjun pituus) perusteella.
Mikä tahansa puu on kaksiosainen graafi .
Mikä tahansa puu, jonka kärkijoukko on korkeintaan laskettavissa, on tasograafi .
Minkä tahansa kolmen puun kärjen kohdalla näiden kärkipisteiden välisillä poluilla on täsmälleen yksi yhteinen kärki.

Puiden laskeminen

Erillisten puiden lukumäärä, jotka voidaan rakentaa numeroituihin pisteisiin, on ( Cayleyn lause [3] ). $n$ $n^{{n-2}}$
Luova toiminto

T(z)=\summa _{n=1}^{\infty }T_{n}z^{n}

sillä ei-isomorfisten juurtuneiden puiden määrä, joilla on kärkipisteet, täyttää funktionaalisen yhtälön

T_{n}

n

T(z)=z\exp \sum _{r=1}^{\infty }{\frac {1}{r}}T(z^{r})

Luova toiminto

t(z)=\summa _{n=1}^{\infty }t_{n}z^{n}

ei- isomorfisten puiden, joilla on kärkipisteet , lukumäärä voidaan esittää juurtuneiden puiden listaussarjalla:

t_{n}

n

t(z)=T(z)-{\frac {1}{2}}\vasen(T^{2}(z)-T(z^{2})\oikea).

Seuraavalle asymptotiikka on totta $n\to\infty$

t_{n}\sim C\alpha ^{n}/n^{5/2}

missä ja ovat tietyt vakiot, , .

C

\alpha

C=0,534948...

\alpha =2,95576...

Puun koodaus

Puu voidaan koodata nollien ja ykkösten joukoiksi. Harkitse esimerkiksi puun laskemista koneeseen. Jostakin kärjestä alkaen siirrymme puun reunoja pitkin kääntyen jokaisesta kärjestä lähimpään oikealle olevaan reunaan ja kääntyen takaisin puun päätypisteistä. Jotakin reunaa pitkin kirjoitetaan kun kuljemme reunaa pitkin ensimmäistä kertaa ja kun kuljemme reunaa pitkin toisen kerran (vastakkaiseen suuntaan). Jos on puun reunojen lukumäärä, niin vaiheiden jälkeen palaamme alkuperäiseen kärkeen, kuljemme jokaisen reunan läpi kahdesti. Tuloksena oleva ja (puukoodin) pituuksien sekvenssi tekee mahdolliseksi palauttaa yksiselitteisesti paitsi itse puun , myös sen asettamisen tasolle. Satunnainen puu vastaa useita tällaisia koodeja. Tästä koodausmenetelmästä seuraa erityisesti seuraava karkea arvio huippupisteiden puiden lukumäärästä : $0$ $yksi$ $m$ $2 m$ $0$ $yksi$ $2 m$ $D$ $n$ $t_{n}\leq T_{n}<2^{2n}$

Prufer-koodi kartoittaa mielivaltaiseen äärelliseen puuhun, jossa on pisteet, numerosarjan alkaen - ja mahdollisia toistoja. Esimerkiksi kuvion puulla on Prufer-koodi (4,4,4,5). Merkittyjen kärkipuiden ja niiden Prufer-koodien välillä on yksi yhteen vastaavuus. Cayleyn kaava on johdettu Prüfer-koodista . $n$ $n-2$ $yksi$ $n$

Puu voidaan määrittää merkkijonona, joka sisältää merkkejä, jotka merkitsevät puun solmuja, sekä avaavia ja sulkevia sulkeita. Puiden ja niiden lineaaristen hakasulkeiden merkintöjen välillä on yksi-yhteen vastaavuus.

Katso myös

Graafiteorian sanasto
Erillisten joukkojen metsä
Luettelo tietorakenteista (puista)

Muistiinpanot

↑ § 13. Puun määritelmä // Graafiteorian luentoja / Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. - M . : Nauka, Fizmatlit, 1990. - S. 53. - 384 s. - 22 000 kappaletta. — ISBN 5-02-013992-0 .
↑ Alfs Berztiss. Luku 3. Graafiteoria. 3.6. Puut // Tietorakenteet = AT Berztiss. Tietorakenteet. teoria ja käytäntö. - M. : Tilastot, 1974. - S. 131. - 10 500 kpl.
↑ Diskreetti matematiikka: Algoritmit. Cayleyn kaava (pääsemätön linkki) . Haettu 29. lokakuuta 2009. Arkistoitu alkuperäisestä 14. kesäkuuta 2009. (määrätön)

Kirjallisuus

Donald Knuth . Tietokoneohjelmoinnin taito, voi. 1. Perusalgoritmit. - 3. painos - M .: Williams , 2006. - T. 1. Perusalgoritmit. – 720 s. - ISBN 0-201-89683-4 .
Ore O. Graafiteoria. - 2. painos — M .: Nauka , 1980. — 336 s.
Harari F. Graafiteoria. — M .: Mir , 1973. — 302 s.

Puu (tietorakenne)
Binäärihakupuu Puu (graafiteoria) puun rakenne
Binääripuut	binäärinen puu T-puu
Itsetasapainottavat binaaripuut	AA puu AVL puu Puna-musta puu Splay-puu puu sakkoilla karteesinen puu Fibonacci puu B-puu T-puu
B-puut	2-3-puu B⁺-puu B*-puu B x -puu UB puu 2-3-4 puu (a,b)-puu tanssiva puu
etuliite puita	suffiksi puu Pakattu etuliitepuu Kolmiosainen hakupuu
Avaruuden binaarinen osiointi	k-ulotteinen puu VP-puu
Ei-binääripuut	Quadtree oktreen Harva Voxel Octree eksponentiaalinen puu PQ puu
Avaruuden hajottaminen	R-puu Hilbert R-puu R+-puu R*-puu X-puu M-puu Fenwick puu Segmenttipuu
Muut puut	pino hash puu sormipuu metrinen puu Päällystyspuu BK-puu Kaksiketjuinen puu iDistance Linkistä leikattu puu LSM puu
Algoritmit	Leveys ensimmäinen haku Ensimmäinen syvyyshaku DSW-algoritmi kattava puu protokolla