Graafi
Wikipedia
Graafi on tietotekniikkaan tai matematiikkaan liittyvä käsite. Edellisessä se edustaa 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
G = (V,E)
missä V on joukko solmuja (vertices) ja E joukko kaaria (edges).
[muokkaa] Luokittelu
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. Painotetussa graafissa jokaisella kaarella on kerroin. Jos jokaisesta solmusta pääsee jokaiseen toiseen solmuun vain yhtä reittiä, eli graafissa ei ole syklejä, sitä kutsutaan puuksi.
[muokkaa] Sovellusalueita
Graafeja ja niihin liittyviä algoritmeja käytetään varsin monissa erilaisissa sovellutuksissa. Esimerkkeinä mainittakoon vaikkapa lyhimmän tai ylipäätään reitin etsiminen ja riippuvuussuhteiden esittäminen sopivassa järjestyksessä (ks. topologinen lajittelu). Ylipäätään minkä hyvänsä ongelman ratkaisu, missä tiedetään alkutila, sallitut seuraajatilat ja tavoitetila (mutta ei suoraan miten sinne päästään), voidaan ainakin periaatteessa tuottaa graafialgoritmeilla.
[muokkaa] Esimerkkejä
Graafeja voidaan mallintaa monin eri tavoin. Ohessa esimerkki suuntaamattomasta graafista, joka kuvaa VR:n rataverkkoa muutaman suuremman kaupungin osalta:
G = (("Tampere", "Turku"), ("Tampere", "Jyväskylä"), ("Tampere", "Helsinki"), ("Helsinki", Turku"), ("Tampere", "Oulu"))
Yllä oleva graafi voitaisiin esittää visuaalisesti vaikkapa näin:
Graafista näkee esim. sen, että Helsingistä pääsee suoraan Turkuun, mutta että Jyväskylästä ja Oulusta pitää mennä aina Turkuun Tampereen kautta.