Ero sivun ”Graafi” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
p kl: en |
Lisätty esimerkki |
||
Rivi 1:
'''Graafi''' on [[tietotekniikka]]an tai [[matematiikka]]an liittyvä käsite. Edellisessä se edustaa
[[abstrakti tietotyyppi|abstraktia tietotyyppiä]], joka koostuu joukosta ''kaaria'' ja niiden päihin kytketyistä ''solmuista''. Tietotekniikan graafikäsite seuraa suoraan vastaavasta matemaattisesta käsitteestä. Matemaattisesti ilmaistuna (suuntaamaton) graafi G on järjestetty pari
<math>G = (V, E)</math>
missä <math>V</math> on joukko solmuja (''vertices'') ja <math>E</math> joukko kaaria (''edges'').
== Luokittelu ==
Rivi 6 ⟶ 11:
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ää mihin tahansa toiseen solmuun kulkemalla riittävän monen solmun ja kaaren kautta, graafi on ''kytketty''.
== Esimerkkejä ==
Graafeja voidaan mallintaa monin eri tavoin. Ohessa esimerkki suuntaamattomasta graafista, joka kuvaa VR:n rataverkkoa muutaman suuremman kaupungin osalta:
<code>
G = (("Tampere", "Turku"), ("Tampere", "Jyväskylä"), ("Tampere", "Helsinki"), ("Helsinki", Turku"), ("Tampere", "Oulu"))
</code>
Ylläoleva graafi voitaisiin esittää visuaalisesti vaikkapa näin:
[[Kuva:vr_graafi01.png]]
Esimerkistä näkee esim. sen, että Helsingistä pääsee suoraan Turkuun, mutta että Jyväskylästä
ja Oulusta pitää mennä aina Turkuun Tampereen kautta.
{{tynkä/tietotekniikka}}
| |||