Verkkoteoria

Verkkoteoria eli graafiteoria on matematiikan osa-alue, joka tutkii kohteiden välisten suhteiden esittämiseen käytettäviä matemaattisia malleja eli verkkoja. Verkot koostuvat solmuista ja niitä yhdistävistä linkeistä, jotka voivat olla suunnattuja tai suuntaamattomia. Verkkoteoriaa voidaan soveltaa monilla eri tieteenaloilla, kuten fysiikassa, biologiassa, sosiologiassa.

Suomen kielessä verkkoteorian perustermistö ei ole kovin vakiintunutta, sillä aihetta käsitteleviä suomenkielisiä kirjoja on julkaistu niukasti. Yksi harvoista suomenkielisistä verkkoja käsittelevistä kirjoista on Kimmo Pietiläisen suomentama teos.  

Verkkoteoriaa hyödyntävää poikkitieteellistä tutkimusalaa kutsutaan verkostotieteeksi, siinä missä verkkoteoria yleisesti mielletään matematiikan ja teoreettisen tietojenkäsittelytieteen osa-alueeksi. Pohjimmiltaan verkko on verkkoteorian määrittämä solmujen ja niitä yhdistävien linkkien kokonaisuus. Verkko kuvaa verkostomaisen rakenteen neutraalisiti riippumatta sen sisällöstä ja tulkinnasta ja esittää, mitä reittejä verkossa eri solmujen välillä on. Verkkoteorian keskeisiin tutkimusongelmiin kuuluvat mm. yhtenäisyys, laajentuvuus, väritettävyys ja satunnaisverkkojen analyysi.

Historia

Verkkoteorian alkuna pidetään sitä, kun Leonhard Euler ratkaisi Königsbergin siltaongelman vuonna 1736. Eulerin todistus oli samalla ensimmäinen todistus verkkoteorian alueella. Tuohon aikaan verkkoteoriasta käytettiin Leibnizin luomaa termiä "analysis situs", sanan "graph" otti käyttöön James Sylvester vuonna 1878 Nature lehdessä julkaisemassaan artikkelissa. Termi oli poimittu kemiasta. Tanskalainen Julius Petersen julkaisi verkkoteoriaa koskevia papereita 1890-luvulla.

Alun jälkeen verkkoteorian kehityksessä tapahtui vain vähän ennen 1930-lukua. Vuonna 1930 Kazimierz Kuratowski ratkaisi kysymyksen verkkojen piirtämisestä tasoon. Seuraava tärkeä etappi oli Dénes Kőnigin tasan 200 vuotta Eulerin siltaongelmaa koskevan tutkielman jälkeen vuonna 1936 julkaisema ensimmäinen verkkoteoriaa kattavasti käsittelevä kirja. Tärkeä verkkoteorian perusteos on myös Frank Hararyn vuonna 1968 julkaisema Graph Theory. Satunnaisverkot muodostavat nykyään yhden keskeisistä verkkoteorian tutkimuskohteista. Tämän aihepiirin klassinen merkkipaalu on Paul Erdősin ja Alfred Rényin vuonna 1959 julkaisema artikkeli tasajakautuneiden satunnaisverkkojen yhtenäisyydestä. Stokastiset satunnaisverkkomallit muodostavat modernin verkostotieteen ytimen ja niillä on paljon sovelluksia mm. bioteteissä, sosiaalitieteissä ja koneoppimisessa.

Graafialgoritmeja
 A*-etsintä
 Davidson–Harel-algoritmi
 Dijkstran algoritmi
 Floydin algoritmi
 Ford–Fulkerson-algoritmi
 IDA*-etsintä
 Karp–Held-heuristiikka
 Kruskalin algoritmi
 Leveyssuuntainen läpikäynti eli leveyshaku (, BFS)
 Primin algoritmi
 Syvyyssuuntainen läpikäynti eli syvyyshaku (, DFS)
 Unkarilainen algoritmi
 Warshallin algoritmi

Graafiongelmia
 Kauppamatkustajan ongelma
 Neliväriongelma

Katso myös
 Graafi
 Solmu
 Kaari
 Verkostotiede
 Heinz R. Pagels
 Skaalautumaton verkko

Lähteet

Viitteet

Aiheesta muualla

Kirjallisuutta 
 Ruohonen, Keijo: Graafiteoria (2004) (Yliopistotason opintomoniste graafiteoriaan)
vuoden 2013 versio via archive.org
Diestel, Reinhard: Graph Theory: Electronic (3rd) Edition
Diestelin oppikirjan verkkoversio, 312 sivua, PDF, ei tulostettavissa
 
 Savolainen, Vesa: Verkkoteoria (2001)

Graafiteoria
Seulonnan keskeiset artikkelit