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 .
Puun kolmas taso on joukko puun solmuja, jotka ovat puun juuren tasolla.![T](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
![m](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
- osittaisjärjestys pisteillä: jos kärjet ja ovat erilaisia ja kärki sijaitsee (ainutlaatuisessa!) alkeisketjussa, joka yhdistää juuren kärkeen .
![u\prev](https://wikimedia.org/api/rest_v1/media/math/render/svg/2bbbd883c96896bc9168edc2956d07076188de24)
![u](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8)
![v](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
![u](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8)
![v](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
- juurialipuu juurtunut osagraafina .
![v](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
![\{v\}\cup \{w\mid v<w\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eafe5946e9aa79271222f86fbf427e977fa98320)
- 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](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
- minkä tahansa muun solmun taso on yhtä suurempi kuin kyseisen solmun sisältävän puun lähimmän alipuun juuren taso .
![T](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
- 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)
![{\displaystyle {\dfrac {n}{2))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76f92fa2b0cb17e753fc653b2fe9897e3d57551e)
Binääripuu
Termillä binääripuu (käytetään myös termiä binääripuu) on useita merkityksiä:
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](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![n-1](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521)
![BP = 1](https://wikimedia.org/api/rest_v1/media/math/render/svg/2caafc4c34e24ac6a5bd255bc6a20094418c0f96)
![B](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
![P](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
- 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](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![n^{{n-2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65a6e7866523a163c773c59df1fc7793ef534c56)
- Luova toiminto
![T(z)=\summa _{n=1}^{\infty }T_{n}z^{n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac8bf9d011907b2cb48262939fd8f4349494ad4e)
sillä ei-isomorfisten juurtuneiden puiden määrä, joilla on kärkipisteet, täyttää funktionaalisen yhtälön
![T_{n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d9241493be76739f2400f258f32c24f9689161f)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![T(z)=z\exp \sum _{r=1}^{\infty }{\frac {1}{r}}T(z^{r})](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d5807345fe182e8a77c511215c154546ac4e780)
.
![t(z)=\summa _{n=1}^{\infty }t_{n}z^{n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b63c1883a52bb421b7b67f60ae47cc92cf4084e4)
ei- isomorfisten puiden, joilla on kärkipisteet , lukumäärä voidaan esittää juurtuneiden puiden listaussarjalla:
![t_{n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/271566db7e8ca8616a4dc3efb6c5982a2d987ee3)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
- Seuraavalle asymptotiikka on totta
![n\to\infty](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0d55d9b32f6fa8fab6a84ea444a6b5a24bb45e1)
![t_{n}\sim C\alpha ^{n}/n^{5/2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46f74f8ca561b49ba6507ff2cc1a0bdd23a60ee9)
missä ja ovat tietyt vakiot, , .
![C](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
![\alpha](https://wikimedia.org/api/rest_v1/media/math/render/svg/b79333175c8b3f0840bfb4ec41b8072c83ea88d3)
![C=0,534948...](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3a72f48b79aadcc9477a00de4edf4a0ab847522)
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ä :
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950)
![yksi](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf)
![m](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
![2 m](https://wikimedia.org/api/rest_v1/media/math/render/svg/70e100f32f96dc84bf0591df4f5c5bd40d71189f)
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950)
![yksi](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf)
![2 m](https://wikimedia.org/api/rest_v1/media/math/render/svg/70e100f32f96dc84bf0591df4f5c5bd40d71189f)
![D](https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![t_{n}\leq T_{n}<2^{2n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/660e955a4f0cb245492eabb4c5040fadf4860842)
- 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](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![n-2](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff40d66ad535411eedb9c686a9008a5089c35ac0)
![yksi](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
- 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
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.