Puu (graafiteoria)

Wikipediasta
Siirry navigaatioon Siirry hakuun
Tämä artikkeli käsittelee puuta verkko- eli graafiteorian käsitteenä. Puusta tietorakenteena katso artikkeli Puu (tietorakenne).

Puu on verkkoteoriassa solmuista ja kaarista koostuva verkko, jossa minkä tahansa kahden solmun välillä on yksikäsitteinen polku. Metsä on verkko, jossa minkä tahansa kahden solmun välillä on korkeintaan yksi polku.

Puun kaaria kutsutaan myös oksiksi. Lehdiksi kutsutaan solmuja, joiden lähtöaste on nolla (eli jotka eivät ole minkään nuolen alkupisteitä).[1]

Määritelmiä

[muokkaa | muokkaa wikitekstiä]

Suuntaamaton verkko on puu, jos se täyttää minkä tahansa seuraavista yhtäpitävistä ehdoista:

  • on yhtenäinen ja siinä ei ole syklejä.
  • on syklitön ja jos :hen lisätään yksikin kaari, muodostuu sykli.
  • on yhtenäinen ja jos :stä poistetaan kaari, ei ole enää yhtenäinen.
  • Minkä tahansa kahden :n solmun välillä on yksikäsitteinen polku.

Jos verkossa on äärellisen monta solmua (), seuraavat väittämät ovat yhtäpitäviä edellisten kanssa:

  • on yhtenäinen ja siinä on kaarta.
  • on syklitön ja siinä on kaarta.

Suuntaamaton verkko on metsä, jos se on syklitön.

Puu on juurellinen, jos yksi puun solmuista on nimetty juurisolmuksi eli juureksi. Tällöin kaarilla on suunta kohti juurta tai poispäin juuresta. Juurelliset puut ovat tärkeitä tietorakenteita algoritmitekniikassa.

Puu

Viereisen kuvan verkko esittää puuta, jossa on seitsemän solmua ja kuusi kaarta. Yksikäsitteinen polku, joka yhdistää solmut 1 ja 7 on 1–2–4–6–7.

  1. Sovelletun matematiikan professori Keijo Ruohonen: GRAAFITEORIA math.tut.fi. 2013. Arkistoitu 30.12.2020. Viitattu 25.10.2019.

Kirjallisuutta

[muokkaa | muokkaa wikitekstiä]

Aiheesta muualla

[muokkaa | muokkaa wikitekstiä]