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

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

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.

Ominaisuudet

Puiden laskeminen

sillä ei-isomorfisten juurtuneiden puiden määrä, joilla on kärkipisteet, täyttää funktionaalisen yhtälön . ei- isomorfisten puiden, joilla on kärkipisteet , lukumäärä voidaan esittää juurtuneiden puiden listaussarjalla: missä ja ovat tietyt vakiot, , .

Puun koodaus

Katso myös

Muistiinpanot

  1. § 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 .
  2. 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.
  3. Diskreetti matematiikka: Algoritmit. Cayleyn kaava (pääsemätön linkki) . Haettu 29. lokakuuta 2009. Arkistoitu alkuperäisestä 14. kesäkuuta 2009. 

Kirjallisuus