Ero sivun ”Graafi” versioiden välillä

549 merkkiä lisätty ,  2 vuotta sitten
ei muokkausyhteenvetoa
Ei muokkausyhteenvetoa
Ei muokkausyhteenvetoa
:<math>G = (V, E)</math>,
 
jossa ''V'' on joukko [[solmu (verkko)|solmuja]] eli pisteitä eli noodeja ({{k-en|vertex}}, monikko: ''vertices'', tai ''node'') ja ''E'' joukko kaaria eli viivoja eli välejä eli nuolia eli särmiä (''edges''). Kaarijoukon määritelmä voi vaihdella, mutta yleisin tapaus on
 
:<math>E \subset \{(a, b) : a, b \in V\}</math>
 
jolloin kaarella voi olla suunta ja se voi yhdistää solmun itseensä. Termiä "nuoli" ei käytetä, jos kaaret määritelläänkin vain kahden solmun joukoiksi eli niillä ei ole suuntaa.
 
Graafina voidaan mallintaa monia ongelmia, jotka pystytään ratkaisemaan algoritmisesti tietojenkäsittelytieteen keinoin.
[[Tiedosto:Directed acyclic graph.png|right|thumb|Kuva suunnatusta graafista, jossa on 8 solmua ja 9 kaarta.]][[Tiedosto:Undirected graph.svg|right|thumb|Kuva suuntaamattomasta graafista, jossa on 4 solmua ja 4 kaarta.]]
Graafeja voidaan jaotella eri luokkiin sen mukaan, mitä ominaisuuksia niillä on. Jos esimerkiksi
graafin jokaista solmuparia (a, b) yhdistävästä kaaresta seuraa aina, että myös solmujen (b, a) välillä on kaari, sanotaan, että graafi on ''suuntaamaton''. Vastaavasti jos mistä hyvänsä solmusta päästään mihin tahansa toiseen solmuun kulkemalla riittävän monen solmun ja kaaren kautta, graafi on ''kytketty''. Painotetussa graafissa jokaisella kaarella on kerroin. Jos jokaisesta solmusta pääsee jokaiseen toiseen solmuun vain yhtä reittiä, eli graafissa ei ole syklejä, sitä kutsutaan [[puu (graafiteoria)|puu]]ksi.
 
=== Puu ===
Jos jokaisesta solmusta pääsee jokaiseen toiseen solmuun vain yhtä reittiä, eli graafissa ei ole syklejä, sitä kutsutaan [[puu (graafiteoria)|puu]]ksi.
 
Puun kaaria kutsutaan myös oksiksi. Lehdiksi kutsutaan solmuja, joiden lähtöaste on nolla (eli jotka eivät ole minkään nuolen alkupisteitä).<ref>{{Verkkoviite| osoite=http://math.tut.fi/~ruohonen/GT.pdf | nimeke=GRAAFITEORIA | tekijä=Sovelletun matematiikan professori Keijo Ruohonen | ajankohta=2013}}</ref>
 
== Tietorakenne ==
 
Ehkä tunnetuin NP-täydellisistä ongelmista on [[Kauppamatkustajan ongelma]], jossa on tavoitteena löytää lyhin mahdollinen reitti, joka kulkee kaikkien kauppamatkustajan listassa olevien kaupunkien kautta. Tietojenkäsittelytiede ei kuitenkaan ole varma siitä, ovatko NP-täydellisiksi luetellut ongelmat ratkaistavissa jollain menetelmällä polynomisessa ajassa.
 
== Viitteet ==
{{viitteet}}
 
== Lähteet ==
5

muokkausta