Puu (graafiteoria)

Wikipedia
Loikkaa: valikkoon, hakuun

Puu on graafiteoriassa solmuista ja kaarista koostuva graafi, jossa minkä tahansa kahden solmun välillä on täsmälleen yksi polku. Metsä on graafi, jossa minkä tahansa kahden solmun välillä on korkeintaan yksi polku.

Määritelmiä[muokkaa | muokkaa wikitekstiä]

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

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

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

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

Suuntaamaton graafi G 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.

Esimerkki[muokkaa | muokkaa wikitekstiä]

Puu

Viereisen kuvan graafi 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.

Katso myös[muokkaa | muokkaa wikitekstiä]