grafteorioissa

Grafiteoria on matematiikan ala, joka tutkii graafeja. Graafi G=(V,E) koostuu solmuista (V) ja reunoista (E). Reunat voivat olla suunnattuja (suuntautuneet) tai ei-suunnattuja. Painotetuissa graafeissa reunoille on annettu luku, joka kuvaa esimerkiksi kustannusta tai pituutta. Graafeilla mallinnetaan monenlaisia yhteyksiä ja suhteita: verkostoja, reittejä, sosiaalisia suhteita ja biologisia rakenteita.

Keskeisiä käsitteitä ovat solmujen aste, polut ja jaksot sekä yhteydellisyys. Graafi on yhteydessä, jos jokaisesta solmusta voidaan päästä toiseen reittien kautta. Polku on solmujen muodostama reitti; kierto on sulkeutuva polku. Eri tyyppejä ovat suunnatut graafit ja ei-suunnatut graafit sekä painotetut graafeja.

Perinteisiä ongelmia ovat Eulerin polku Königsbergin silloilla, Hamiltonin polut sekä väritysongelmat. Neljän värin teoreema väittää, että tasomainen graafi voidaan värittää neljällä värillä siten, että vierekkäiset solmut saavat eri värit.

Algoritmeja käytetään näiden ongelmien ratkaisuun. Esimerkkejä ovat syvyyssuuntautunut etsintä (DFS) ja leveyssuuntautunut etsintä (BFS), lyhyimmän polun Dijkstra, sekä minimipuumetsän Kruskal ja Prim. Maksimivirtoihin liittyviä ongelmia ratkaistaan usein Ford-Fulkerson -menetelmällä.

Sovelluksia ovat tietoliikenneverkot, reititys, sosiaaliset verkostot, biologia, kemia ja logistiikka. Grafiteoria on historiallisesti kehittynyt Königsbergin siltatilanteesta vuonna 1736; myöhemmin siinä menestyivät kuten Cayley, Tutte, Erdős ja Lovász. Nykyisin ala yhdistää combinatoricsin ja laskennalliset menetelmät teoreettisiin sekä käytännön ongelmiin.