Graafi

Verkko eli graafi on matematiikkaan (graafiteoria eli verkkoteoria) ja tietojenkäsittelytieteeseen liittyvä käsite. Se koostuu solmuista ja niitä yhdistävistä kaarista. Matemaattisesti ilmaistuna verkko on järjestetty pari

$G=(V,E)$,

jossa V on joukko solmuja (engl. vertex, node) ja E joukko kaaria (linkkejä, viivoja, välejä; engl. link, edge). Kaarijoukon määritelmä voi vaihdella, mutta yleisin tapaus on

$E\subseteq \{(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.

Luokittelu

Kuva suunnatusta graafista, jossa on 8 solmua ja 9 kaarta.

Kuva suuntaamattomasta graafista, jossa on 4 solmua ja 4 kaarta.

Verkkoja voidaan jaotella eri luokkiin sen mukaan, mitä ominaisuuksia niillä on. Jos esimerkiksi verkon jokaista solmuparia (a, b) yhdistävää kaarta kohden on myös kaari (b,a), sanotaan, että verkko on suuntaamaton, muuten suunnattu. Jos mistä hyvänsä solmusta päästään mihin tahansa toiseen solmuun kulkemalla riittävän monen solmun ja kaaren kautta, verkko on yhtenäinen. Jos jokaisesta solmusta on kaari kaikkiin muihin solmuihin, verkko on täydellinen. Painotetussa verkoissa verkon solmuihin ja/tai kaariin voidaan liittää painokertoimia.

Polut ja syklit

Polku on jokin jono solmuja ja niitä yhdistäviä kaaria (vähintään yksi) niin, että polku alkaa solmusta, päättyy solmuun ja kulkee solmusta seuraavaan kaarta pitkin. Jos polku alkaa samasta solmusta kuin mihin se päättyy, sitä kutsutaan sykliksi tai kierrokseksi. Verkko, jossa ei ole syklejä, on syklitön, ja siinä solmusta pääsee jokaiseen toiseen solmuun vain yhtä reittiä pitkin.

Puu

Suuntaamatonta syklitöntä verkkoa kutsutaan puuksi. Puun kaaria kutsutaan myös oksiksi. Lehdiksi kutsutaan solmuja, joilla on vain yksi naapuri.

Suunnattu syklitön verkko

Pääartikkeli: Suunnattu syklitön verkko

Tietorakenne

Tietojenkäsittelytieteessä verkkoa 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 on kaari solmuun b, muuten epätosi.

Aina verkkoa 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.

Sovellusalueita

Verkkoja 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 verkkoalgoritmeilla.

Esimerkkejä

Verkkoja voidaan mallintaa monin eri tavoin. Ohessa esimerkki suuntaamattomasta verkosta, joka kuvaa VR:n rataverkkoa muutaman suuremman kaupungin osalta:

G = (("Tampere", "Turku"), ("Tampere", "Jyväskylä"), ("Tampere", "Helsinki"), ("Helsinki", Turku"), ("Tampere", "Oulu"))

Yllä oleva verkko voitaisiin esittää visuaalisesti vaikkapa näin:

Verkon kuvaajasta näkee esimerkiksi sen, että Helsingistä pääsee suoraan Turkuun, mutta Jyväskylästä ja Oulusta pitää mennä aina Turkuun Tampereen kautta.

Verkkoteorian ongelmia

Verkkoteoriaan liittyy monia kuuluisia avoimia ongelmia, joiden ratkaiseminen toisi keksijälle mainetta ja kunniaa. Monet verkkoteorian ongelmista luokitellaan tietojenkäsittelytieteessä NP-täydellisiksi. Se tarkoittaa lyhyesti sanottuna sitä, että kyseinen ongelma on nykyisten tietokoneiden laskentakapasiteetin ulkopuolella, jos verkon solmujen tai kaarten 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.

Lähteet

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

Kirjallisuutta

• Ruohonen, Keijo: Graafiteoria. Opintomoniste 136. Tampere: TTKK, 1990. ISBN 951-721-530-4.

Aiheesta muualla

• Kuvia tai muita tiedostoja aiheesta Graafi Wikimedia Commonsissa