Ero sivun ”Puu (graafiteoria)” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
p Botti muokkasi linkkiä / linkkejä |
|||
Rivi 1:
'''Puu''' on graafiteoriassa [[solmu (verkko)|solmuista]] ja [[kaari (graafiteoria)|kaarista]] koostuva [[graafi]], jossa minkä tahansa kahden solmun välillä on täsmälleen yksi [[polku (graafiteoria)|polku]]. ''Metsä'' on graafi, jossa minkä tahansa kahden solmun välillä on korkeintaan yksi polku.
== Määritelmiä ==
Puu on suuntaamaton graafi G, jos se täyttää minkä tahansa seuraavista yhtäpitävistä ehdoista:
Rivi 18:
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 ==
[[
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.
|