Graafi

Graafi eli verkko on matematiikkaan ja tietojenkäsittelytieteeseen liittyvä käsite. Se koostuu joukosta solmuja ja joukosta niitä yhteen liittäviä kaaria. Matemaattisesti ilmaistuna graafi G on järjestetty pari

G = (V, E)

missä V on joukko solmuja (vertices) ja E joukko kaaria (edges). Kaarijoukon määritelmä voi vaihdella, mutta yleisin tapaus on

$E = \{(a, b) : a, b \in V\}$

jolloin kaarella voi olla suunta ja se voi yhdistää solmun itseensä.

Graafina voidaan mallintaa monia ongelmia, jotka pystytään ratkaisemaan algoritmisesti tietojenkäsittelytieteen keinoin.

Sisällysluettelo

[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] Tietorakenne

Tietojenkäsittelytieteessä graafia käytetään myös abstraktina tietotyyppinä tai tietorakenteena. Se toteutetaan yleensä vieruslistoina tai vierusmatriisina. Vieruslistaesityksessä solmun naapurit säilötään linkitettyyn listaan. Vierusmatriisiesityksessä matriisin alkion (a, b) arvo on tosi, jos solmusta a pääsee solmuun b, muuten epätosi.

Aina graafia ei tarvitse toteuttaa konkreettisena tietorakenteena. Solmun perusteella voidaan generoida lennossa uusia solmuja. Rekursiiviset funktioiden kutsut saattavat muodostaa verkkomaisen rakenteen. Joskus solmuista tiedetään ennalta jotain: esimerkiksi ruudukon ruudulla (x, y) on aina kahdeksan naapuria: (x + 1, y), (x, y + 1), (x + 1, y + 1) ja niin edelleen.

[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.

[muokkaa] Graafeihin liittyviä ongelmia

Graafeihin liittyy monia suuria avoimia ongelmia, joiden ratkaiseminen toisi keksijälle mainetta ja kunniaa. Monet graafeissa esiintyvistä ongelmista luokitellaan tietojenkäsittelytieteessä NP-täydellisiksi. Se tarkoittaa lyhyesti sanottuna sitä, että kyseinen ongelma on nykyisten tietokoneiden laskentakapasiteetin ulkopuolella, jos graafin solmujen tai kaarien joukko kasvaa riittävän isoksi. Emme siis tiedä menetelmää, jolla kyseinen ongelma voidaan ratkaista järkevässä ajassa.

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.

[muokkaa] Lähteet

Thomas Cormen, Charles Leiserson, Ronald Rivest ja Clifford Stein: Introduction to Algorithms – 2nd ed., s. 524–531. MIT Press ja McGraw-Hill, 2001. ISBN 0-262-03293-7.