Grafiteoriassa

Grafiteoria on matematiikan ja tietojenkäsittelytieteen ala, joka tutkii graafeja. Graafi G = (V, E) muodostuu solmukohdista V ja kaarista E, jotka yhdistävät solmukohtia. Graafeja on sekä suuntautuneita että ei-suuntautuneita. Yksinkertainen graafi on sellainen, jossa ei ole silmukoita eikä useita kaaria saman parin välillä. Grafiteorian malleja käytetään verkkojen, reittien ja sosiaalisten suhteiden mallintamiseen.

Keskeisiä käsitteitä ovat polku (path), joka on solmukohdista muodostuva jono, sekä sykli (cycle), joka alkaa ja päättyy samaan solmuun. Yhdistetty graafi on sellainen, että jokaisesta solmusta löytyy polku toiseen, ja puu on yhdistetty graafi, jossa ei ole sykliä; siinä on n solmua ja n−1 kaarta.

Algoritmit ja ongelmat: DFS (syvyyssuuntautunut vierailu) ja BFS (leveyssuuntautunut vierailu) ovat perusmenetelmiä graafeihin tutustumiseen. Lyhyin polku voidaan löytää Dijkstra’n algoritmilla (ei-negatiiviset kaaret) tai Bellman–Ford -menetelmällä. Minimi-verkot ratkaistaan Kruskalin ja Primin algoritmeilla. Maksimaalisen virran laskemiseen käytetään Ford–Fulkerson- ja Edmonds–Karp -menetelmiä. Kromatiikka ja isomorfia ovat keskeisiä aiheita; monet niistä ovat NP-kovia.

Teoreettiset tulokset: grafiteoriassa käsitellään suunnitelmalluutta (planarity) sekä Kuratowskin lause, jonka mukaan graafi on suunniteltu, jos ja vain jos se ei sisällä K5:n tai K3,3:n subgrafiaa.

Sovellukset ovat laajat: tietoverkot, reititys, sosiaaliset verkostot, kemia ja biologia sekä logistiikka ja tiedon rakennevaihtoehdot.

Historia: Grafiteorian varhaiset juuret ovat Leonhard Eulerin Königsbergin siltatapauksessa (1736), mikä johti graafien tutkimuksen systematisointiin.