Graafi
Graafi eli verkko on matematiikkaan (graafiteoria eli verkkoteoria) ja tietojenkäsittelytieteeseen liittyvä käsite. Se koostuu joukosta "solmuja" ja joukosta niitä yhteen liittäviä "kaaria". Matemaattisesti ilmaistuna graafi eli verkko "G" on järjestetty pari
jossa "V" on joukko solmuja eli pisteitä (, monikko: "vertices") ja "E" joukko kaaria eli viivoja eli välejä ("edges"). Kaarijoukon määritelmä voi vaihdella, mutta yleisin tapaus on
jolloin kaarella voi olla suunta ja se voi yhdistää solmun itseensä.
Graafina voidaan mallintaa monia ongelmia, jotka pystytään ratkaisemaan algoritmisesti tietojenkäsittelytieteen keinoin.
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 puuksi.
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.
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.
Graafeja voidaan mallintaa monin eri tavoin. Ohessa esimerkki suuntaamattomasta graafista, joka kuvaa VR:n rataverkkoa muutaman suuremman kaupungin osalta:
codice_1
Yllä oleva graafi voitaisiin esittää visuaalisesti vaikkapa näin:
Graafista näkee esimerkiksi sen, että Helsingistä pääsee suoraan Turkuun, mutta että Jyväskylästä
ja Oulusta pitää mennä aina Turkuun Tampereen kautta.
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.