graafiteoriaan

Graafiteoria on matematiikan ala, joka tutkii graafeja. Graafi koostuu solmuista ja reunoista, jotka yhdistävät solmupareja. Reunat voivat olla suunnattuja (suuntautuva graafi) tai ei (suuntaamaton graafi). Graafeja käytetään mallintamaan suhteita ja yhteyksiä monenlaisissa ilmiöissä, kuten tietoverkoissa, sosiaalisissa verkostoissa ja logistiikkajärjestelmissä.

Historian alkujuuret ovat antiikissa, mutta graafiteorian kehityksen kynnys tuli Eulerin Königsbergin siltatehtävästä (1736). Tämän ratkaisun myötä syntyivät käsitteet kuten Eulerin polku, Hamiltonin polku ja graafien värittäminen. Keskeinen tulos on neliväriteoreema: planaarisia graafeja voidaan värittää enintään neljällä värillä.

Keskeisiä käsitteitä ovat yhteys, polut ja syklit, planaarisuus sekä aste. Algoritmeja käytetään käytännössä, kuten BFS ja DFS polkujen ja yhteyksien löytämiseksi, Dijkstra nopeimman reitin löytämiseksi, sekä Kruskalin ja Primin algoritmit minimipuun muodostamiseksi. Ongelmat kuten Hamiltonin polku ja matkustavan myyjän probleemi (TSP) sekä graafin värittäminen ovat tyypillisesti ongelmallisia ja kuuluvat NP-hard tai NP-complete -luokkiin.

Sovellukset: graafiteoria on keskeinen tietoliikenteen reitityksessä, verkostoanalyysissä, sosiaalisissa verkostoissa, biologiassa ja kemiassa sekä ohjelmistotutkimuksessa. Tämä ala on vahvasti vuorovaikutuksessa tietokonematematiikan ja soveltavan verkostotutkimuksen kanssa.