Suunnattu syklitön verkko

Suunnattu syklitön verkko eli DAG (engl. directed acyclic graph) on suunnattu verkko, jossa ei ole suunnattuja syklejä. Se koostuu solmuista ja solmujen välisistä suunnatuista kaarista siten, että kaaria pitkin ei ole mahdollista kulkea suunnattua polkua joka päätyisi lähtöpisteeseensä. [1]

Esimerkki suunnatusta syklittömästä verkosta

Suunnattuja syklittömiä verkkoja käytetään matematiikassa tai tietojenkäsittelytieteessä mallintamaan erilaisia rakenteita. Esimerkiksi osittaisjärjestys voidaan esittää DAGin avullalähde? ja koneoppimisessa käytetyt Bayes-verkot ovat rakenteeltaan DAGeja[2].

Lähteet
  • Barber, David: Bayesian Reasoning and Machine Learning (draft). Luonnosversio 21. marraskuuta 2011. Cambridge University Press, 2012. Teoksen verkkoversio. (englanniksi)

Viitteet
  1. Barber 2012, s. 25–26
  2. Barber 2012, s. 38

    Kirjallisuutta
    • Ruohonen, Keijo: Graafiteoria. Opintomoniste 136. Tampere: TTKK, 1990. ISBN 951-721-530-4.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.